ABC008を解いてみた
A問題
入力SからTまでの数の個数を数えればいいのでT-S+1を出力しました。
B問題
全探索で名前が同じであればその名前の票数に対応する変数を+1し一番票数が多い名前を出力しました。
C問題
部分点狙いの全探索で実装しました。itertools.permutations()を使ってコインの並びを全て数え上げ、それぞれの並びに対して手順の処理をしました。そして表の総数をn!で割った数を出力しました。コインが表か裏かを管理する変数を用意し、1で表、0で裏と対応させ変数の合計で表の総数が求められるようにしました。また、 a=1-a でフラグの反転を実装しました。
満点解法は解説読んで理解できたのでそのままコードに落とし込みました。
D問題
全探索しか思い浮かびませんでした… 機械を動かすと4つの領域に分割されそれらが独立している領域であるということから動的計画法を用いて計算することで99点、さらに座標圧縮によりメモリを節約することで満点ということで納得です。
全体の雑感
全探索で解ける問題だけしか解けていないのでアルゴリズムを覚え実装に慣れていきたいです。
