【AtCoder】ABC004を解いたのでメモ【Python3】
結果と最終提出コード
解答中の心境
【A】
- 最高によゆー
【B】
- 下手な書き方だけど綺麗に書こうと悩むよりはマシ?
【C】
- すぐに規則性を見つけられた!
【D】
- 解説の方法1を使うことには気づけた
- 解説にもある、『赤を跳ね飛ばす〜』の説明箇所を処理するのに苦労した
- 5つだけどうしても通らないケースがある...なんで...
解説やコメント
【A】
- なし
【B】
- 1次元の配列に入れて逆から取り出せば良かったみたい
【C】
- なし
【D】
- 解法が3つ紹介されている
- 私もやったが、広げ方を考えて最後に集計する
- 動的計画法を計算量が減るように工夫して使う
- 最小費用流を使う
解法1の高速化を詰まることなく実装できたのは良かったが、5つ通らないのは納得いかない!コンテスト終わったらテストケースを公開してくれないかな。笑
動的計画法はちょいちょい聞くが、再帰関数に苦手意識がありすぎて実装できない...。どこかのタイミングで克服しなければ...
費用最小流は私には早そうなのでスルーで!笑
得た知識
- 関数外で宣言した値を関数内で変更するには
global
つけようね!1時間ぐらいハマったよ! - おおまかな計算回数を求めると高速化が必要か判断しやすくなるっぽい
まとめ
- 動的計画法が仲間になりたそうにこっちを見ている。
- 満点は遠かったが部分点取れてるし、落ち込まずやろう。
- AtCoderの中の人に「コンテスト終了後にテストコードを公開しようぜ!」って言えるようにレートガシガシあげなきゃ...笑
追記
AtCoderのテストケースは古すぎないものであれば公開されていました!