| A | B | C | D | E | F | |
| 問題文 | ■ | ■ | ■ | ■ | ■ | ■ |
| 自分の提出 | ■ | ■ | ■ | ■ | ■ | ■ |
| 結果 | AC | AC | AC | AC | AC | AC |
全体感想
92分6完（2ペナルティ）で118位でした。
いやー、最近のABCコンテストの中ではかなり難しく感じていました。
F,Eを読むも後回しにしてAから解きました。
問題Dの時点で、ちゃんと証明しきるまでに結構苦労しました。そして、問題E。ABCコンテストの問題Eの中で最難に感じてしまいました。私の解法はBIT上の二分探索を何度か使うのですが、そもそもBIT自体がABCコンテストではほとんど使ったことがないため結構大変ですよね。
writerデビューの方が何人かいらっしゃったようで、お疲れ様でした。楽しませていただきました。
問題C – Maximal Value
例えば $N = 4$ だと
\[B_1\geq \max\{A_1,A_2\},\qquad B_2\geq \max\{A_2,A_3\},\qquad B_3\geq \max\{A_3,A_4\}\] と書けることが分かります。$a\geq \max\{b,c\}\iff a\geq b \text{かつ} a\geq c$ なので、これらは
\[B_1\geq A_1,\quad B_1\geq A_2,\quad B_2\geq A_2,\quad B_2\geq A_3,\quad B_3\geq A_3,\quad B_3\geq A_4\]と分解できます。この式を眺めながら、「$B$ が与えられたときに $A$ を最大化せよ」という問題を考えればよく、個別の $A_i$ の条件に分離できているので解けます。
$\max$, $\min$ の取り扱いに関して、「$\max$, $\min$ と書いてあっても結局個別に考える / 好きな方をとれると考える」みたいな考え方は、過去問でも何度も出てきている考え方だと思います。
問題D – Face Produces Unhappiness
幸福度は、「LL」または「RR」と並んでいる位置の個数です。
長い区間をflipしたときに何が起こるかを考えると、flipする・しない区間の境界まわりでのみ幸福度の変化の可能性があることが分かります。この辺の気持ちをきちんと精密化すると、
・1手あたり、多くとも幸福度が2点しか増えない
ことが分かります。このことを元に、サンプルを個別に手計算してみると、「基本的には必ず幸福度+2が実現できる」気持ちになります。入力例3が例外ですが、さすがに理論値を超えて幸福度を増やすのは無理なので。
・幸福度が $N-3 $人以下ならば、幸福度を $+2$ するような操作が存在する
を証明したくなります。これが成立するかどうかは瞬時には確信が持てなかったのですが、サンプルで全て成り立ったこと以外に、最近のABC-D問題の難易度とかからの類推という気持ちもありました（笑）
はじめはこのことを、全体の並びの左端の方・右端の方に注目して証明したのですが、左から順にやっていく方が簡単でしたね。
・幸福度4：LLRRLRLRRR
・幸福度6：LLLLLRLRRR
・幸福度8：LLLLLLLRRR
・幸福度9：LLLLLLLLLL
非幸福度が2以上ならば+2、非幸福度が1ならば+1が実現できます。
問題E – Second Sum
次の問題が本問題のほぼ下位互換ですので、先にこちらに取り組むのがよいと思います：
・AGC 005 B – Minimum Sum → ■
これと同様に、各数値が何度足されるかを考えます。たとえば[入力例3]で5が足される回数を考えましょう。
・8 2 7 3 4 5 6 1
この課題を考える際には、周囲の数が5より大きいかどうかしか関係ありません。
・o x o x x ! o x
「最大・最小」「K番目の数」「中央値」のように順位が絡む問題は「ある基準値から見て2値化して考える」というのも、頻出のテクニックです。
この数が最大値から2番目となるには、自身より大きい数を1つだけ取り込まなければいけません。どちらを取り込むかで場合分けします。
・o x o x x ! o x → 2 × 1 = 2通り
・o x o x x ! o x → 3 × 2 = 6通り
という要領です。最大値となる値を決めたら、前後の x （小さい数）のところは（連結になる形であれば）自由に使う・使わないを選べます。
計算に必要な数値を考えると
・自身の左にある1番目の o（大きい数）の位置
・自身の左にある2番目の oの位置
・自身の右にある1番目の oの位置
・自身の右にある2番目の oの位置
が必要です（左に1つもない場合などを適切に処理しわける必要もあります）。
ここまでの考察でも十分問題E程度の密度があるように思います。ここからの実装がまた頭を悩ませます。
配列に、大きい数から順に挿入していくことを考えます。
・8 x x x x x x x
・8 x 7 x x x x x
・8 x 7 x x x 6 x
・8 x 7 x x 5 6 x
このような順で処理をすると、oxの2値を自然と表現できます。各時点で、「自分の左にあって値が入っている最寄りのセル」等が取得できればよいことになります。
・C++のset型のような二分木であれば、ソート順を維持した形でデータを持っているため、「左隣」等の取得が容易です。
・pythonのlistに挿入する形だと難しいです。二分探索か挿入のどちらかが遅くなると思います。setは二分木ではなくhashなので、順序の構造は扱えません（追加・削除・検索等はO(1)で速い）。
私はBIT（fenwick tree）を用いて処理しました。これはある点の値の変更・区間和の取得を高速に行えるデータ構造です。「値の変更・和」といっても用途が見えにくいですが、
「値を追加する位置に1を加える」→「区間[L,R]内での和をとれば、[L,R]内のデータ件数を数えられる」
という形で、数え上げの小道具として利用することができます。この用例は ARC-C難易度を埋めていると何度も出てきます。今回は、BIT上でさらに二分探索を行うのでややこしかったです。
私は今のところライブラリ化の類は一切していないのですが、何度も経験していると、適当なデータで自分でテストしながらさっと正確に書けるようになりつつあります。
問題F – Many Slimes
貪欲アルゴリズム周りは、「こうやるとうまくいくよね！」とやるよりも、「最適解を観察すると、こういう性質を仮定してよいことが分かる」という観察をまずは固めていく方が良いですね。これは過去問の経験でだんだんと分かってきました。
・ある日のスライム生産に注目する。強いスライムほど強いスライムを生んでいるとしてよい（$a\geq b$ で $a$ が$a’$, $b$ が $b’$ を生むならば$a\geq a’$, $b\geq b’$ としてよい）。
・2日目に、スライム$a,b$ が居る。やはり、スライム $a$ は残スライムのうち最強のスライム $c$ をこの日に受け持つとしてよい。スライム $b$ は、生産可能な残スライムのうち最強のもの $d$ をこの日に受け持つとしてよい。
$d$ を受け持つとしてよいこと以外は、冒頭に述べた性質から仮定できます。スライム $b$ が $d$ を受け持つとしてよいかは微妙なところですが、ここをもう少し考えると別の方法に比べて「生産力・残タスクどちらの意味でも損はしない」ことが分かります。
