[日記] AtCoder 最近解いた問題 (ABC147, ABC146, ABC145)

競技プログラミングの話題を最近身の回りでもよく見るようになってきたので、久々にやっていこうと思い ABC 147 に参加しました。 ICPC2014 ぶりのコンテストリアルタイム参加でしたが、想像よりできなくなってた (２完) のでまた過去問もちびちび解いてリハビリしようと思います…。

ある程度問題を解いたら、復習用のメモも兼ねて、ときどき記事に残していこうかなと思います。青レート相当くらいまで埋めたいな…。

ICPC と比較すると、 ICPC の方が実装難に寄った問題が多かったかなあみたいな印象があります。 AtCoder には「1000000007 で割った余りを表示」とか独特の典型テクがありそうなので、ちょっと慣れが必要かもしれないなあと思いました (AtCoder に限らずだとは思いますが)。

ABC147

5 年ぶりのオンタイム参戦で緊張。でも楽しかった！

ABC147 A Blackjack

３つの数字の合計が２２を越えるか判定する

印象

やるだけ。

解法

足して if 文で分岐するだけ。だったのに、テストせずに投げたら bust をなぜか burst と書いてて WA もらってしまった…w 久々とはいえ緊張しすぎ

ABC147 B Palindrome-philia

文字列が与えられる。その中から好きな文字を選んで、好きな文字に変えることができるとき、最短何手で回文にできるか。

印象

素直に数えるだけ。

解法

入力を受け取ったらとりあえず文字数を取得 (仮に N とする)。 0 <= i < N/2 でループ回して、 i 文字目と N - i 文字目が同じになってるかを調べる。もし違えば、その文字は変えなければならないのでカウント+1。カウントの合計を表示して終わり。

ABC147 C HonestOrUnkind2 [bit全探索]

「正直者」と「不親切な人」が合わせて N < 15 人いる。「正直者」は本当のことしか言わないが、「不親切な人」は本当も嘘も言う。

「i 番目の人いわく、 j 番目の人は (正直 or 不親切)」という形式の証言がいくつか与えられるので、それらの証言と矛盾しない最大の正直者の人数を求める。

印象

日本語が難しかった。混乱して「不親切な人も本当のことを言うことがあっても良いんだから、全員本当のことを言ってるってことじゃだめなの？」とかよくわかんないことを考え始めてしまったのでとりあえず飛ばした。結局時間内には解けず。落ち着き is 大事

解法

(正直者を 1 、不親切な人を 0 とする) 0 と 1 を自由に N 個並べる並べ方は 2^N パターンになるが、 N が 15 以下ということはせいぜい 3 万パターンくらいにしかならない。全探索 (総当たり) で十分間に合う。

配列で管理しても良いが、二進数の性質を利用すると 16 ビットの整数一つで表せてとても楽（「bit 全探索」という名前がついていたらしい）。

それぞれのパターンについて：もし正直者が

• 不親切な人のことを正直だと証言

or

• 正直な人のことを不親切と証言

していたらそのパターンはアウト。不親切な人の証言は全てスルーで ok (本当でも嘘でも矛盾にはならないので)。

矛盾がなかったパターンのうち、正直者の数が一番多かったものが答え。

ABC147 D XorSum4 [ビット演算]

N < 3 * 10^5 個の整数が与えられる。それらの中から適当に 2 つ (重複無し) を選んで Xor を取ることを全通りやったとき、合計はいくつか。

印象

あんまり見ない感じの問題。素直に二重ループすると最大で N^2 = 9 * 10^10 の時間がかかることになるので、無理そう。 Xor の性質 (同じ数字同士を Xor すると消える) を使うんだろうなあということはなんとなく想像できる。 Xor はビットごとの計算なのでうまい方法がありそうだけど、足し算は繰り上がりがあるので厄介だなあ…。

