README
¶
ABC146 感想
- Aはmapを使った。多分if文よりもこっちのほうがタイプ数は少ない。
- Bは復習の余地あり。剰余算を使うべきだった。
- Cは二分探索は一瞬で思いつくが、問題をよく読んでいないのが非常にダメ。
- 今回のFや以前のこどふぉでもそうだったが、最近制約の見逃しが多すぎるので大反省。
- Dは少し悩んだが、最終的にかなりきれいな実装に鳴ったと思う。
- 螺旋本の流儀が若干使えたように思える。
- Eは難しくて本番では全く解けず。
- 復習内容にもよるが、zero sum rangesももう一度見直したほうが良いかもしれない。
- Fは貪欲でやる方法も思いついたかもしれないが、基本的には理解できていないので、復習がみっちりと必要。
- しかしながらこれも制約の見逃しがあったので、問題に立ち向かう以前の問題。
maspyさんのツイート
貪欲の正当性の証明としては、
・先進性を示す。任意の"時点"で最適な方法であることを、"時系列"順に示す。 ・最適解に仮定できる性質を課していく（2つ入れ替えても悪くならないのでこの形etc）と、貪欲になることを示す
などが代表的なテンプレ。
E問題の復習（@2020-01-25）
解答PDFの内容は理解できたが、 もう少し自然な発想方法と添字がややこしい部分をもう少し整理する方法が知りたいため、 解説放送も併用。
解説放送より
「連続する部分列であって、総和を K で割ったあまりが 0 であるようなものの個数を求めよ」
というのがより簡単な典型問題としてあり、その解き方を習得しておくことが重要。
※Zero-Sum Rangesはこれよりも更に簡単な問題（合同式ですらないので）
これは累積和を S とすると S[j] - S[i] = 0 mod K から S[j] = S[i] mod K というのは、
とても簡単かつ自然に導出できる。
そしてこれは S[i] mod K の値の分布を管理しつつ、区間ごとに処理すれば1スキャンで求められる。
これを事前知識として持っておければ、解答PDFの思考は非常に自然に見える。
逆に、解説放送ですぬけさんのやっている、あらかじめ全要素を -1 する（長さをゼロにしている？）
という方がトリッキーに見える（補題の実装がそのまま使えるので、実装は楽そうだが）。
実装に関しては、「これまでの分布（注目中のインデックスを区間の終点とみて数える）」ほうがシンプルかもしれない。 すぬけさんはqueueを併用して実装していた。 すなわち、「queueの中に入っているものが辞書で管理されているもの」というように考えている。
（エッセンスとしては）移項を行うといい感じの問題になる、というところ。 解答PDFのやり方ならば、同じ添字をそれぞれ左辺・右辺に集める、という感じ。
あと、放送のコメントで良さげな物があった。
「等しい」がむずい時に「差が0」に帰着できないか、 「差が0」がむずい時に「等しい」に帰着できないか、っていうのは結構よく考える事が多いと思う。
結局は言い換え、思考の転換みたいなことだと思う。
F問題の復習（@2020-01-25）
ダイクストラの辞書順最小の経路復元と同じく、後ろからDPをする必要がある。
すなわち、各マスに対して、ゴールまでの最短手順をメモしたテーブルを作る。 そして、前からゴールへの最短手順で矛盾なくすすめる複数マス目の選択肢から、 辞書順最小となるように選んでいく。
この手順を振り返ると、後ろから貪欲に大股で歩く方法でもいいことはわかる。
典型: ゴールから考える。
典型: 後ろからDP。
この抽象化は微妙な気がするので、辞書順最小の経路復元の方法として覚えておく。
Directories