[AtCoder 参加感想] 2019/09/07:ABC 140

  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

こちらの方が問題Eよりも時間かかりましたが、こちらはもう少し早く乗り越えられるべきだったような気もします。

貪欲アルゴリズム周りは、「こうやるとうまくいくよね!」とやるよりも、「最適解を観察すると、こういう性質を仮定してよいことが分かる」という観察をまずは固めていく方が良いですね。これは過去問の経験でだんだんと分かってきました。
・あるスライム個体に注目する。1日目・2日目・3日目・…に生むスライムの強さは、降順であるとしてよい。
・ある日のスライム生産に注目する。強いスライムほど強いスライムを生んでいるとしてよい($a\geq b$ で $a$ が$a’$, $b$ が $b’$ を生むならば$a\geq a’$, $b\geq b’$ としてよい)。
「としてよい」は、「解が存在するならば、そのうちで〇〇を満たすものが存在するはず」ということです。
アルゴリズムに反映させていきたいです。0日目は自明なので、1日目、2日目について考察します。

・1日目に、スライム$a$ が居る。このとき、スライム $a$ は、残スライムのうち最強のスライム $b$ をこの日に受け持つとしてよい。

・2日目に、スライム$a,b$ が居る。やはり、スライム $a$ は残スライムのうち最強のスライム $c$ をこの日に受け持つとしてよい。スライム $b$ は、生産可能な残スライムのうち最強のもの $d$ をこの日に受け持つとしてよい。

$d$ を受け持つとしてよいこと以外は、冒頭に述べた性質から仮定できます。スライム $b$ が $d$ を受け持つとしてよいかは微妙なところですが、ここをもう少し考えると別の方法に比べて「生産力・残タスクどちらの意味でも損はしない」ことが分かります。
あー、結局冒頭の考察は要らなかったかもしれません。結局毎日を「強いスライムから順に見て、残タスクスライムのうち最強のものを片付けていけばよい」が分かります。他の方法をとると、各時点で常に「生産力・残タスクともに下位互換」が維持されます。
貪欲というのは一見もっとも易しいやつですが、私は苦手意識があります。行き当たりばったりでない思考順序が少しずつつかめてきている気もしますが、今回のFは苦労してしまいました。少しずつ上達していければと。

タイトルとURLをコピーしました