Re:AtCoderで青色になるまでにやった事とかをまとめる

前回までのあらすじ

1.この記事を参考にして水色になりました。

2.この記事を参考にして青色になりました。

3.この記事を参考にしたら水色に戻りました。

はじめに

こんにちは。7/1のARC100で無事青色に戻る事ができました。やったー！
流石に二回連続でクソ記事を生成するのも良くないので、この記事ではARC100の参加記と考察を書きます。

記録

ARC100では176位でパフォ2086、レートは1544から70上がって1614(highest)になりました。
CEの2完で1000点、提出情報はこんな感じです。

Submission #2775185 - AtCoder Regular Contest 100
Submission #2775990 - AtCoder Regular Contest 100

コンテスト中の経過

コンテスト開始と同時にCを読みました。問題文が難しかったので理解するまでに3分ぐらいかかってしまいました。
でも解法はよくわかりませんでした…

ちょっと考えてbの値を決めた時の悲しさの値のグラフが凹のような形になる事は分かったのですが、そのような問題を解くのに便利な三分探索のライブラリを持っていませんでした かなしいね
検索をかけて調べてもコードがそのまま載っているサイトは(検索上位の数ページでは)無かったし、自分で書くとバグらせそうなので諦めました ここまでで約10分(は？)

そこからDとEの問題文を読んだのですが、これもよくわからない…
DはJOIにいくつか類題(いくつかに切って最小値や最大値を求める問題)があったので、とりあえずそっちの問題を見ながら進めていきました。
類題として思い当たったのが水ようかんやバームクーヘンなどで、前者は切り分けた時の最小値と最大値の差、後者は円を分割した時の最小値の最大化を求める問題でした。
水ようかんの方はとても似ている問題だと思ったので解説を見たのですが、どうやら計算量的に間に合わないらしい かなしい
バームクーヘンはO(NlogN)ぐらいで解けるらしく、そちらの解説スライドを見る事にしました。

とりあえずそれに載っていた「最小値を決め打ちして累積和にぶたんをして貪欲をする」みたいな方法を試してみましたが、"3 2 4 1 5"のようなケースでWAを吐いてしまい断念
そもそも最小値の最大化と最小値と最大値の差は全く別物なので、かなりのガバでした…

想定解だった「真ん中の値を固定してにぶたんorしゃくとり」は思いついたのですが(負け惜しみ)、2つに分割した中でさらに半分になるように切ると答えが出る、という部分に正当性を感じられなかった(ここもガバ)ので諦めました 見返すとガバばっかりだなお前

という事でDは諦めてE問題へ向かう事に この時点でNoSubのまま50分ぐらいが経過していたので、最悪このまま未提出レート変動0でもいいかなとか思ってました
見た目と制約を見るとなんとなくbitDPっぽい…それっぽくない？ みたいなお気持ちだったのでとりあえずbitDPをする方針に決めました。

まずは仮にK=6のケースについて考えてみます。
Kは2進表記で110なので、2進表記でi={000,010,100,110}になるAiの中から値の大きい二つの和を出せばいいような気がします。
しかし、その考え方だとi,j=(1,5)になるようなペアを選んだ時に総和が最大になるような数列が来た時に正しい答えを出す事ができません。
そこで、Kが小さいものから埋めていってその累積maxを取る事にします。累積maxを取る考えはサンプル2やサンプル3を合わせているうちに自然と湧く気がします。

ここまでで、各Kについて(i or j) and ~K が0になるような(i,j)の組のうちAi+Ajが最大のもののペアを取ればいい事が分かりましたが、肝心の(i,j)のペアの求め方がわかりません。
とりあえずdp[i][j]:kを「i and ~k == 0を満たすAiの中でj番目に大きい値」としてみます。
この場合、dp配列の添字jの部分は2個しか取らなくてよく、添字iの部分は2^N個取る必要があるので、O(2^N*(一回の遷移にかかる計算量))ぐらいでDPができそうです。

肝心の遷移については配るDPで、「0<=K<Nを満たす各Kについて、dp[i|(1<<K)]の部分にdp[i][0]とdp[i][1]を割り込ませる」みたいな感じの事を考えてみます。
もしdp[i|(1<<K)][0]よりdp[i][0]の方が大きかったらdp[i|(1<<K)][1]=dp[i|(1<<K)][0]としてdp[i|(1<<K)][0]=dp[i][0]とすればいいですし、dp[i][1]についても同様に遷移ができます。
しかしこのような取り方をすると、A0が最大になるようなケースでdp[8][0]とdp[8][1]の両方がA0になってしまうような問題が起こります。同じ値が来た時に回避させたいならif(dp[i|(1<<K)][0] != dp[i][0])のようにすればいい気もしますが、数列の複数の要素が同じ値を取っている場合に問題を起こしてしまいます。
そこで、dp[i][j]:kを「i and ~k == 0を満たすAiの中でj番目に大きい値のindex」と変えて重複対応をしてみると綺麗に解決させる事ができます。

ここまで書いてサンプルを合わせたら後は提出のみ、なのですが開始80分を過ぎた後の初Submitは心臓に悪かった…
これで落ちたら最悪太陽だったので、通った時は本当に安心しました。

さて、このままだとE<CDで負けてしまうのでCを通す事にします。CE>CDなのでそこさえ通せれば順位もレートも爆上げなはず…！
落ち着いて考え直してもまぁ三分探索っぽいなぁ…って感じだったので、インターネッツから他人のライブラリを盗んでくる事にしました。
判定関数の実装部分はとても楽でバグらせる事はなかったのですが、初期でのbの範囲設定を[0,INF)とかにすると最後のサンプルが合わず普通にWAを吐くので注意しましょう…計算量にも余裕があるので[-10¹⁸,10¹⁸]を初期範囲に持った三分探索をしました。

これでCも通して2完、CD2完の人より高い点数なので順位も爆上げで精神に優しかったです 0完太陽じゃなくて本当によかった

おわりに

また水色に落ちたら記事を書く予定です お楽しみに！