notepad

いろいろ書くメモ帳

ABC008を解いた

今回はAtCoder Beginner Contest 008を解きました.公式解説はこちら

A アルバム

自力完答
2つの整数S,T間の整数の個数を求める問題.S,Tも個数に含まれるのでT-S+1で求められる.

B 投票

自力完答
Mapや辞書が実装されている言語だと簡単に解ける. キーを人物名,値を得票数に割り当てて処理を行い,値が最も大きいキーを出力すれば良い.

C コイン

自力で99点
とりあえず全探索で実装してみるも,もちろんTLEで99点. 動的計画法でも使うのかと思ったが,解説を見ると解析的に解けるらしい. 目的のコインの左側に約数のコインが何個あれば云々…というところまでは思いついたが,期待値の計算ができなかった. 確率論は苦手.

D 金塊

自力では解けず
この問題もとりあえず全探索で実装して動かしたが,中間点ももらえないほど実行時間が遅かった.Pythonだから仕方ないのだろうか.

装置を起動すると,装置を中心として十字に金塊を回収するため,回収後は4つの領域にわけられる. これを利用し,動的計画法を使って,取りうるすべての領域について計算すれば解けるようだ. 解説のようにDPテーブルを作るよりも,メモ化再帰を使ったほうが単純そうだったので,メモ化再帰で実装した.

メモとしてi,j,k,lの組をキーとした辞書を使うことで,座標圧縮のことを考えたりすることなく簡単に実装することができた.

感想

Pythonはゴリ押しが厳しい