E 問題がむしろ見慣れた感じの問題だったのでそっちを先にやった（結局そっちは難しかった）。後になってみると、筋は悪くなかったのでもう少し粘ってればよかったなと思う。

解法

実は Xor 問題は AtCoder では典型らしい。次出たら正解したい。

上の「印象」はだいたい合っていて、気づけなかった重要ポイントは「足し算もビットごとにできる」こと。たとえば 12 + 25 を (1 + 2) * 10 + (2 + 5) * 1 と桁ごとに分解して計算しても良いわけで、これを二進数でやればビットごとに計算できることになって、 Xor の性質を活かせた。

ここからはビットごとの合計について考える。何ビット目を取り上げても同じことだけど、想像がつきやすいのでとりあえず１ビット目（１の位）の合計について考える。

「奇数と奇数」「偶数と偶数」の Xor を取ると、１ビット目は 0 になる。逆に「奇数と偶数（順不同）」の Xor を取ったときだけ、１ビット目は 1 になる。したがって、「１ビット目の合計」を求めることは、「「奇数と偶数」の組を何組み作れるか」を計算することと同じになる。 N 個のうち k 個が奇数であれば、奇数の選択肢が k、偶数の選択肢が N - k あるのだから、組み合わせは k * (N - k) 通り。

同様に各ビットの合計を求めていって、最後にビットシフトしながら足していけば全ビットの合計が得られる。

ハマりポイント

合計が int に収まらないことは想像できたので合計はちゃんと long long で計算していたが、途中で出てくる (奇数の数) x (偶数の数) すら int をはみ出てしまうことに気づけなかった。

C/C++ の場合、 (long long)num_odds * (1 - num_odds) のように明示的にキャストするか、はじめからビットを数える変数も long long にしておく必要がある。

ABC147 E Balanced Path [DP (bool)]

W (<= 80) x H (<= 80) の大きさの表があって、各マスに２つづつ数 (<= 80) が書いてある。左上のマス (0, 0) からスタートして、それぞれのマスに書かれた２つの数を「赤チーム」「青チーム」に分けながら右下 (W - 1, H - 1) を目指す。どんなルートでもいいが、寄り道（左に戻ったり上に戻ったり）はダメ。最終的な「赤チーム」の合計と「青チーム」の合計の差をなるべく小さくしたいとき、最小でいくつにできるか。

印象

「いかにも DP (メモ化再帰) っぽい」という印象からパッと思いついたダメ解法がこれ：

いつもなるべく偏りが小さくなるように行動していれば最終的な偏りも小さくなるはず。したがって、あるマス (x, y) 時点での最小の偏りは、次の二つのうち小さい方：

- 左隣のマス (x - 1, y) 時点での最小の偏りに、このマスで発生する偏りを加えたもの
- 上隣のマス (x, y - 1) 時点での最小の偏りに、このマスで発生する偏りを加えたもの

関数っぽく書けば、こんな感じの再帰構造になっているはず：

    // ans(x, y)  = マス (x, y) 時点での最小の偏り
    // diff[x][y] = マス (x, y) に書かれた二つの数字の差
    ans(x, y) = min(
        abs(ans(x - 1, y) - diff[x][y]),
        abs(ans(x, y - 1) - diff[x][y])
    )

ans(<右下のマス>) を計算すればそれが答え。 x, y の組み合わせがたかだか 80 x 80 = 6400 程度しかないから、メモ化してあげれば計算量的にも楽勝。

これだと答えが合わない。極端な例を挙げれば、たとえば最後のマスに書かれた二つの数が 0 80 だった場合、それまでどんなに偏りがないように進んできたとしても、このマスだけいきなり 80 の偏りができてしまう。むしろ直前にぴったり 80 だけ偏っていれば、このマスの偏りで帳消しになって 0 になる。つまり、大前提の「いつもなるべく偏りが小さくなるように行動していれば最終的な偏りも小さくなるはず」が間違っている。

