あるごリズム備忘録

学んだことの記録と日記

競プロの記録 (2016_09_11)

今日は新規4問を解き、ABC045へ参加した。

1問目
No.98 円を描こう - yukicoder

計算上の直径を超えるまで半径を1ずつ増やすとかしていたけど、
計算上の半径の2倍に1足してintでキャストするだけでよかった。

2問目
No.99 ジャンピング駒 - yukicoder
偶数座標にコマ1つと、奇数座標にあるコマ1つのセットで、この2つのコマが消える。したがって、その二つを数え上げて、差を出してやればよい。

3問目
No.104 国道 - yukicoder

文字列を頭から見ていって、毎回2倍し、右ならそこに1加算する。

4問目
No.111 あばばばば - yukicoder

入力文字列の中の、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日。