Codeforces #309 Div.2 <失敗談>
今回はレートが回復したのでよしとする。(1291->1411)
A.
考えるのがめんどくさかったので無思考でsetを使って通した。計算量的に足りるので問題なし。O(s.size()*26*log(s.size()*26))?
B.
一つの列を掃除するとすべての行に影響してしまう。ここから結局全く同じ配置の行がどれくらいあるかに帰着される。実装も簡単。思考タイプの問題。O(n^3)
C.
本番では解けなかった。DPを使うのだろうと見当はついていたが後ろの方から決定していくという最初のアイデアに固執してしまっていた。(回答は1,2,...,kと順に決めている。)
昇順に考えると、次におくボールは一番後ろに必ず1個おいて、あとは自由となるので
(c_1+c_2+...+c_i -1)C(c_i -1)通りとなる。これをかけていけばいい。
(よく考えると高校レベルの組み合わせな気がして泣けてくる)
D.E.はいつかやる。
D.
そもそも問題文を理解できてなかったので詰み。コンテスト後読み返し、理解すると、抜き出して法則性を探していくタイプ。やってくとフィボナッチとなっているのがわかるので、フィボナッチ進数みたいなことをやる。
Codeforces #308 Div.2 <失敗談>
A.
ACできたので特になし。
B.
1~nまで数字を書くとき、合計何桁の数字を書くかという問題。
考え方は良かったが、pow(n,r)がintの値を返すと思っていたが、doubleだったため、計算結果がdoubleになり、誤差が発生してしまった。こういう時はforの中で数値をかけていった方が安全。
C.
w^0,w^1,,...,w^100を足し引きして、mを作ることができるかという問題。
w進法を使うところまでは近かったが、実装できなかった。実装力。w進法をつかって各桁の数を求めたがその方法だと桁上がりの処理が面倒。while(m!=1){... m/=w;}という形にしたほうが元の数として扱えて便利。発想が凝り固まっていた。
D.
n個の座標が与えられ三角形がいくつできるかという問題。
コンテスト中は見ていなかったが多分Cより簡単な気がする。C++は実行速度が速いので、O(n^3)で通ってしまう(細かく言うとO(nC3))。とりあえずすべての問題を見ておく。オーダーぎりぎりもせめてみる。
E.
+と*の数式に()をつけて最大となる値を求めるという問題。
これも難しいことを考えずに総当たりを実装すればいい。実装が(僕的に)難しいので多分コンテスト中は解けなかったと思う。
今回の問題は発想力がいるような問題はほとんどなく、実装できればよいので、冷静にバグを除いていけば結構得点できたんじゃないかと思う。
Now Rating: 1291 (-81)
失敗談
最近めちゃくちゃCodeforcesできないので、気分ガン下がりである。目標としてはA,B,C問題を解きたいのだけれども、Aしか解けてないような状態が続いてる。のでコンテストでの失敗の原因を挙げていこうとおもう。ブログに書くことで問題点を認識し、同じ間違いをしないようにしたい。
コードの変化
ABCを一通りやってACできなかった過去の自分の提出コードを見てると、競プロやり始めてからコードの書き方がかわったような気がする。具体的にいうと
・マクロの多様
・よくわからない変数名
といった感じだ。STLに関しては別に悪いことじゃないと思う。例えばmin,maxは自分で二項演算子でかけるだろうけど、それを書けばコードが長くなって可読性が下がる気がする。それよりも一つの命令で書いてあった方が全体の中で何をしているのかがわかりやすい。それが自分で書くと4行とか掛かってしまうコードとかでは如実に出ると思う。役割でのオブジェクト指向みたいなそんな感じだ。
マクロの多様については判断を任せたい。僕的にはREP(i,n)REP(i,m)って書いた方がすっきりしてタイプも減って可読性が高いと思うのだけれど、なれない人にはわかりにくいだろう。for(int i=0;i<n;i++)を打つのに10秒くらいかかるけどREP(i,n)は3秒くらいでできる（タイプが遅いのは勘弁）
変数名が適当なのは競プロが悪いのではない。単純に僕が英単語を知らなくて適切な長さの英単語の変数をつけることができないだけである。
コンテスト中辞書引いて適切な単語を使おうということにはならず、その場で適当な変数を作る。のでそんな感じになってしまうのである。これに関してはプログラマが使うような英単語はだいたい限られているので人のコードを読んで使える英単語の幅を増やそうということだ。
hogehoge
最近ABCのCが解けなくてヘイトが高まる。
あとすぐに回答解説を見るのをやめたさ
ABC#024の戦績
A,B,CがACで300点、順位的には100位というキリ番。やっぱりコンテストになると若干焦ってコードが雑だったりコーナーケースを逃したりするので場慣れしたい。
A.
場合分けするぐらいで特に言うことはない。
B.
まあ見るからにいもす法なのでそのまま組む。始点と終点の設定を若干しくってしまったのでちょい時間ロス。
C.
これはちょっと考察した。移動の仕方は法則があるのかとか考えたけど、考えるうちに安直なことに気づいてgreedy。ここまでで45分ぐらい。
D.
動的計画法って書いてるけどどう考えてもメモリも時間も足りない。O(N^2)だけどO(NlogN)とかにへらすなら行列にしてダブリングかと思ったけど行列がそもそもN^3だし無理だ。というわけでやっぱり代数的にO(1)かなって思う。
ごりごり数式をいじって二元連立方程式になり解いた。けど当然割り算がでてくる。合同式で割り算てまずいんじゃねっけって思考停止。諦め。
//Dの解法
解法はやっぱり代数的な解き方。問題は合同式での割り算。
合同式での割り算は条件を満たせばできる。ただし逆元をかけるという方式を使う。逆元というのはXY=1(mod p)となるYのこと。これば実数でいえば1/xだったりする。合同式ではどうかというとmod素数なら簡単に求まる。
フェルマーの小定理というのがあってaと素数pが互いに素であるとき
a^(p-1)=1 (mod p)
がなりたつ。これよりaの逆元はa^(p-2)となる。今回は10^9+7で素数なのでこれが利用できる。
でもp乗って10^9+7じゃん...
これはまあ察しがつくようにダブリングをすればいい。これでO(logN)となって問題解決。
あとはプログラムをかくだけ。...だったのだが入力をintにしていたためオーバーフロー。
10億7の問題ではlong longを使いましょう。ってオチ
