AtCoder Beginner Contest 008

 難しすぎる…

結果

 399/400 74:32 18位相当

 

 開始時刻 2017/07/22 16:15:00 提出履歴

A: アルバム - AtCoder Beginner Contest 008 | AtCoder

 0:30(AC)

 良心のやるだけ問題。植木算の要領でT-S+1が答え。

B: 投票 - AtCoder Beginner Contest 008 | AtCoder

 4:09(AC)

 名前をキーに投票数をmapで管理するのが良さげ。最後に最多得票者の名前を出力。これも良心。

C: コイン - AtCoder Beginner Contest 008 | AtCoder

 74:32(TLE, 99/100)

 ABCでこんな難しい問題が、しかもCで出ると思ってなかった。申し訳程度に全列挙して99点だけもらう。この問題は後で解いて別の記事にします。

 確率は扱いがわからない…。

 

 追記)解きました。

hidollara.hatenablog.com

D: 金塊ゲーム - AtCoder Beginner Contest 008 | AtCoder

 60:28(AC)

 しばらく考えて、W<=80、H<=80の99点解法はDPかなと思いつく。金塊を回収すると長方形が4つに分割されるので、分割統治してまとめていくような形。O(N*W^2*H^2)かな。

 で、DPを思い付いてすぐに座標圧縮に考えが至る。N=30なので座標圧縮した時に考える分割パターンは(30C2)^2くらいでなはずで、多分こうだろうと判断。

 ただ、座標圧縮が難しくて四苦八苦。頑張って対応する配列を作ったあたりで気づく。「タプル使ってmapでDPすれば無駄な計算しないで済むのでは?」

 ここまでの苦労にさよならバイバイ(git stash)して、方針を変更してタプルで実装を始める。意外とうまくいきそう。コンパイルする。…"Inplicit instantiation of undefined template"?何それ?

 結論から言うと、これはmapにunordered_mapを使っていたことによるエラー。tuple型の内部でhash関数が定義されていないせい(多分)で、unordered_mapは使えない。ということで、mapに切り替えてコンパイルしたら無事成功。テストケースがとりあえずうまくいったので、提出してAC。

感想

 確率問題は難しい。というかDも普通に難しい。これ本当にABC?

 とりあえずCは後で解かないといけない。確率に弱すぎて解説見てもちんぷんかんぷん…。