ABC268

ABCDFの5完。実装問で下げて未証明ACで上げるレーティングに価値はない。調子はよかった。

A - Five Integers

std::setに突っ込んでsize()が答え。この内容で1分切ったのは偉い。

B - Prefix?

100文字以下なので普通にTからSを探して(最初に現れるものが)先頭ならYes。けっこう神経を使う。string::findの戻り値がイテレータじゃないの忘れてた。

C - Chinese Restaurant

FFTみがある。かなり難しい。全然わからない。円だと考えにくいので直線で考える。対応する料理との距離に注目して、解法に気づいた。問題を少し単純にして、自分の目の前に料理がある人数を最大化してみる。すると、どれだけ動かしたときにスコアが入るかは人毎に決まる。配列でカウントして最大値を見るだけでいい。元の問題についても、これを3か所にやるだけでいい(ほんとにいいのか?という感じだが、各操作回数(N回未満)に対しそれで喜ぶのが何人かはちゃんと求まっている)。自分の実装ではvectorじゃなくてmapで数えてて草。ここまでかなりスピードを出せている。

D - Unique Username

問題文を理解するのが大変。とりあえず読んで、Xが3文字以上と制約の一部の意図がまだわからない。全然わからないので全探索を疑ってみると、N=8のときはアンダースコアの自由度が低く、N=6などでは順列がそもそも少ないので、たぶん条件に合う文字列は全列挙できる。まずTを全部unordered_setに入れる(AやCでunorderedにするの忘れたなあとか思いながら)。next_permutationでSの(インデックスの)並べ替えをして、あとは再帰も考えたけど残り文字数の管理がめんどくさそうなのでループで済ます方針にした。2重のnext_permutation。N-1個の仕切りと、16からSたちの長さを引いていって必ず使うアンダースコアの個数N-1も引いたもの。ここで制約の意味がわかった(必ず入れるアンダースコアを含めて16文字以内)。あとは構成してそれがunordered_setに入ってなかったら出力して終了。

16文字以下の条件が不要なのはわかっていたが、保険として入れた。そんな気が起こるくらい、めっちゃ時間かかってる。提出してWA。アンダースコアの個数を表すvectorのカウンタの宣言が1個外側にあった。直してAC。3文字以上の制約は(16文字以下も)、AtCoderに登録する名前が由来らしい。そんなん気づかんわ。それを誰もが知っているという状況ならこういう出題もありかもしれんが。いや、それが本質でない問題なら嫌だな。そもそも問題の内容を理解した時点で現実のユーザー名という概念から離れる。

(追記)計算量見積もり難しすぎだろと思ってたけど、鳩の巣原理か(見積もる必要がなかった)。これは完全にやられた。3文字未満の文字列は、全部生成してTに突っ込んでしまえと思ったくらい少ないし、条件を満たさない文字列がTに含まれていても得しかない。

E - Chinese Restaurant (Three-Star Version)

これもなかなか難しい。Three-Starの意味がわからない。しばらく考えて差分計算のようなことができそうだと気づく。ある人に注目して、例えば初期状態で目の前に対応する料理があったとして、N回操作すると最初は1ずつ不満度が増えて次に1ずつ減ってとなる。このままではだめだが、何か工夫できそう。いもす法じゃん。書き始めてから、思った以上に複雑であることに気づく。Nが奇数のとき1回だけ不満度が変化しないことがあるというのも気づいてなかった。残り20分強というところで諦めてFへ。Dが30分弱で解けて、Eが30分強で解けなかった。何この時間。

(追記)
ACLの畳み込みで解いた。具体的な操作回数と不満度の関係を構成して、料理との距離の分布と。コードは短くなったが、この方針だと考察難度はEという感じではない(難しくて時間かかった)(青diffらしいのでそれなら妥当か)。

コンテスト中に書いてたやつ、細かいところは合ってた(すげえ)(問題の対称性の高さに助けられた感はある)。大きな間違いが2つあり、不満度ではなく満足度みたいのを考えてて符号が逆だったのと、いもす法で累積和を2回とる必要があるところ1回でいいと思っていた。

