Codeforces Round #626 (Div. 1, based on Moscow Open Olympiad in Informatics)

　A, Cの二完でレートが上がった。Div. 1回でレートが上がるのは嬉しい。

コンテストへのリンク

A. Unusual Competitions

　カッコ列に関する問題。結局、")"と"("の個数が同じときは、")"のとき-1、"("のとき+1としたときの累積和が負になっている部分の長さを足せば良いのだけど、これが最小かはちょっと悩むところな気がする。

B. Present

　AtCoderのTwo Sequencesとほぼ同じ問題だった。

　この問題は、PyPyだと制限時間が厳しいため苦労して解いたことをよく覚えている……のだけど、コンテスト中は全く思い出せなかったし、復習時も解法を思い出せなかった（AtCoderの公式解説を読み返せば分かったが）。うーん……。

・xor→桁ごとに考える

　というのは良いとして、その後が難しい。

　「和を取ったとき、ビットが立っている個数」を各桁について求めれば良いのだが、繰り上がりがあるので、その桁だけ見ているのでは分からない。「その桁以下の桁」を見て実際に和を取らなくてはいけない。

　そうすると、結局O($n^2$)かかってしまいそうなのだが、実は、二分探索を使って求めることができる。

　たとえば、四桁目を考えたとき、0000～1111までの二つの和は、0000～11110の範囲に収まるので、四桁目が1になるのは、1000～1111か、11000～11111の二つの範囲になる。

　和がその二つの範囲に入るindexを二分探索で求めれば良い。なお、PyPyだとそれではTLEになる（と思う）が、二分探索ではなく尺取りを使えば間に合う。

C. Instant Noodles

　問題設定は複雑だけど、内容を正しく把握すると、ユークリッドの互除法が分かっていますか？　という問題になる。

　なお、コンテスト中は、Counter[tuple()]という書き方をしたらTLEしたので、Counter[hash(tuple())]という風に書いてACしたのだけど、普通に、dict[tuple()]という書き方でACできた模様。

　中に入れるものによっては、Counter()とdict()で時間に差がつくのですね。気を付けよう。

D. Reality Show

　公式解説を読んでAC。

　検索しても日本語での解説が出てこなかったので、さらっと解説を書きます。

（問題概要。制約は書いていませんが、二乗が通りそうな制約です）

　n人の人が順に並んでおり、それぞれにA[i]（aggressiveness）と、C[i]（cost）という整数が与えられている。index順にその人々を選ぶか、選ばないかを選択する。ただし、選ぶ場合は、A[i]の値が、今まで選んだ人の最小値より小さくなくてはならない。

　各人を選んだ時に、コストと利益が発生する。コストはC[i]、利益はaggressivenessの値によって決まり、aの人を選んだ時、P[a]である。（Pは負の値も取る）

　ただし、aggressiveness aの人が二人以上いた場合、そのうちの二人は戦い、残った一人のaggressivenessがa+1になる。この際、さらに利益がP[a+1]加算される。

　利益 - コストを最大にするような選び方をしたときの利益 - コストの値を求める。

（解説と雑感）

　公式解説でもある通り、まず、

・同じaggressivenessの人達を選んだなら、どのような順番に選んだとしても利益は同じになる

　ことに気付くのがポイント。

　設定が複雑なため分かりにくいけど、これは当たり前。
　人が二人で戦う、というイメージではなく、値aのスライム二匹合成されると、a+1のスライムになる、というイメージで捉えると納得しやすいと思う。
（今後、人ではなくスライムと書くことにします）

　このとき、indexを後ろから（aggressivenessの小さい方から）見ようと考えるのはまあ自然。そうすると、aggressiveness aのものを選んだら、今後a未満のものを考えなくてよくなる。

　ただ、こう考えても、今までのスライムたちがどう合成され、どんなaggressivenessのスライムが残っているか、を一々考えていては大変。

　だが、順番を変えても同じならば、一々合成させずとも、そのaggressivenessのスライムの個数さえ分かっていれば良い、と気付くのがもう一つのポイント。

　つまり、

・DP[k][cnt] = Aのmaxがkで, そういうスライムがcnt匹いるときの利益 - costの最大値

　としておいて、この値が更新されたときに、そのスライムを合成させたときを考えて、DP[k+1][cnt/2]などの値を更新していけば良い。（※）

　計算時間ですが、今見ているスライムのaggressivenessがaのとき、a+1の部分の更新ヶ所は1/2、次の箇所は1/4……なので、（更新順番を工夫すれば？）大体二乗になるようです。

　ただ、（※）を毎回行った自分の提出でもACできてしまいました。三乗でTLEになるだろうと思って投げたのですが。
　更新箇所がそれほど多くないので、三乗（のはず）の書き方をしても通ることが多いのかも？

　Div. 1のDということで身構えてしまうけど、解説を読むと意外と素直な問題でした。とはいえ、自力ACできるか、と言われると厳しそう。そもそも、コンテスト中にDを読みにいこうとはなかなか思えないですが……。