ひとつまえは、AtCoder 練習帳１
Difficulty = 1474, コンテスト中に、わりと惜しいところまでいったような気がして悔しかったやつ。t-1 秒以内に食べきる範囲で、n-1 個で dp して、最後に１個追加すればいいというところまでは着想して、ギリギリ動かしたところで時間切れ。3WA だった。
時間でソートしたつもりが、おいしさでソートしてしまっていた以外にも、 いろいろ問題があって、コンテスト後に書き直そうとしても、なんかよくわかんなかった。
さっき、Sen さんのブログ を参考にしつつ書いたものがこれ： 8526021
時間でソートし、t-1 秒以内で食べられる最大満足度を dp するんだけど、 最後の一個は（dpの時間制約外で）食べ始めたら満足度がいくらになるのかを常に更新していく。 私のコードで、内側ループを昇順にすると、dp の埒外で食べたやつをもう一度カウントしてしまうので、降順に変えた。もしくは、Sen さんのコード のように、dp の更新が過去向きに（時刻が j - A になってる）なるようにする必要がある。
なるほど。
Difficulty = 1158. SAPIX さんすう的： 8419445
あみだくじは互換の積って感じか： 8420238
蟻本を前から読み始めて、BFS はあんまり書いたことないんだよなぁ（DFSは、ごく自然に書けるんだけどなぁ）とおもって、これを： 8323218
基本形になれなきゃと、蟻本みながら書いてみた。 ９月にもこの問題はやっていて、その時の提出 7434888 と、今回のは、 あたりまえだけど、ほぼ同じ。今回のの方が、０オリジン処理を最初にやったので、後半がシンプルになってるかな、程度。
もう覚えたかな。（今日は、９月にどんなの書いたか記憶にも残ってなかった）
C うめていこうとおもって。とくにいうことなし： 8325321
推定 Difficulty 1112 だけど…、普通に書くだけだったような気が： 8264516
推定 Difficulty 1334 …んなわけない気がする。Experimental だからか： 8264997
随分日にちがあいてしまった。
きのうおさらいした、BisectRight をつかった。Left かしら、Right かなとか、検索範囲をどうすんのとか、すこし手元でどたばたしたけど、提出自体はいっぱつ AC で。
DP ... では無理だよなぁ、どうするんだろう？？ くらいで解説を読んでしまって反省。 小さなケースで実際に紙と鉛筆でためす、または、小さいケースを解くDPで様子をみてみるなどしろと。
…はい。あとで解く。
はじめ、試しに、単に素数を前から N 個だしてみて WA（そりゃそうだ）。 つぎに、条件にあうものだけ前から順に追加していく方法をためしてみたが、 解説にあるように N=9 までしか求められなかった。
解説をみて、納得。なるほど。5で割って1あまるものばかり5個の和は、5で割り切れる： 7914215
DP？…メモ化再帰か、ということで、比較的あっさり書けた： 7897867
これも、メモ化再帰のような、DP のような。 あまり頭の中で区別がなくなってきた…。 DP の状態表現を先に考えて、ループで更新するか、それが無理ならメモ化再帰にするかを後で考える感じかもしれない： 7898319
ちなみに、メモ化の際に、計算がまだなことを表す０と、たまたま値が０になるのを区別していないけど、わざとです（無駄な計算をする可能性があるけど、手抜き分はペイするとおもった）。
検索で殴るのでなく、数の性質を使うタイプ。\(k\) が \(A_i\) の最大個約数の倍数で、かつ、\(A_i\) の最大値以下であれば可能： 7856693
部分数列の和がゼロになるケースを数え上げろというもの。 累積和ではTLEだろうなぁと思って、TLE。累積和の同じ値が出現する個数を数えればいいと気づいたのだけど、Dictionary を使って個数を数えようとして、今度はRE。 解説をみて、なるほどと思ったという。我ながら、ニブいなぁ。
累積和の配列をソートすれば、同じ値は固まるのでそれを数えればよかった： 7845589
一応自力で通したが…。 どの範囲で知らべるのがいいのかわからず、lcｍ から N*M の範囲を調べることにした。 最初それではTLE（その前に、おそらく int あふれでエラー）、次に二分探索するようにして AC になったが、ほんとは lcm だけチェックすればよかった： 7846332
簡単だった（difficulty 254 らしいし）。９分： 7804248
これも書くだけ (difficulty 1), 5 分： 7804331
Difficulty 1323. 高橋君が右/上 を目指すシナリオと、左／下を目指すシナリオの２通りをシミュレートして、 いずれかで盤からはみ出たら NO って感じで。すんなり通った： 7804539