自分の能力を超えた実装で時間を溶かすよりは楽な方針を探したほうがいい?でもそれって実力が高いからできることだと思うんだよな。簡単な問題なら自分もそうしてるし。この問題は向きで混乱しやすく方針を変えると以前の考え方を引きずって更に混乱する可能性が高い。そもそも楽な方針を見つけるのに時間がかかる。

コンテスト中の方針のまま手作業をなくす実装を考えてAC。しかし、細部がかなり大変でめちゃくちゃ時間がかかった。いもす法で表現した山を途中からって、思ったより考えることが多い。求めているものって、楽な方針というよりは、手作業のない実装だよな(手作業はゴミのような時間)。そうなると、望んだ方針を見つけても実装はやはり時間がかかったということもある(順位が下がるだけならそれでいいが、そもそも間に合わないので、手作業を頑張って早く終わらせて次の問題を見ようと思ってしまう(それがよくないんだなあ、気をつけよう))。

F - Best Concatenation

9は、同じ位置に1が9個詰まっていると考えればいい(以下そのように考える)。Sのうち2つをとりどちらを前にするのがいいかを考えてみる。N*(N-1)/2通り全部についてどっちにしたほうがどのくらいスコアが上がるかわかればいい(間に合わないけど)。時間もないので全順序が入るという現時点では強い仮定を置いてみる。するとSはソートできてそのように連結すればスコアの最大値を与える文字列になる。なんか(実装難度が)それっぽいので実装するかあ(ゴミ)。重要なのはXの個数と1の個数なのでそれをカウントして間接ソート。その2つの文字列だけを連結したときの具体的なスコアを求める必要はなく、前のXと後ろの1の関係だけを見ればいい。個数の積が大きくなるように並べ替える。サンプルが合ったので提出してAC。

(解説を見て)なるほどこれ「Xの個数/1の個数」の降順にソートしてたのか。0個のときも含めちゃんと順序が入っている。わかんなかったー。

G - Random Student ID

(追記)コンテスト中にちょっと見ただけ。とっかかりがないなーと思っていたが、解説を見ると2者を比べればいいのか(このくらい気づきたいが)。今回のABCは、CとEが似てるし、BとGも接頭辞つながり、DFも文字列で、こういうなんとなくつながってるセットは好きだ。トライ木を使うらしいというツイートも見てたので、これで解けそう。自分の上と下に何個ずつあるかDFSしながら数える。接頭辞の関係になければ半々。相手の接頭辞になれば必ず勝つ。逆は負け。他のケースはない。半々を基準にすると必勝は0.5だけ期待順位が上がる。

夏アニメ第7話

話数が進んでいない作品も多く、もうクールの終わりなのに7話というタイトルが合ってしまう。

ラブライブ!スーパースター!! 2期 #7

冒頭のゲーム、一人でやっててびっくりした。れんちゃんぶっこわれちゃった。相変わらずかのんが強くて感動的。でもここで恋と1年生(メイ)が深い関係を持つのいいぞ。サブタイも個人的にけっこういい回収。最終的に全部のキャラが生きているのがほんといい。四季とメイは後ろでバランスブレイカーなことするのやめろ。

あー、5話にゲームの伏線あったなあ。

自分がラブライブに慣れたせいかもしれないけど、2期はタンパク。形式的な感じがする。1期はEDがよくてそれが軸になってるところがあった。

異世界おじさん #7

たかふみが魔法使いこなしてるのいいな。相変わらずリズムは合わないが、かなり安定して面白い。

オーバーロードIV #8,9

8話。王国内部の折衝が面白い。ナザリックはいつものやつだけど、さすがにスルーするところ。フィリップと話してた人の声がよかった。サブタイの通りほんとに計算外だったな。

9話。ぐへへってなってるの良い。これOPの人か気づかんかった。計算通り!?

リコリス・リコイル #9,10

9話。元々!?「たきなをここに戻してあげて」がここで来るのなあ。クルミがかっこいい。

10話。EDの振り返りいいよね。真島好きなのに危うさバンバン出しててつらい。ミカと千束の関係がいい。「あまり無理するな」が、ありがちな台詞にみえてこの人にしか言えないものになっている。

こういう作品でネタバレが避けられないのはわかっているから、そういう意味では最初からさめてる。

