今日解いた競プロの問題。

ABC271

A: こういうのは"0123456789ABCDEF"みたいな文字列を用意しておくと実装しやすい。

B: やるだけ

C: 重複巻は売るだけ得なので、数だけ数えておく。他はstd::setにぶちこむ。1巻から順にないと意味がないので、重複巻→後ろの巻、の優先順位で売って次の巻の資金源にする。後ろからとっていくのと次の巻を買うのがぶつかったら終わり。

D: dpして復元するだけ。復元パートで配列の範囲外参照に気付かず時間を溶かした。引き算出てきたら負数の可能性が出るの当たり前だね…

---

昨日解いた問題(第4回ドワンゴからの挑戦状 予選-C)の解説解法を読み直した。「順序が固定されている場合のパターン数を前計算」「グループ化して計算」という大雑把な理解は合っていた。が、前計算の方法があまりにも頭良すぎてハゲた。

求めたいのはある和をもつ広義単調増加(単調非減少)数列のパターン数なわけだが、dp[i][j]:=(長さiで総和jの単調非減少列の数)と置いて

• dp[i+1][j]+=dp[i][j]
• dp[i][j+i]+=dp[i][j]

と遷移する。これはそれぞれ「前に数値0を追加」「全体に1を足す」に相当する。この簡単な遷移だけで全て網羅出来てしまうのだ。あまりにも美しい。

単調非減少列のグラフの形をなぞると割と自明だったりもする。原点から始めて、格子点上を上か右のみに移動する軌跡にちょうど対応するのだ。右への移動と上への移動の2通りだけの枝分かれがあるので、dpの遷移も同じような形になる。

もう一つ、この解説解法だと非常に動作が速かった。自分が自力で書いたTLギリギリの解法とオーダー表記では違わないはずなのにだ。定数倍が非常に軽いのは間違いないのだが、それだけで説明できるかというと怪しい。

自力解法の計算量は正真正銘$O(N(\sum killB)^2 + M(\sum killA)^2)$だ。しかし解説解法の方は、グループ化しているので実は違う。すべてのメンバーのキル数が異なる場合、グループ数は最大100個になりそうだが、キル数の総和が1000以下であるという制約がある以上そのようなことはあり得ない。ちゃんと計算してみると実は最大40ちょっとにしかならないのだ。

したがって解説解法は正確には$O(N+M+\min(\sqrt{\sum killB}, N)(\sum killB)^2+\min(\sqrt{\sum killA}, M)(\sum killA)^2)$になる。

---

明日はU-22プロコンの事前審査の合否が出るらしい。事前審査ということは最低限の作品としての条件を満たす、くらいの意味合いなのだろうか？それとももうちょっと厳しく「最初の関門」くらいのイメージなのだろうか？いずれにせよ今から出来ることはないので胡坐をかいて待っておく。お祈りみたいなのを信じる性ではない。