予選突破の練習のお題について

予選Aの問題のA〜Cは解けているという前提のものだったので、それを除くと残りの問題は

というところ。

れっつとらい

A: コンテスト - Typical DP Contest | AtCoder

A問題……なのだがこのコンテスト、

このコンテストは動的計画法 (Dynamic Programming, DP) の練習をすることを目的として作られています。

なので無理やりやっても解けない。ひどいや。
なんとかDPの配列をうまく考えようと思ったけどだめだった。写した。オワタ。

B: 難易度 - AtCoder Regular Contest 043 | AtCoder

まあこれ、↑より先に予選突破練習会で既にやってたんだけど。初めて私が(無駄に二分探索と)動的計画法をやった記念すべきでもない瞬間である。
これも写した。無茶苦茶にやってTLEになってたころは全チェック終わってTLEって出るのに相当時間かかったけど、ちゃんとやったら一瞬でACって出た。すごい。

D: 壊れた電車 - CODE FESTIVAL 2015 予選A | AtCoder

これの点が少しでも取れていれば本戦に……しかし、部分点以前の問題としてどうやればいいのかすらわからなかった。
この問題を当日Ruby2.2.2で解いてた人、いなかったんだよなあ。1.9.3は1人いたけど。やはり世間的にはCとかJavaなのか。
みんなの答え見たらめっちゃ少ないコード量で解けてて泣いた。そしてコード量が少ないのに(少ないから)問題の解法が読み取れない。

E: 常ならずグラフ - CODE FESTIVAL 2014 決勝（オープン） | AtCoder

特に何か工夫するってわけじゃないけど、 ＼＿／ みたいな形を考慮するの忘れてた。

C: Palindrome Concatenation - Indeedなう（オープンコンテストB） | AtCoder

おっ、RubyでACした人が1.9でも2.2でもいないぞ!これはRuby初ACのチャンス!!→ダメだったよ……
解法わからない時点でダメなのだが、仕方ないと言って他言語AC(DP使ってちゃんと通ってるやつ)から写してもTLEが出るという。なんか写した時に余計なことしたかなあ。うーん。わからん。でも一応部分点は来た。

B: ゲーム - Typical DP Contest | AtCoder

漸化式と似たような発想をすればいいというのがわかってきたので、漸化式のようなものを考えようとしたけれど、ダメだった。

感想

説明されればわかるんだけど、これどうすればそういう発想になるの?
今週末大丈夫かなぁ。

S_Shimotori’s diary

CODE FESTIVAL予選突破の練習をする