異世界薬局 #7,8

7話。ロッテと妹がかわいいというだけで見てるけどつらくなってきたな。今回出てきた男はやべー性格でよかった。オーバーロードにもこんな老人いたよな。

8話。インフルエンザあるんかい。異世界薬局が現れて被害を受けている既存ギルドが悪者みたいに描かれるのきついなあ(ファルマが悪者になりそうなところをごまかされている)。しかも、過去に貴族から酷い扱いを受けてこうなったっぽいのが悲しさしかない。

ダンジョンに出会いを求めるのは間違っているだろうかIV #6,7

6話。リリがメインの話だったけどこれでは不遇感が残る。んー打ち破ったという夢は次回に来るってこと?

7話。コメント見てたけど予知夢の設定面白そうだな。悪い結果を避けるから信じてもらえないのどうしようもなさ。

プロセカ その8

前回。調子が悪くて書きかけで2週間くらい放置していたので、前半部分は2週間前までの状況しか反映されていない。


(このスクショは昨日のものなので今は少し数が変わっている)

Lv.27以下を全てMASTER解放した。27上位は本当に重くて、回数重ねて上振れでできただけという印象しかない。Lv.28の解放済みは「脳漿炸裂ガール」のみ。28のMASTER解放は、不可能とは思わないけどだいぶ遠く感じる。少しの回復で28のクリアが安定するのは良い。タイミング調整でトリルが安定するようになったのがとにかく大きい。

MASTERの簡単なやつと短いやつを全部フルコンして、これで11個。フルコン狙いはあまりしてこなかったけど、狙えるだけの力が付いたと思ったので時間をかけてやった。特に苦戦したのは「再生」と「オーダーメイド」。スライドがそこそこできるようになっていて、「再生」のように遅い曲なら目で指と譜面を追うこともできるのだが、必ずどこかで落としてそれが見えないのがつらかった。最終的には録画してメリハリのある動きを心がけることで通った。「オーダーメイド」は以前も苦戦していた最後のほうの1か所がやはりできなかった。スライドはできている気がするのだが、反対側のフリックが抜けているのだろうか。すごい回数やって、1回通ったのでよし。ここからフルコン数を増やすのは険しい道になりそう。

EXPERTの低難度帯のフルコン埋めをした。23以下では「シャルル」だけ残ってしまっている。そんなに気合いを入れてやっていたわけではないけど。やはりこれだけの時を経て未フルコンで残っているだけあって、苦手な譜面が多かった。「幽霊東京」と「ビバハピ」をようやくフルコンできたのはよかった。「幽霊東京」は本当に苦手。フリック絡みもそうだけど、全体として様々な基礎を試される譜面で、一つでも落としたらフルコンできないからそりゃあフルコンできない。

HARDの高難度のフルコン埋めをした。19以上でフルコンしてないのは「エンドマークに希望と涙を添えて」のみ。「the EmpErroR」のフリックを通してフルコンしたのは地力が付いているのを実感したが、エンドマはまだ無理そう。1回だけMISSが1個だけまで行ったけど、その部分(タップタップフリックの連続)はたぶんまだコンボがつながったことがないし、他の部分もそれなりに難しい。

MASTERの29以下のクリア埋めをやろうとしたが、「命に嫌われている。」だけ全く歯が立たない。まあ回復積んでクリアというのは難易度評価がかなり歪むよね。適正難度になって初めてわかることは多い。

EXPERTの高難度のクリアを久しぶりに目指してみたが、30はクリアできて、31はクリアできなかった。30は、トリルのスピードさえあれば回復でゴリ押しできて、31はそれに加えて技術も要求される感じ。実力が上がったと思うたびに挑戦してきたが、ようやく消失EXがクリアできた。交互押しの速さがHARDからEXPERTで1.5倍になってるのがやばすぎだった。HARDのほうは最近かなりゆっくりに感じるようになっていたが、それでも1.5倍は大きすぎる。