これで行けるはずと思ってがっつり実装してしまっていたので、コネコネいじくりながらデバッグしてるうちにコンテスト時間終了。

解法

マスの数が不自然に少ない (最大 80 x 80) ことをもう少し気にするべきだった。 DP なのは合っていたが、このマス数ならさらに次元を一つ増やすことができた。

書かれている数の最大が 80 ということで、ひとマスで生じる偏りの最大も 80。寄り道は禁止なので、左上から右下まで進む間に通るマスの数は最大で 80 + 80 = 160 くらい。これらを掛けると、スタートからゴールまでどんなに目一杯偏らせながら歩いても、偏りは最大で 160 * 80 = 12800 程度。この程度なら、それぞれの偏りについて総当たりで「結果がこの偏りになるようなルートはあるか」を調べることができる。

これも同じように再帰的な構造を持っていて、「マス (x, y) 時点で偏りをちょうど d にすることができるかどうか」を reachable(x, y, d) とすると

reachable(x, y, d) = reachable(x - 1, y,     abs(d - diff[x][y]))
                  || reachable(x - 1, y,         d + diff[x][y] )
                  || reachable(x,     y - 1, abs(d - diff[x][y]))
                  || reachable(x,     y + 1,     d + diff[x][y] )

となる。x, y の組み合わせが 6400 通り、 d の最大が 12800 なので、掛けると起こりうる全パターンで 81280000 = 8 * 10^7 くらい。ちゃんと DP (メモ化) すればギリいける。 reachable(<右下のマス>, d) が true になるような d のうち、一番小さいものが答え。

ダイクストラの状態を増やすやつは経験があったけど、 DP はそういえばなかったので思いつけなかった。「具体的な値を返す DP」 → 「具体的な値それぞれについて、それが可能かどうかを持つ DP」と次元を増やすのは今後も出てきそうなので次は解きたい。

ABC146

ここからは過去問。

ABC146 A Can't Wait for Holiday

曜日が与えられるので、次の日曜日までの日数を答える。

印象

やるだけ

解法

文字列を読み込んで if 文で分岐するだけ。

ABC146 B ROT N

整数 N とアルファベットの文字列が与えられるので、文字列の各文字を N だけズラして出力する。ただし Z までいったら A に戻る。

印象

やるだけ

解法

整数 N を読み込んだら、あとは一文字読むたびに：

• ASCII コードを元に何番目のアルファベットかを計算 (ch - 'A')
• そこに N を足してから、アルファベットの文字数である 26 で割った余りを取る
• ASCII コードに戻して出力 (ch + 'A')

を繰り返す。

ABC146 C Buying an Integer [二分探索/全探索]

1 〜 10^9 の整数を売っている整数屋さんがあって、整数 n を n * a + <nの桁数> * b (a, b <= 10^9) 円で買うことができる。
x <= 10^18 円持っている人がこのお店で買える最大の整数はなにか。ただし、ひとつも買えない場合もある。

印象

登場人物がみんな 10^9 スケールなので、数自体に対する総当たりは無理そう。

条件に <nの桁数> * bがあるのがだるい。もし条件が n * a <= x だけだったら、 n <= x / a なので一発だなあ。

桁数が 1〜9 桁のどれかしかないので、総当たりすればよさそう。

解法

だいたい印象通り。

桁数 d について 9 >= d >= 1 でループ回して：

• (x - b * d) / a (小数点以下は切り捨て) を計算する
• もしマイナスになってしまったら、 d 桁の整数はひとつも買えない
• もし d 桁より大きい数になったら、 d 桁の整数はもはやなんでも買えるので、一番大きいやつが答え
• もしその間に収まったら、その整数が答え

後で気づいたこと

n * a + <nの桁数> * b は n について単調 (n が大きくなれば値段も上がる) なので、普通に二分探索でいけた。そっちが想定解法な気がする。

ABC146 D Coloring Edges on Tree [DFS/BFS]

