Slimes全体感想92分6完(2ペナルティ)で118位でした。いやー、最近のABCコンテストの中ではかなり難しく感じていました。F,Eを読むも後回しにしてAから解きました。問題Dの時点で、ちゃんと証明しきるまでに結構苦労しました。ABCコンテストの問題Eの中で最難に感じてしまいました。私の解法はBIT上の二分探索を何度か使うのですが、そもそもBIT自体がABCコンテストではほとんど使ったことがないため結構大変ですよね。writerデビューの方が何人かいらっしゃったようで、お疲れ様でした。楽しませていただきました。書けることが分かります。A_4\]と分解できます。条件に分離できているので解けます。好きな方をとれると考える」みたいな考え方は、過去問でも何度も出てきている考え方だと思います。Unhappiness幸福度は、「LL」または「RR」と並んでいる位置の個数です。長い区間をflipしたときに何が起こるかを考えると、flipする・しない区間の境界まわりでのみ幸福度の変化の可能性があることが分かります。・1手あたり、多くとも幸福度が2点しか増えないことが分かります。このことを元に、サンプルを個別に手計算してみると、「基本的には必ず幸福度+2が実現できる」気持ちになります。入力例3が例外ですが、さすがに理論値を超えて幸福度を増やすのは無理なので。するような操作が存在するを証明したくなります。これが成立するかどうかは瞬時には確信が持てなかったのですが、サンプルで全て成り立ったこと以外に、最近のABC-D問題の難易度とかからの類推という気持ちもありました(笑)はじめはこのことを、全体の並びの左端の方・右端の方に注目して証明したのですが、左から順にやっていく方が簡単でしたね。・幸福度4:LLRRLRLRRR・幸福度6:LLLLLRLRRR・幸福度8:LLLLLLLRRR・幸福度9:LLLLLLLLLL非幸福度が2以上ならば+2、非幸福度が1ならば+1が実現できます。■これと同様に、各数値が何度足されるかを考えます。[入力例3]で5が足される回数を考えましょう。1この課題を考える際には、周囲の数が5より大きいかどうかしか関係ありません。x「最大・最小」「K番目の数」「中央値」のように順位が絡む問題は「ある基準値から見て2値化して考える」というのも、頻出のテクニックです。この数が最大値から2番目となるには、自身より大きい数を1つだけ取り込まなければいけません。どちらを取り込むかで場合分けします。6通りという要領です。(小さい数)のところは(連結になる形であれば)自由に使う・使わないを選べます。oの位置が必要です(左に1つもない場合などを適切に処理しわける必要もあります)。ここまでの考察でも十分問題E程度の密度があるように思います。ここからの実装がまた頭を悩ませます。配列に、大きい数から順に挿入していくことを考えます。xこのような順で処理をすると、oxの2値を自然と表現できます。各時点で、「自分の左にあって値が入っている最寄りのセル」等が取得できればよいことになります。・C++のset型のような二分木であれば、ソート順を維持した形でデータを持っているため、「左隣」等の取得が容易です。・pythonのlistに挿入する形だと難しいです。二分探索か挿入のどちらかが遅くなると思います。tree)を用いて処理しました。これはある点の値の変更・区間和の取得を高速に行えるデータ構造です。「値を追加する位置に1を加える」→「区間[L,R]内での和をとれば、[L,R]内のデータ件数を数えられる」という形で、数え上げの小道具として利用することができます。ARC-C難易度を埋めていると何度も出てきます。今回は、BIT上でさらに二分探索を行うのでややこしかったです。私は今のところライブラリ化の類は一切していないのですが、何度も経験していると、適当なデータで自分でテストしながらさっと正確に書けるようになりつつあります。Slimesこちらの方が問題Eよりも時間かかりましたが、こちらはもう少し早く乗り越えられるべきだったような気もします。貪欲アルゴリズム周りは、「こうやるとうまくいくよね!」とやるよりも、「最適解を観察すると、こういう性質を仮定してよいことが分かる」という観察をまずは固めていく方が良いですね。これは過去問の経験でだんだんと分かってきました。・あるスライム個体に注目する。1日目・2日目・3日目・...に生むスライムの強さは、降順であるとしてよい。・ある日のスライム生産に注目する。「としてよい」は、「解が存在するならば、そのうちで〇〇を満たすものが存在するはず」ということです。アルゴリズムに反映させていきたいです。0日目は自明なので、1日目、2日目について考察します。この日に受け持つとしてよい。この日に受け持つとしてよい。この日に受け持つとしてよい。受け持つとしてよいこと以外は、冒頭に述べた性質から仮定できます。受け持つとしてよいかは微妙なところですが、ここをもう少し考えると別の方法に比べて「生産力・残タスクどちらの意味でも損はしない」ことが分かります。あー、結局冒頭の考察は要らなかったかもしれません。結局毎日を「強いスライムから順に見て、残タスクスライムのうち最強のものを片付けていけばよい」が分かります。他の方法をとると、各時点で常に「生産力・残タスクともに下位互換」が維持されます。貪欲というのは一見もっとも易しいやつですが、私は苦手意識があります。行き当たりばったりでない思考順序が少しずつつかめてきている気もしますが、今回のFは苦労してしまいました。32分5完で114位でした。36分6完1ペナで、64位でした。37分6完1ペナルティで22位でした。63分6完で39位でした。形式的べき級数解説pythonその他タイトルとURLをコピーしました。