速さ。9.5にして「愛されなくても君がいる」EXPERTをフルコン。10.2で「チルドレンレコード」をMASTER解放。(9.5は上のレベルだと遅いので)9.8と10.2を使い分ける?でも色々試して大抵10.0がよさそう。その後は、何か打開策を求めるときたまに速さを変えるようになった。27で最後に残った「カゲロウデイズ」をMASTER解放したときは10.2だった。連戦で左腕が疲れた状態だったのにスルッといい結果を出してしまった。

タイミング調整

-3.0は明らかにマイナスすぎ。-1.0から-2.0のどこかが適切っぽい。その範囲だと、以前はできなかったトリルが気持ちよく決まる(そこくらいしか判断基準がない(LATEとFASTの比率は意識次第である程度変えられる))。ということで、-1.5や-2.0を一定期間試して、今は-1.5で落ち着いている。特に、-2.0はマイナスすぎだと思いつつ時間をかけて慣れようとしてみた(実験的に)(何らかの技術を身に付けようという意図もある)。その後、-2.0だと体感でさすがに合わない曲があり、-1.0もトリルをやった感じ足りない気がするので、その中間の-1.5。中間のがマシという考え方もあやしいけど。

曲によってタイミングに1.0程度の違いはあるような気がして、でもそれは自分の癖のせいでそこまでずれてるわけないだろとも思うし。フルコンを狙うときは曲に合わせて変えることもある。「悪ノ娘」と「悪ノ召使」のMASTERは-2.0で、「いーあるふぁんくらぶ」のEXPERTは-1.0でフルコンした。マイナスにずらすのは、LATEがあまりにも多くなったとき(割合もそうだけど、ある程度絶対数があるとき)。プラスにずらすのは、タップしたいのに譜面が流れてこないという明らかに体感でずれてるとき。ブラインドテストしたいよね(まあ変更したのを忘れててそうなってたことあるけど(言われなきゃわからない))。体感は次やったら変わってるとか勘違いだったとか普通にあるから難しい。

-2.0から-1.5にしたのは、FASTが多くずれも感じる「テオ」がきっかけ。これでMASTER解放した。(GOOD以下が)7という数は大きいなあと思った。「アイディスマイル」EXPERTはさすがに-1.5でもFASTが出るし体感もそう。MASTERだと-1.5で半々だったけど、自分にとってレベルの高い譜面はそうなる。

2週間後

「from Y to Y」のMASTERをフルコン、これで12個。行けなくもなさそうなものはいくつか残っているがその後のビジョンがない。昨日はEXPERTの24~25のフルコン埋めをやった。今日は「シャルル」のEXPERTをフルコン、これで23以下が終わり。EXPERTの24以下で残っているのは、「少女レイ」(あまりやってない)と「威風堂々」「Forward」(難しい)の3個。これでEXPERTのフルコン数は137。こんなところまで来れるとは思ってなかったな。25はかなり難しいものが多く、「何回かやれば行けそう」なものはもう残っていない。26だと、「ミルククラウン・オン・ソーネチカ」をフルコンしたのは嬉しかった。25のMASTER解放をやっていたころ、タップ主体でとっつきやすい26も同時にやっていて、その中の一つ。ようやくフルコンできる実力が付いた。HARDのフルコン数は204。全埋めの可能性が出てきたのと、挑戦したときのフルコン率がかなり高くだいぶフルコン数が増えてきてたので、積極的に埋め始めている。

で、タイミング調整。-0.5を少し試していて、やはり譜面が深いところまで来る気がして-1.0にした、つもりだった。2日後、-0.5だったことに気づく。意外とマイナスなくていいのか?と思い0.0を試すことに。数日後、やはりLATEが多い傾向にあるため、基本を-0.5に戻す。曲によってそのときの自分の感じ方は色々なので、フルコンを目指すときなどは0.5ずつくらい変えながら合わせていく(そうしているうちにフルコンできたらよい)。今の自分は、ある程度、曲だけでなくノーツも見てPERFECTを取りに行けるようになっている。そのため、GREATで妥協しない意識も以前よりはかなり強く持てるようになった。

え、トリル?0.0や-0.5でそれなりに取れてるけど。おそらくは、元々遅れ気味でコンボが途切れていたトリルが、タイミングを-1.5などにすることでつながるようになり、それがきっかけで技術が向上し、タイミングを元に戻しても技術はそのまま使えてるということかと。これからは、「トリルは早め意識」「(-1.5だから)早め意識は要らない」などの邪魔になった足場を撤去していくフェーズに入るのだと思う。