N <= 10^5 個の頂点と、それらを結ぶ N - 1 本の辺が与えられる。これらは必ず木になるように与えられる (すなわち、ループしない)。
これから全ての辺に色を塗っていきたいが、同じ頂点に同じ色の辺が2本以上つながることはないようにしたい。最小で何色必要か。またその時の塗り方の例をひとつ示せ。

印象

「木になる」がミソっぽい。ちゃんとデータ構造を作れば、塗りながら掘ってくだけで (DFSでもBFSでも) 行けそうだけど実装めんどくさいな…。

サンプルを見てると

各頂点について「使用済みの色リスト」を持って、「辺が与えられるたびに、その辺の両端のノードどちらでも使われていない、一番小さい番号の色を塗る」

でもいけそうだなあ → テストケースにはちゃんとダメなケースが入っていて WA。

解法

データ構造を作って塗りながら掘っていくで正解。横着しちゃダメ。

入力を読み込んでしかるべきデータ構造 (後述) を作ったら、適当なノードを選んでそこから出発。そのノードから生えてる各辺について、それぞれバラバラの色を塗って再帰。再帰先では直前に使った色をスキップしなければいけないことに注意。ループはないと言われているので、直前の１色だけを覚えておけば OK。

しかるべきデータ構造について。入力を素直に「辺の配列」で管理してしまうと、「ある頂点から生えてる辺の一覧」を得るのに毎回 N - 1 の時間がかかってしまうのでダメ。各頂点について「その頂点から生えている辺のリスト」を並べた、二次元配列のようなものを作るのが正解。ただしこの二次元配列はかなりスカスカになるので、内側は線形リストなど動的なデータ構造にしておかないとメモリが足りなくなる。

ABC146 E Rem of Sum is Num [累積和の除余]

N <= 2 * 10^5 個の整数が与えられる。この部分列のうち、総和を K < 10^9 で割った余りが要素数に一致するようなものはいくつあるか。

印象

「部分列」でパッと思いつくのはしゃくとりと累積和。

しゃくとりは「割った余り」が単調じゃないので厳しそう。

しかし累積和にしても、 N <= 2 * 10^5 なので総当たりはできない。うーん。

解法

累積和の除余も典型問題だったらしい。

catupper さんの配信アーカイブを見たけど、「部分列の除余」を見た時点でとりあえず式を立ててみて、ごにょごにょ移項したりしてるうちに答えが見えたみたいな感じだった。次は解きたい…。

とりあえず累積和を取ってみる。すなわち、

{A[i]} = 1 2 3 4 ...

のような数列から

{A[i]} =   1 2 3  4 ...
{S[i]} = 0 1 3 6 10 ...

のような数列 S を作る。と、 A[i] から A[j] までの総和 が S[j] - S[i-1] で簡単に求められる。ここまでは普通の累積和。

これを使うと、問題文の条件

「 A[i] から A[j] までの和を K で割った余り が A[i] から A[j] までの要素数 と一致する」

を簡単な式で書き下すことができる。

(S[j] - S[i-1]) % K = j - i + 1

言い換えれば

j - i + 1 < K
S[j] - S[i-1] = j - i + 1 (mod K)

これを満たすような i, j の組が何組あるかが求まれば、それが答え。

下の式を辺々移項すると

j - i + 1 < K
S[j] - j = S[i-1] - (i - 1)　(mod K)

i の取り方をずらせば

j - i < K
S[j] - j = S[i] - i (mod K)

となって方針が見えてくる。

この条件を満たすような i, j の組が何組あるかを求めるためには、以下の数列

{S[i] - i} = 0 0 1 3 6 ...

の中に、 K で割った余りが一致するようなペアがいくつあるかを (j - i < K に気をつけながら) 数え上げればよい。もっと言えば、たとえば K が具体的に 2 だとわかっていれば、たんに以下の数列

{T[i]} = {(S[i] - i) % 2} = 0 0 1 1 0 ...

