ABC118-D
問題
提出したやつ
リアルタイムでやった時は出来なくてpdfで見たのをそのまま覚えてて書いた
紙
pdfの解法まんま写経したので大した事書いてなかった。
考え方
- 動的計画法でdp[i]を「i個のマッチを使ってできる最大の桁数」としてnまで求める
- dpの中で最大になるインデックスをindexMとしてdp[indexM]からdp[0]にたどっていく
- たどっていく経路はdp[i]-dp[i-本数]==1になるやつ
まず桁数考えて次に経路を復元（って言っていいのか？）する筋道自体難しいと思う。
リアルタイムでやった時はdfsで数字を足していってテストケース29中の4でWA。
こんなん絶対intをlongに変えればACするやつやんって。
あと地味にAがソートされずに入ってくるのも引っかかりどころな感じある。
他人のやつ
全員dpでやってるし典型問題っぽい
使用するマッチ棒の本数を{0,2,5,5...}や{1<<29,2,5,5...}のように最初に適当な数字を入れている人が多い。入れないと[i-1]でアクセスすることになるが、入れると-1がいらない。
ただこうするとfor(int i:b)とかするときに除外するのが面倒なので使いどころを選ぶのか。
pdfの方法ではdp配列を使ってもう一回すべてのAの可能性を考えて経路を復元しているが、どの桁数から増えたかを記録するbefore配列,どの数字を作ったかのrev配列を作っている解法が楽そう。
longの最大値より大きい数も扱えるクラス（中身はStringとかint配列とか）とその配列dpを用意してdp[i]にdp[i-本数]にA_iを前に追加したもの、後ろに追加したもの、substringつかってサンドしたもの（これ必要か？）の3つの中の最大値を入れていくって解法もあった。
dfsで解いてるやつもあったけどそれもメモ化して高速化が必要みたい。
あと2次元配列でやってたり訳わからんのあったり色々。
動的計画法だと分かればあとはいろいろな方法が取れるみたい。
