競プロ(C++)メモ
れあ
long long型でpow関数を使うと、正しく計算されない。
(pow関数がdouble型で返されるためだと思うのだが、仮数部は十分に広いはずだしなぜ？？となっている。たしかに、2の累乗は10の累乗に近似しかできないけども…)
暫定的に、nがlong long型のときは、pow(n,2)よりn*nを使う。
テストケース15(AtCoderのテストケースより)
in:
2
-607207239 -1000000000 -607167600 -214414478
-1000000000 -1000000000 392792761
-999960362 -214414478 392792762
out:
Yes
れあmodintは明示的にmodint(N)のようにしないと、うまく動かない。
公式ドキュメントでは、
modint y = 10;
int z = 1234;
y * z; // y * modint(z)と解釈される
とあるが、*=などは特に記載がない。
例えば、以下の問題 では、
cnt *= ((mint(K) - mint(1)) * mint(K)) / 2;
は良くて、
cnt *= ((K - 1) * K) / 2;
はダメだった。
※using mint = modint1000000007;を宣言
基本的に、型が違う場合は明示的に指定すべきなのは承知。
intとllもそう。coutで文字とintが混在するのも本来ならそう。でも競プロだとしないことが多い。
忘れた頃に引っかかると思うので、注意。
れあ「前提となる部分」については、初期化がてら、先に計算を済ます方が良さそう。
今日のコンテストのこの問題で、初期化すべきところを全探索と同時並行で行ってしまい、3WAした。
具体的には、
?1000
23
のような場合を考慮しておらず、ビットの桁の大きい方から、可能な限り足していくようにした結果、?1000を11000(24)と扱ってしまい、本来なら解があるところを-1と出力してしまう。
?1000を01000(8)と扱えば問題なく8が解になる。
これは、1の書かれたところを最初に足しておくことで、解決した。
1と書かれたところは不変で前提と見て良いので、こういう処理は先にしておく。
れあnext_permutationを使う前に、必ずソートするように…。