の中に同じ値のペアが何組あるかを (j - i < K に気をつけながら) 数え上げればよい。プログラム的には：

res = 0 として、 0 <= i <= N でループ回しながら

1. (もし i >= K なら) T[i - K] の登場回数カウントをマイナス１
2. T[i] の登場回数カウントを res に足しこむ
3. T[i] の登場回数カウントをプラス１

で数え上げられる。 1. の操作は j - i < K の条件を満たすために必要。ただし、数列 T に出現しうる値の最大値である K - 1 がかなりでかいので、登場回数カウンタには効率のいいデータ構造 (hashmap とか) を選ぶ必要があることに注意。

別の発想方法

みんなどうやってこれ思いつくんだろうなあと思って色々ブログを漁っていたら、別の考え方から辿り着いている人もいた。

「 A[i], A[i+1], ... A[i+m-1]」の m 個の数を合計した除余が m になる、という条件は、各要素からあらかじめ 1 を引いておけば「除余が 0 になる（割り切れる）」と同じ。

{A[i] - 1} = 0 1 2 3 ...

累積和取って

{A[i] - 1} =   0 1 2 3 ...
    {S[i]} = 0 0 1 3 6 ... 

合計が割り切れるということは

S[j] - S[i-1] = 0 (mod K)

移項して i の取り方をずらせば

S[j] = S[i] (mod K)

となって、やはり数列

{Ti} = {S[i] % K} = 0 0 1 1 0 ...

から同じ値のペアを数える問題に帰着した。

ABC146 F Sugoroku [貪欲]

N + 1 個のマスが一直線に並んだすごろくがある。マス 0 からスタートして、 M 面ダイスを振りながら進み、マス N にぴったり到着したい。ただし、マスのうちいくつかは即死マスになっている。最短手数でゴールするには、どんな順でダイスの目を出せば良いか。ただし、複数パターンある場合は、辞書順で一番小さいもの (例: 321 よりは 123 が小さい) を出せ。

印象

貪欲 (即死しない範囲でなるべくたくさん進む) でいけそう。辞書順で一番小さいものなので、ゴールからスタートに向かって進んでいけばいいかな。

解法

印象通り。ゴールからスタートして、即死マスを踏まない範囲でなるべくたくさん進めば正解。

これが辞書順最小になることは、ちゃんと証明しようとすると実は難しいらしい。けど、あってたのでとりあえず ok。

ABC145

ABC145 A Circle

半径 r が与えられるので、この円の面積が「半径 1 の円」の面積の何倍になるかを求める。

印象

円の面積は r * r * PI。 * PI は打ち消しあうので、たんに２乗すればよさそう。

解法

印象通り。数を読み込んで、二乗して表示するだけ。

ABC146 B Echo

文字列が与えられるので、この文字列が同じ文字列を二回繰り返したもの (hogehoge など) になっているかを判定する。

印象

やるだけ

解法

文字数が奇数だったらまずダメなので No と言って終了。

0 < i < N / 2 についてループ回して、 i 番目の文字と N / 2 + i 番目の文字が違う文字だったらダメなので No と言って終了。最後まで生き延びたら Yes と言う。

ABC146 C Average Length [順列]

N <= 8 個の点の座標が与えられる。これらの点を好きな順に訪問するとルートは N! 通りになるが、全ルートの平均距離はいくらか。

印象

どの頂点も対等な関係にあるので、結果は Σほげほげ / N みたいな格好になりそうだなあ。全通り列挙した時、それぞれの辺が何回登場するかがわかれば良さそう。

解法

印象通りの方法で効率よく解ける。が、 N がたかだか 8 以下なので、全通り計算して素直に平均を取っても実は間に合った。制約をよく見よう。

効率よく解く方法はこんな感じ：

