発想の転換
計算機は小数点とか扱うの苦手なので、あまり÷(/)を使わない. できるだけ×をつかうと、int型のみで済む.doubleに変換しなくても良くなる. とくに、座標計算とか、角度もとめるとかはもろにそうで、 int x, y; ならば、 arg = atan2(y, x) とかとやるよりも、 pairp(x, y)とする方が扱いやすい。 double型だと、等しいものだと判定するのに、epsを使ってやったりと計算がものすごく煩瑣になる。e.g)SRM312 div2 difficult int型だと、判定基準に==を使ってやるだけでよく、煩瑣な計算も必要ない。 double型の計算をするのはどうしてもしなきゃいけない時のみにとどめる、というのを頭に入れておくとよいだろう。
階乗の計算で0!は1なので別個に考えなければならない可能性がある.
大文字と小文字を個別しないとかだったら、いっそのこと与えられた文字をすべて大文字にすれば良い. #definetoupper(int ch); toupper(word[i]); //string型の文字列をすべて大文字に。 string stringtoupper(string s) { int sz = s.length(); for(int i = sz; i < sz; i++) { s[i] = toupper(s[i]); } return s; }
巨大な数を扱う時、long long型で取り扱うのが、定石だが、 それでも、足りなさそうな見込みがあるときは、%を使えるときは使う。 たとえば、2乗で限りなく数が増えていくときは、i % 2 で、何とかしのぐ。 和を求めるとき(数を足し合わせるとき)、int型ならはみ出ないかどうかをチェックする。
施行する数の大きさも考える。 たとえば、N <= 1,000,000,000(一億回)なら、よほど簡単な計算でないと無理。 すくなくとも、全体をforでくくれない。コンテストの場合にはそういうことも考慮する。 例)DIV 472 medium
文字列をrotateする(何文字か右へずらす)とき、同じ文字列を二つくっつけると、華麗になる.
というか、自分が頭の回転早いなと思える?
string rotate = str + str; int len = str.length(); for(int i = 0; i < len; i++) { //検索[i, i+len)までの文字列を if(str == rotate.substr(i, len)) { cnt++; } } //そういえば、0.1sごとに電光掲示板みたいに文字をずらして、あたかも文字が左に行っているようにするとか、 Cの問題集で昔した記憶がある.
添字の中に添字を埋め込むと大変見づらくなるので、極力避ける.
//SRM478 div2 for(int i = 0; i < operations; i++) { bottles[ toId[i] ] += bottles[ fromId[i] ]; bottles[ fromId[i] ] = 0; if(bottles[ toId[i] ] >= capacities[ toId[i] ]) { bottles[ fromId[i] ] += bottles[ toId[i] ]-capacities[ toId[i] ]; bottles[ toId[i] ] = capacities[ toId[i] ]; } //非常に見にくい for(int i = 0; i < operations; i++) { int to = toId[i]; int from = fromId[i]; bottles[to] += bottles[from]; bottles[from] = 0; if(bottles[to] >= capacities[to]) { bottles[from] += bottles[to]-capacities[to]; bottles[from] = capacities[to]; } } //明らかに見やすさが違う.
方向とか文字別で場合分けするとき、else ifとかswitchを使ったりせずにいったん、char ch[5]とかにまとめて格納してから処理をするとコードが圧倒的に短くなる.
string getMinProgram(vectoractions) { string instr = ""; map table; //まとめて格納. char tabC[5] = "N-/|"; char tabR[5] = "SLFR"; //mapの使い方もこうすると賢い. for(int i = 0; i < 4; i++) { bar[tabC[i] ] = i; } string act = ""; for(int i = 0; i < actions.size(); i++) { act += actions[i]; } for(int i = 1; i < act.length(); i++) { int diff = (table[ act[i] ] - table[ act[i-1] ]+ 4) % 4; //まとめて文字を格納したときの効果がここで現れる. instr += tabR[diff]; } }
//数字入れ替え問題とか、なにかをswapしたり、flipしたりして何らかの(cntの)最小値を出す問題は //何回も同じ箇所をいれかえることは基本的にしない. //入れ替えて結局元に戻すのは無駄だから.必然的に貪欲法とかで解く可能性が高い。 SRM311 div1 easyなど。
maptable; pair pii; queue Q;