競プロの記録 (2016_09_11)
今日は新規4問を解き、ABC045へ参加した。
計算上の直径を超えるまで半径を1ずつ増やすとかしていたけど、
計算上の半径の2倍に1足してintでキャストするだけでよかった。
2問目
No.99 ジャンピング駒 - yukicoder
偶数座標にコマ1つと、奇数座標にあるコマ1つのセットで、この2つのコマが消える。したがって、その二つを数え上げて、差を出してやればよい。
文字列を頭から見ていって、毎回2倍し、右ならそこに1加算する。
入力文字列の中の、i(奇数)文字の部分文字列は回文となっている。
サイズiの文字列はL-i+1個含まれいる。
iを大きくしながらカウントする。
5問目
No.112 ややこしい鶴亀算 - yukicoder
与えられる入力X[i]のパターンは2種類。
X[i]のうち、大きいほうの数が鶴の数、小さいほうの数が亀の数になる。
setで数を記録したりとかしていたけど、もっと簡単な方法があるのだろうか。
結果は、2完で166位、レートは349。
悔しい。さすがに3完はしたかった。
次回の目標はレート3完で650以上。
A問題
A: 台形 / Trapezoids - AtCoder Beginner Contest 045 | AtCoder
やるだけ。
B問題
B: 3人でカードゲームイージー / Card Game for Three (ABC Edit) - AtCoder Beginner Contest 045 | AtCoder
シミュレーションする。
ルールの読み間違えで手間取った。
終了条件は「0枚自分の番を迎える。」なのに、「0枚になった瞬間」かと思っていた。
C問題
B: 3人でカードゲームイージー / Card Game for Three (ABC Edit) - AtCoder Beginner Contest 045 | AtCoder
bitと使って全探索するだけ。
何ビット目かす変数jと、今見ている位置を同期させればシンプルでうまくいく。
しかし、ビットの進む方向と、文字列を見ていく方向が逆(数字の増え方は同じ)だったため、ここで詰まってしまった。
図を書くときに、位置の「数字」もしっかり書き込むことで改善できそう。
本番中は解けなかった。
制約が|S|<=10の時点で、bit探索を思いつくべきだった。
やはり「まずは全探索を考える」ことが大切だ。
この習慣は持っておきたい。
(補足)
stringからintへの変換に、stoi()は使えないらしい。
普通にS[i]-'0'で数値に直すのが無難。
久しぶりにABCにリアルタイムで出場した。
強くなりたいなら、やはりコンテストに出続ける必要があると感じた。
コンテスト中の必死さやアイディアが出ないもどかしさ、
コンテスト後の悔しさや練習不足への後悔など、
モチベーションを大きく刺激してくれる。
まずは今回のCのような問題を確実に解き切れるようにしなければならない。
そのためには、yukicoderの星1問題だけではこの手のアイディアの蓄積ができないし、
そもそもAtCoderの問題とyukicoderの問題では簡単な問題の傾向がかなり違うように感じられる。
CODEFESTIVALの予選だと、それほど求められない要素も多いような気がする。
そこで、今後1週間の1日当たりのプランは次のように定める。
1.yukicoder(星1):3問 (15×3分程度)
※勢いをつける。
2.yukicoder(星1):4問 (50×4分程度)
※定番アルゴリズムを身につける(思い出す)。
3.再解答(60分程度)
※必要なことだが解き直しはモチベーション的につらいため時間で区切る。
これを最低ノルマとする。空いた時間は、yukicoder(星1)を解き続け、AC癖をつけた。
また今後は、記事に書くのは基本的に星2以上の問題に限り、
星1問題は、よほどきになった点以外は記事にしないか、新しく知った小ワザ等のみをまとめて書く。
A予選まであと13日。