20190324_ABC122

README

ABC122感想

• A問題は連想配列使ってくださいの問題。
• B問題は全探索を落ち着いて。
• C問題は累積和だが、適当にやってしまったところがある。
  • 半開区間っぽいやり方で書き直したいところがある。
• D問題は行けたと思ったが、サンプルが通らず、最後まで気づけず。
  • 実はサンプルだけでは読み取れない、禁止パターンがあった。
    • AG*C, A*GC
  • 最終的には、自分が当初書いていたものを1次元拡張したものが必要となる。
  • 最後のMOD忘れでデバッグに無限に時間がかかってしまったので、今後は気をつけたい。
    • テンプレに書いておいた。
  • DPに慣れないうちは、遷移を整理するためにしっかりと紙を使いたい。
  • 今回の数え上げの遷移のさせ方も、しっかりと吸収したい。
    • 当初は、加算していくのではなく、乗算しようとしていたので。

---

D問題のDPをやってみて思ったことなど

• はじめから一般化しようとせずに、まずは小規模な例について「DPっぽい解き方での計算方法」を書き出してみる。
  • 紙に書くこと！自分の頭ではまだこのレベルを「暗算」するのは荷が重い。
  • 最大・最小だとちょっと書きづらいのかもしれないが、数え上げならば紙に書き出せるはず。

ニコニコ大百科のとあるコメントの引用

そもそも動的「計画法」という名前は、最終結果はとりあえず置いといて、先に どんな材料があれば答えが出るか決めちゃおう というところから来てる。 一般的に でかい問題は分割統治 して、それぞれ別に作った結果を最後にがっちゃんこするってのがよくあるセオリーなわけだが、それぞれが完全に独立でやっちゃうと部品の共通化ができなくてすげー効率が悪いわけよ。だから元締め側でそこは管理して「これは余所で用意したのと一緒だからそれを使いまわす」という風に車輪の再発明をしないというのがミソなわけだ。 ただ普通の計画と違って 部品を作りながら足りないところを増やしていくから動的だ という言い方をする。

説明の厳密性はともかく、太字にしたあたりは共感する部分があるので、メモしておいた。