ARC127

3完。久々にARCであったまる。でもDEに届かないのは悔しい。残り時間が中途半端でDEの取り組み方がよくわからなかった。DEを読んで考える時間がコンテスト中にちゃんとあったのはよかった。

A - Leading 1s

1なのが嫌すぎる。先頭に1が2個並ぶ4桁の数というとき、1100も1199も入るのに1110は違う。ちらちら考えていたことがあって、1を1個ずつカウントすればいいんじゃないかと(1110だったら、1と11と111に合計3回カウントしてもらう)。結局それでよかった。なんというか、選ぶのに勇気が要る方針。高々16桁なので、1が始まる位置と終わる位置を全探索。愚直に11000とかを生成して、Nより大きければそこで終わり、そうでなければ111000であれば1000個を上限として111000以上N以下の数をカウントする。

B - Ternary Strings

対称性でえいっとするのかと思ったら、妙に自由度が高くて捉えどころがない。サンプルよりも少しだけ大きな例を手で色々いじる。2で始まるものがN個あって、そこへ小さい順に2000, 2001, 2002と割り当ててよさそうな気もするがどう構成するか。そもそも構成できるのか(かなりできそうではあるが)。逆に使わないものを抜いていくことを思いつき、解けた。3^L個並べて、2222, 1111, 0000を抜いても条件を満たしている。ということは、大きい順に抜いていくだけ。3^Lはそこそこ大きいのでvector<bool>を使った。

(解説を見て)抜くんじゃなくて直接構築すればいいね。定数倍が重いと思っていたがそういうことか(3^Lより3*Nのほうがだいぶ小さい)。なんか無駄にアクロバティックな解き方するよなたまに。

C - Binary Strings

先頭の0削除して左に詰めてるのやべーだろ。とりあえず、16未満まで書いて観察する。全部1で始まる。1を除いて、10で始まるのが残りの半分。11で始まるのがもう半分。簡単かどうかは置いといて、けっこうきれいな構造をしている。ここで、ABC218Gのユーザ解説のトライ木が浮かぶ。文字列を全部トライ木に入れると、高さNくらいになってO(N)で辿って行けそうな気がする。16未満の場合、てっぺんに1個、左に10で始まるのが7個、右に11で始まるのが7個。ここで、巨大な数Xをどう扱うかかなり悩んだ。1を引く関数は必要そうで計算量も大丈夫そうということで実装してようやく落ち着いた。まずXは先頭に0を詰めて長さNにしておく。また、Xを2進法で表したときに含まれる1の個数を管理しておく。あとはトライ木で目的の文字列を目指すだけ。Xからは1を引いておく。Xが0であればそこが答え。そうでないとき、N桁のXの最上位が0なら1を引いて左へ、1なら右へ。そして最上位の桁を(論理的に)削除する。懸念点として1を引く計算量があるのだが、同じXから何回も1を引くだけなので、1回時間かかったあとは当分大丈夫。雑に考えて平均O(log(N))には収まりそうな雰囲気を感じてこれで実装。最上位の桁を削除したとき1の個数を更新してなくてサンプル合わなかった。

(解説を見て)あーこれもA問題と同じで、3回以上繰り下がりがあるのは8回に1回だけどそれを3回ではなく1回としてカウントすれば簡単なのか(残りの2回は「2回以上」と「1回以上」で1回ずつカウントされてる)。

D - Sum of Min of Xor

サンプル2を見て、AとBが同じときでさえわからんなと思った。ペアの片側を固定すると、普通の和との差分はその固定したやつの立ってるビットそれぞれについて全体で何個立ってるか数えておけばよさそう。じゃあ一般の場合はどうか。ペア毎に毎回minとってるんだけど。これは無理でしょ。上位ビットから考えるか?ペアに含まれる4個の数のビット17(最上位)を見て、16通り。同じなら下を見る、違うなら小さいほうを採用。現状見通しが悪い。

E - Priority Queue

問題文を読んで、問題名の通りじゃんとなるまでにかなりの時間がかかる。後ろから考えると、2で区切ってどんどん小さい問題に帰着させることができそう。ただ、あまりにも簡単そうに見えてしまい逆に何もわからなくなった。整数の選び方は要するに順列なので、小さい順列で問題を解いてその隙間の好きな場所に後続の1の個数分挿入できる感じ(そうなるように番号を振り直す)。2が来たら最大のものを1個削除するんだけど、これで個数が減るけど(のちのことはさておき今は)通り数は減らない?解けそうな問題だけどこんなんでいいのかなあという感じ。