以前から気になってはいたのだが、自分は10年以上前からProject DIVAシリーズをやっていて、それは判定が遅いと言われていた。また、打鍵音の遅延も現在のプロセカ(SonicSYNCを使っている)よりはずっと大きかったと思う。つまり、曲に対してタップ音が遅く鳴ることに慣れている恐れがある。遅延によって変な癖が付いている可能性がある。だから0.0だとLATEが多いのかななどと思ったり。あと、Project DIVAだと、慣れてからは、曲の初めのほうで「この曲は早め意識だな」とか曲毎のタイミングを捉えてプレイしていた(自分がそう感じているだけだとしてもFINEを減らす効果はあると思う)。プロセカだと、それはできていない。DIVAはボタン押すの大変でプロセカは楽にタップできるぶん譜面が高密度でという違いはあるが、どうなんだろうなあ。

それで、スライドノーツの中にある粒で鳴る音はさすがに0.0で曲と合わせてあるはずで、それと自分がタップして鳴る音は合わせる必要があるから0.0が正しいのではとか思ってて(SEありだと0.0しかないことになってしまうが正しいか?)。結局、今は-0.5をベースに必要ならその場で変えるという運用。「フューチャー・イヴ」は、タイミングを変えながら曲と譜面をだんだん理解していく感じだった。Lv.27は全てMASTER解放したと書いたが、これはまだ。ブログ書いてる途中で新曲追加されちゃったじゃん。今後も、自分の状態に合わせて変えていく必要があると思う。

今後ね。いよいよ、やることが減ってきた。MASTER解放もフルコンも、もう簡単には増えない。「下手になったなあ」と感じることが増えてきた。EXPERTもMASTERも、26,27をフルコンとか、回復なしで28をやるとか、そういうステップに進むんだけど、さすがにそんな精度やスピードは物理的な限界が近いのではと思ってしまう。まあこれだけの長期間、実力が伸び続けたというだけでもすごいゲームだよな。やることがないわけではない。最近EXPERT低難度でGREATが減ってきたのは感じるので、そこをより磨いて、あとはMASTERの27くらいを集中的にやるとかかな。

左手人差し指の先と右手首は、プレイに大きい影響は出ていないものの、違和感の強さに波があり、引き続き注意していく。

ほか

ライブボーナスドリンクが増加傾向にある。これまでは、イベントでもう少しで10万位あるいは5万位以内に入れるときと、ライブミッションがもう少しで全クリアできるときに使っていた。余っているなら、イベントストーリーの初日全解放にも使うことにした。それでも余るので、まあ細かいこと(あと5分で1回復するときプレイヤーランクが上がりそうなら待つとか)を気にしないために雑に使っていきたいが性格的にどうか。

8/31開始のイベントは、調子が悪いのもあって淡々とチアフルでライボを消化していた。ドリンク大を2個使って初日にイベストを解放し、ずっと15000位前後とこれまでで最もいい順位で推移していた。ライボ消化だけでも毎日けっこうな回数やるので、ほぼ毎日上限である3回ライボをもらえていた気がする(かなり大きい)。願いの雫も1個取れそうだなと思っていたが、終了日を勘違いしていて今日慌ててドリンク大を3個使い雫を取った(初めて)。報酬の星3リン(残念ながら判定強化だがチアフルならリーダーにしなければあまり関係ない)を使い、総合力21万で210%とけっこう強い編成にできていた。ドリンクを使って1万位を目指すかについては、1万5千と1万はめちゃくちゃ距離があるのと、報酬があまり増えないことから、やらなかった。

スタンプは欲しいと思いつつスタンプ交換券が溜まっていたので、イベント前にそのイベントのキャラのスタンプを交換して使うことにした。

イベントがない日はレベルがMAXでないメンバーの育成にあてる(こういうときキズナを考慮するの毎回忘れる)。キャラクターランク上げがもうサイドストーリー後編解放くらいしかなくなってきた。