ある１つのルート中に踏破する辺の数は N - 1 本なので、 N! 通りすべてのルートを歩くと、トータルで踏破する辺は全部で (N - 1) * N! 本。これをルートの本数である N! で割ったものが求めたい平均。

ところで、たとえば 点A → B, B → A を同じ辺とみなすと、辺は全部で N C 2 = N * (N - 1) / 2 種類ある。全ルートを踏破すると辺が全部で (N - 1) * N! 回登場することがわかっていたが、どの頂点も対等な関係にあるということは、きっとこの N * (N - 1) / 2 種類の辺は均等に登場するはず。したがって同じ辺が何回登場するかは割り算で求まる： {(N - 1) * N!} / {N * (N - 1) / 2} = 2 * (N - 1)!。つまり、それぞれの辺の長さを 2 * (N - 1)! 倍しながら合計すると、全ルートを踏破した時の合計距離が求まる。が、これは相当大きな数になってしまう。

求めたかったのはルート全体の距離の平均だったので、合計距離を計算してからまとめて N! で割るかわりに、毎回 N! で割りながら足していってもよい。よって、それぞれの辺の長さを 2 * (N - 1)! / N! = 2 / N 倍しながら合計していったものが答え。

ABC146 D Knight [全探索/二項係数]

巨大なチェス盤の左上 (0, 0) にナイトが立っている。ナイトは「右に２・下に１」動くか、「右に１・下に２」動くことができる。マス (x, y) (x, y <= 10^6) にたどり着く方法は何通りあるか。

印象

10^6 なので縦方向・横方向どちらか片方だけなら総当たりできる。二重ループは無理。

横方向だけ考えれば縦方向は勝手に決まるとかそんな感じがする。

解法

だいたい印象通り。

たとえば右に 5 マス移動するには、

1. 「右に２」を２回、「右に１」を１回の計３手
2. 「右に２」を１回、「右に１」を３回の計４手
3. 「右に２」を使わず、「右に１」を５回の計５手

の３種類のパターンが考えられる。このとき、下に何マス進むかはパターンごとに自動で決まってしまう。

1. 「右に２」を２回、「右に１」を１回 → 下には４マス進む
2. 「右に２」を１回、「右に１」を３回 → 下には７マス進む
3. 「右に２」を使わず、「右に１」を５回 → 下には１０マス進む

たとえば (5, 10) に行きたければ 3 のパターンを選ぶしかないし、 (5, 5) にはどうあがいても行くことができない。

そこで、まずは目的地 (x, y) にたどり着くための「パターン」を探す。

0 < i < x / 2 についてループを回して、「「右に２」を i 回使うパターンでは目的地にたどり着けるか？」を確認していく。たどりつけるパターンがなければ 0 通りと言って終了。

パターンが見つかっても、これはそのまま答えにはならない。たとえば「「右に２」を２回、「右に１」を１回」のパターンに決めたとしても、経路としては

• 2 -> 2 -> 1
• 2 -> 1 -> 2
• 1 -> 2 -> 2

の三通りが考えられる。一般に、「右に２」を使う回数を i とすると「右に１」を使う回数は勝手に x - 2 * i と決まるので、合計の手数は i + (x - 2 * i) = x - i になる。 x - i 手のうち i 回「右に２」すればいいので、 (x - i) C i が求める経路の本数になる。一般に

n C r = { n * (n - 1) * ... * (r + 1) } / { r * (r - 1) * ... 1 }

だが、 x, y <= 10^6 なのでこの値は結構ヤバい大きさになる。ので、 1000000007 で割った余りが要求されている。掛け算は簡単で、たんに

res = (res * i) % 1000000007

のように掛け算の結果に対して % 1000000007 してやればよいが、割り算はそうはいかないくて、これがめっっちゃ難しい。

1000000007 は素数なのでフェルマーの小定理より

x ^ (1000000007 - 1) = 1 [mod 1000000007]

両辺 x ^ (-1) を掛けて

