こんばんは、ゴドーです。
今日のAtCoder Beginner ContestはA~Eの5問完答でした。
Aは一瞬でしたが、Bで積を取る前のMOD計算を忘れてWAを２回出してしまいました。
オーバーフローを避けるために先にMODを取るのは基本中の基本なので、注意しなければなりませんね。
C問題は正方形の判定に手間取りましたが、ユーザー解説にある通り、四角形の辺の長さから正方形を判定する方法を採りました。
解くには解けましたが、公式解説にある２点を決めて判定する方法の方がスマートでしたね。
逆にD問題は明らかにメモ再帰と分かったのでほぼ一瞬。
今回はC問題よりD問題の方が簡単でした。
E問題は見るからに動的計画法ということで、解説通り、ｋ回ルーレットを回したときに各マスにいる確率を更新していくことで回答。
方針自体は大きく迷いませんでした。
F問題にも手を付けましたが、こちらは全く歯が立たず。
部分和を計算して削除する候補を作っていく方法を考えましたが、１手だけ削除するならまだしも、２手目以降を考えるとどう処理していいのか分かりません。
解説は問題の読み替えを加えた動的計画法で解いていましたが、これは全く思いつきませんでした。
確かに、考えるべき和の上限が M =3,000 と小さく抑えられているので、動的計画法でメモリに乗り切るということですね。
上限が小さい”ある値を取れるかどうか”問題については、動的計画法が使えそうだということを覚えておいて損はなさそうです。
それでは、また。
/ゴドー