イベスト。やっぱニーゴなんだよなあ。具体的にってわけじゃないけど共感できるという意味では抜けてる。今回のレオニもよかった。リンがかわいすぎるし、カイトが強キャラ感ある。何か起こるわけじゃないけど、王道な話で面白い。

お知らせが長文すぎてヤバ。まふゆの表の顔はエリア会話でも最近既読のを見た気がするしそういうものだと思ってた。

FAST/LATEの表示でGREATを意識できるようになったのはいいが、GOODをたまに見落とすようになった(フルコンと思ったら違ったということがあった)。

「メルト」MASTERの最後の縦連が初めて通った。GREATは100あったけど。こないだの仕様変更の影響も大きそう。EXPERTのフルコンもしたいね(惜しいところまでは行く)。

EASYでフルコンを逃した回数をそろそろ忘れてそう。プロセカを始めたばかりのころに1回と、なんかタップが入らなくて落としたやつ、よそ見してて最初がGOODだったやつ、PC画面を凝視(ぷよぷよ用語)したらミスったやつ。4回かな。

チアフルで「未完成賛歌」EXPERT初フルコン、しかし「通信が切断されたためホームに戻ります。」と言われ、なかったことに。

「脳漿炸裂ガール」のオスメスのところでいつもミスるの、「千本桜」の少年少女と譜面が似てるからつられて早めに離してしまうのではないか。

曲を練習するとき、回数は2回がよい。1回だとやりっぱなしという感じになるし、3回目からはどうしてもダレる。何かテーマを持ってやっているなら5回くらいはあり。

全く眠れない深夜にログインボーナスもらってしまった(午前4時に日付が切り替わる)。その後眠れた。オートライブで火消ししたので、ギリギリでライボを全く漏らさなかった(初めて)。

「眠りを知らぬ怠惰な未亡人」という期間限定星2があり、サイドストーリーがないらしい(メンバーのデータを整理していた)。

表計算ソフトでキズナランクを管理して、まあ時間をかけて入力するわけだけど、おかげで1つを除いてキズナランク5を達成した。5はわりとすぐだけど、10はかなり時間がかかるし、16とかはやる気が起きない。ランク5で称号を得るのは楽しかったけど、やることがなくなった。

キズナランクの種類数は、最初85個、3/29のv2.0.0で3個追加、5/10に24個追加、7/11に24個追加で現在136個。キャラ数が26なので325個が上限。

「アイディスマイル」のフィーバーチャンスの入り方が好き。DIVAの「from Y to Y」のチャンスタイムを思わせる。静かに入るんだけどそのまま静かに盛り上がるというか。

この前ライボあげたとき初めて遥の「いただきます」で返された。自分はけっこう前から好んで使っていた。「ごめんなさい」「大丈夫だよ」の典型っぽいやり取りも最近初めて見た気がする。そういう出会い。

「霽れを待つ」って書き下ろし曲だったのかよ!

どこかで聞いたと思ったルンパッパは「インビジブル」(Project miraiシリーズ)だった。空耳とかじゃなくて「拝啓ドッペルゲンガー」でもちゃんとルンパッパという歌詞だった。同じ人の曲。

「君の夜をくれ」のMASTER、「悪魔の踊り方」と言われててなるほどね。どっちも全然できない。

最近、カクつくことが多い。みんなでライブで特に。夏のせいなのかFAST/LATE付けてるせいなのか。困るのはソロでやってるときだよね。さすがに低頻度だけど、それでフルコン逃したことも一応あるからな。なんとかなってくれ。

ARC147

4完。ARCは、長期的には実力が出るけど、まあその回の順位を競おうとするとクソゲー

A - Max Mod Min

ソートしてしまっていい。よく読むと、そのソートした列の左端と右端を使うとしてよい。シミュレーションが間に合うかを考えると、A_iとして選ばれたものが毎回半分以下になりそうだ(A_iがA_jの2倍以上ならA_j未満になって半分以下、そうでないならA_jの2倍未満のものからA_jが引かれるのでやはり半分以下)。操作を行うとA_iはA_j未満になるので末尾から先頭に持ってくればそのままソートされた状態が保たれる。dequeを使えばよい。

B - Swap to Sort