x ^ (1000000007 - 2) = x ^ (-1) [mod 1000000007]

が言えるので、

// modpow(n, m) は n^m を 1000000007 で割った余り
res = (res * modpow(i, 1000000007 - 2)) % 1000000007

とすれば res / i を計算したことになる。これは完全に知識ゲーだしライブラリ化してしまってもいいかも…。

ABC146 E All-you-can-eat [両側からDP/ソートしてDP]

N <= 3000 種類の料理があって、それぞれの料理に「美味しさ」と「食べ終わるまでの時間」が決まっている。 T <= 3000 分だけ時間が与えられた時、美味しさの合計が一番大きくなるように食べるといくらになるか。ただしラストオーダーの時刻である T - 1 分までに頼んだ料理は、制限時間を越えても食べ切ってよい。

印象

いかにもナップサックだけどラストオーダーで一捻り入ってる。

「ラストオーダーで頼む料理を一つ決め打ちしてナップサック」を各料理についてやって、最大を探せばいけそうだけど、３乗オーダーになってくるので計算量的にきつそう。

どうせラストオーダーで一番時間のかかる料理を食べることになりそうなので、料理を所要時間順にソートして、所要時間の小さい料理からナップサックすればいけそう。

解法

だいたい印象通り。ラストオーダーで一番時間のかかる料理を食べるパターンだけを考えれば十分：なぜなら、ラストオーダーにすぐ食べ終わる料理を選ぶパターンは、並べ替えればラストオーダーに一番時間のかかる料理を食べるパターンに変形できる。しかし、逆はできない。

所用時間の短い順に食べていけばよいということがわかれば、順序を考慮する必要がなくなるのでただのナップサック問題になる。料理を所要時間順にソートしてから、以下の DP (メモ化再帰) をすれば ok：

// max_umami(t, n) ... 時間 t の間に 1 ~ n 番までの料理から得られる最大のうまみ
// time[n] ... n 番目の料理を食べるのにかかる時間 (t = T の場合だけ 1 として扱う)
// umami[n] ... n 番目の料理のうまみ
max_umami(n, t) = max(
    // n 番目の料理を食べる場合
    // → 時間 t のうち time[n] は n 番目の料理に使うので、残りの時間で 1 ~ n-1 番目の料理を食う
    umami[n] + max_umami(t - time[n], n - 1),
    // n 番目の料理を食べない場合
    // → 時間 t をすべて 1 ~ n-1 番目の料理に使って良い
    max_umami(t, n - 1)
)

ラストオーダーの時刻 T - 1 に注文する料理は特別に１分で食べきれることにしてしまえば、 max_umami(N, T) が答えになる。 N * T <= 9000000 なので十分間に合う。

別解

解説を見てみたら別の方法で解いていて、それはそれで面白そうだった（というか応用が利きそうだった）のでそっちでも解いてみた。

もともとの「印象」にあった

「ラストオーダーで頼む料理を一つ決め打ちしてナップサック」を各料理についてやって、最大を探せばいけそうだけど、３乗オーダーになってくるので計算量的にきつそう。

この方針も実は、以下のようにやれば２乗オーダーに収まった：

• 「時間 t の間に 1 ~ n 番目までの料理を食う」通常の DP (dp1 とする) に加えて、「時間 t の間に n ~ N 番目までの料理を食う」逆向きの DP も作っておく (dp2)

すると、各 1 <= n <= N, 1 <= t <= T-1 について、「 n 番目の料理をラストオーダーに取っておくことにして、 t の時間を 1 ~ n-1 番目の料理に、残りの時間を n+1 ~ N 番目の料理に使った場合のベストうまみ」が以下のように一発で求まる。

umami[n] + dp1(t, n - 1) + dp2(T - 1 - t, n + 1)

これのうち最大のものが求める答え。「アイテムを１つだけ飛ばすことができる」ような DP で一般に使えるっぽいので、頭の片隅に置いておくと良さそう。