judge.u-aizu.ac.jp まず本を読み終わる時間を最短にするには一人目が所要時間の長い順に本を読み、二人目の子供は二冊目から同様に読めば良い。一人目が一冊目を読む間に、二人目が二冊目以降を読み終わらない場合は最適性は明らか。全て読み終わったあとに…

judge.u-aizu.ac.jp 問題を見てすぐにDPっぽいということが分かる。使用した最小金額を値として持つということが自然なので、すぐに思いつく解法としては[店の数]×[500円の数]×[小銭]が考えられる。なので通るかと思い、実装した。色々とバグらせてしまい、…

judge.u-aizu.ac.jp まず問題を見た時点でDPだということが分かる。そして、制約がなので、がくらいになることがわかる。 想定解法はおそらく場合分けしてDPと全探索の二通りの解法で書くんだろうなと予想していて、実際に講評の解法の1個目はそうなっていた…

judge.u-aizu.ac.jp E問題だが、かなりシンプルなメモ化再帰で解ける問題。状態数は任意のサイズの長方形なので、だいたいくらいになって間に合う。実装は30分ほどでできていたのだが、境界をミスしていてデバッグに時間がかかり40分強でAC。 ICPCのD、E問題…

judge.u-aizu.ac.jp 街（この問題ではスタート地点および汚れた床）の間の距離を求めるのにBFSしないといけないので面倒だが、それさえやってしまえばTSPを書くだけの問題。TSPについては停止条件でスタート地点に戻る必要がない点について注意が必要。 実装…

codeforces.com A、B、Cはpretestが通ったが、Cがhackされてしまった。C問題は本当に計算量が大丈夫なのか少し自信がなかったが、WAでhackされていたので不思議に思って確認してみると、iとjを書き間違えている部分があった。なぜprerestに通ってしまったの…

atcoder.jp 僕の知識にムラがあるので正しい難易度判定ができないが、明らかに簡単な回だったと思う。 C問題は最大公約数を求めるだけ。10分くらいでAC。難易度を考えると遅かった（なんとなく昨日のCより簡単すぎたので、本当に最大公約数で良いのか少し考…

judge.u-aizu.ac.jp 単純にメモ化再帰した。コーディングの方針がほぼ確定しているとはいえ、20分くらいで解けたので僕としては及第点としたい。しかしループの範囲を間違えて1WAした。こういうのが良くない。 judge.u-aizu.ac.jp

judge.u-aizu.ac.jp 簡単そうな問題だったので30分くらいで早く実装する練習をしようと思ったが、渦巻きの図を書くことに異常に手間取ってしまった。もう少しバグを生まないように、しっかり考えて描かないといけないと常に思っているのだが、実際にやるのは…

atcoder.jp DPの練習として、必勝法問題の典型問題。ゲームの勝敗の問題はかなり苦手意識がある。 atcoder.jp

atcoder.jp DPの練習をするためにEducational DP Contestの問題を解いた。典型的で簡単な問題らしいが、序盤から僕にとっては難しい問題が多くあった。 その中で、僕からすると簡単ではなかったけれど解けて嬉しかったのがJ問題。確率を求めるようなDPは見る…