まず、奇数番目と偶数番目の2種類の世界に分かれていて、操作Bでは同じ世界の中同士しか入れ替えることができない。とりあえず、操作Bで好きなだけ揃えてその後転倒数のぶんだけ操作Aをするという方法を思いついたが、1234→3214→3241と逆に操作していくと反例が構成できてしまった(最初に3142と操作しては操作Aがたくさん必要になる)。転倒数について考え直すと、操作Bは操作Aを3回で実現できて転倒数は1か3変わる。

逆だ。そもそも操作Aの回数を最小にする問題なんだから、そこから考えるのは自然だろ。操作Bでは違う世界に行けないので、奇数の世界にいる偶数と偶数の世界にいる奇数が同数存在しその数だけ操作Aが必要になる。そしてそれは達成できる。なるほどねー。操作Bの回数が気になるが、1回の操作Aに対してN/2回以下の操作で隣接させることができ、操作Aの必要数はN/2以下なので、ここで4万。それぞれの世界のソートは、長さがN/2くらいなので、2回のソートでN*N/4回くらいでやはり4万。合計で10万よりは少ないのでOK。提出してWA。

正しそうな考察とコードをデバッグするのはつまらないね。これ競プロの構造的欠陥だよな。左から順に偶奇が合ってないのを見つけて、右に向かって相手を探してそこまで操作Bで持っていくという実装にしていたが、これだとスワップした結果その場所に偶奇が合わないものがまた存在している可能性がある。その場所をまた調べるように変更してAC。14分もかかってしまった。

C - Min Diff Sum

ある並べ方について、一人(同じ座標に他の人はいないとする)を微小に動かしたときのスコアの変化を考える。左右にいる人数が重要だ。左に5人右に1人の場合、左に動かすと動かした距離の4倍スコアが改善する。だが、区間なので扱いが難しい。

端から考えてみる。区間の右端が最小のものと区間の左端が最大のものを考えると、これはそれぞれ右端と左端を選ぶとしてよさそうだ。ただし、その2つの区間に共通部分があるとき(区間が1つしかないときを含む)は全部の人がその中の同じ座標を選べるので場合分けが必要。これを繰り返すことを考えると、もう解けていそうだ。最初はスコアを逐次計算していくことを考えていたが、座標が決まる(最後はこれまでに選んだ最大の右端(最小の左端でもよい(左右の人数が同じなので間ならどこでもいい))の座標に全員集める)のであとはABCのC問題みたいのを解くだけだ(これに10分かかるか3分で済むかはけっこうでかいよな)。座標が全部決まったらソートして左から自分より左の人たちとの距離の寄与を足していく。これには自分より左の人たちの座標の値の合計を持っておけばいい。

実装はけっこう大変で、priority_queueに区間の左端の位置と区間のインデックスを入れる。右も同様に。座標が決まったかのフラグも持ち、priority_queueのtopを見るときは既に決まってるやつを全部popしてから。あとはフラグを更新しながら座標を決めていく。B問題よりは時間がかからなかった。

(追記)いや言われてみれば2個ずつ座標を決めていくとき左右で完全に分かれてるからpriority_queueから既に決まってるやつが出てくるわけないんだ。そうなると左端と右端を別々にソートしてもよくなる。スコア計算も、決めた2個と内側のやつらとの寄与は2個の距離に内側の人数を掛ければいい。これに2個同士のも足す。短く書けるねー。

(追記)ABC267のBもそうだけど、短く書く方法が存在するからといって「この問題は実装が軽い」とはならない。

D - Sets Scores

縦N横Mの図を描く。一番上の行は2^M通り好きに決めることができる。そこからはM通りの選択が続くのでM^(N-1)通り。「素晴らしい集合の列」が何通りあるかがわかった。で、スコアだけど、積だし、独立な気がするので、個数の期待値(単にN/2)を掛けていく。サンプルが合った。そんなうまい話はないと思ったが、順位表を見るとペナ率が異常に低い。これは可能性があると思い提出するとAC。

BCでかなり苦戦したのに、わずか13分の未証明ACでなかったことに。

E - Examination

「不正」みたいな問題名にしたほうがいいだろと思ったけどEだからこれがいいのか。何かでソートして貪欲みたいな見た目だけど800点だからな。