Yukicoder 246 No.1045
https://yukicoder.me/submissions/475888
bitDP
269行目の、上にブロックが積めない場合は自分を一個積むという選択肢を忘れており、沼にはまった。涙
参考
https://qiita.com/drken/items/7c6ff2aa4d8fce1c9361
https://drken1215.hatenablog.com/entry/2019/12/14/171657
ABC 165 E
https://atcoder.jp/contests/abc165/submissions/12807838
Nが奇数の時は思いついたが、偶数の時の具体的な配置が思いつかず死亡。
部屋に割り振る数字の差が各部屋で異なれば、N回試合を行ったときに同じペアになることはないことがアルゴリズムの方針。
ABC 166 E
https://atcoder.jp/contests/abc166/submissions/12807122
i,jの組み合わせを分離できることに気づかず死亡。こういう組み合わせの問題はまずi, jを分離できるか考えて、計算量を$O(N^2)$から$O(N) or O(NlogN)$にすることを考えるべきかもしれない。反省。
ちなみに$i - A_i$ = $j + A_j$が成り立つときは$i-j = A_i + A_j$となり、右辺は正なので、自動的に$i>j$となって$|i-j| = i-j$と条件を満たすことに注意。
ABC 158 E
https://atcoder.jp/contests/abc158/submissions/12812035
文字列の中から連続する部分列を持ってこいって問題は、左(or右)からずっと連続した部分列に対して満たしたい性質を計算して、あとでその部分列同士を引き算することで、文字列中の任意の部分列を表現できる。
他にも類題あった気がしたけど忘れた。
ABC 155 D
https://atcoder.jp/contests/abc155/submissions/12826731
配列のindexではなく、値による二分探索。配列の要素ではなく値のため、同じ値が複数生じうるが、「K番目」を「K個以上」みたいに言い換えると大丈夫。
253-256行目の、マイナスの数のint型の切り捨てを勘違いしていた・・・
めぐる式二分探索えらいわ
参考 2分探索
https://qiita.com/drken/items/97e37dd6143e33a64c8c
ABC 155 E
正解
https://atcoder.jp/contests/abc155/submissions/12847218
間違え
https://atcoder.jp/contests/abc155/submissions/12844271
当初は、上の桁から考えてやった。例えば56円の時は100-505 + 10 - 14の方が105 + 10 - 14よりも少ないから、そこの打ち消しあいをどうにかしようという考えでやったんだけど。実は6455みたいな5が連続すると成り立たないみたいなことがあって、間違ったアルゴリズムの間違いが複雑骨折してて、例外を見つけるのにすごい時間を使った。
以下のサイトを見てフムフムとなった。
https://yamakasa.net/atcoder-abc-155-e/
ABC 61 D
https://atcoder.jp/contests/abc061/submissions/12950851
Bellman Ford法で解ける。注意しないといけないのは、スタートからたどり着ける負の閉ループが存在したとしても、スタートとゴールの間に閉ループがなければinfとはならないこと。
ABC 137 E
https://atcoder.jp/contests/abc137/submissions/13009451
Bellman Ford法の始点・終点に関係ない場合閉ループが存在した場合、それを排除する方法が難しい。ABC 61 Dと同じようにやったらエラーして、もっと2*V回くらいループを余分に回すと検出できた。
また、after_contestに追加されたテストケースは一生通せる気がしないからあきらめる。
ABC 167 E
https://atcoder.jp/contests/abc167/submissions/13111580
参考書は何冊でも選べると勘違いして死亡。選ぶか選ばないしか選択肢ないんかーい。つら
Yukicoder 248 C
https://yukicoder.me/submissions/482724
UnionFindをちゃんと理解できていなかったからできなかった。いい勉強になる。
root関数の中で、縮約するか否かは問題のせってアップに応じて変えた方がいいんだね
JOI 2014 予選 5
https://atcoder.jp/contests/joi2014yo/submissions/13273263
JOI 2016 予選 5
https://atcoder.jp/contests/joi2016yo/submissions/13274558
ダイクストラ法を使うためのグラフをどのように構築するかがポイント。
Yukicoder 1060
https://yukicoder.me/submissions/486457
$x^2 - (S-x)^2 = Sx - S(S-x)$という変形天才か。。。
こういうパズル系の問題ってどうやったら解けるようになるの？？？
ABC 168 E
https://atcoder.jp/contests/abc168/submissions/13617024
ベクトルの内積を利用する。2つのデータがあるときのbinary_searchがあまりわかっていなかったのと、データの処理にパニクッた。