3完。Dが間に合わない、それだけでこのARCはただつまらないだけのゲームになる。競プロ、構造的欠陥があるよ。
A - Bridge and Sheets
すき間を埋める。1枚のシートで複数のすき間を埋めるケースが気になるが、区切っているのはシート（たち）なのでそういうケースはない。位置Lに番兵シートを設置して、位置0で終わるシートから始めて前のシートから今のシートまでの距離を割り算切り上げで必要枚数を求める。
B - Reserve or Reverse
（左側の文字から見て）小さい文字と入れ替えてないものがあれば削除して損しないので、小さい文字とだけ入れ替えるとしてよい。さて、最初の文字でそういう入れ替えができるなら、したほうがいい（そうしないどの結果よりも辞書順で小さくなる）。また、同じ文字と入れ替えるなら、位置は右であるほどいい（違いはのちの選択肢が広がることだけなので）。最初後ろからしゃくとりみたいに実装を始めてしまったが、セグ木。クエリ範囲で少し混乱。すっきり解けたのに、実装にかなりの時間をかけてしまった。
（解説を見て）あーこれSWAGでできんの。
（追記）よく見たらSWAG使えない。速い提出を見て、文字毎の個数を管理して最小のに当たるまでしゃくとりしていく感じでできた。
C - The Majority
過半数というのがかなり難しそうに見えるが、まずはその制約を外して考えてみる。すると、番号（そういえば色じゃなくて整数なんだな）毎に仕切りを入れるだけ。よく考えると、番号1のボールも同じようにできる。過半数というのは同数より1個以上多いというだけの話だった。その1個を各箱に配り、他の番号のボールに1対1対応させる。それができなければ0通り。できるなら、残ったものを他の番号と同様に処理する。全部掛け算するだけだが、ここで二項係数の前計算ができない大きさであることに気づく。NやKが小さめな制約はそういう意味だったのね。a_iにK-1を足して998244353以上になることがあるというのが気持ち悪いが、単に答えが0になるだけで正常に計算できそうなので提出、WA。番号1の個数から引き算してオーバーフローするのをうっかりした。
あー、これひょっとして、しまい方が0通りでなくてかつ答えが0になることはないのか。
D - Concatenate Subsequences
xの長さが1のときは簡単。長さ2のときも頑張って考える。すると、数列aの前半から選ぶものは貪欲に最小で一番左のものを取っていった列（bとする）の前から連続していくつか取ったものになると気づく。計算量が2乗になってしまいそうだが、ここで都合のいい性質がないか調べると、さっきの列bは構成の仕方を考えると値が切り替わるときにその直前の値はbを構成したときの位置で使うとしていい（違う位置に同じ値があったらそこでbに入れてるので）（説明が難しすぎる）。また、同じ数が続いたときは、長さ1のケースが最小ならそうするので、そうでないときは相手が自分より大きいので全部使うとしていい。そもそもbは広義単調増加。今思うと長さ1のときだけ場合分けすればよかった。ここまでの考察が複雑なうえに、同じ値毎に区切って処理するのも大変。先頭以外で同じ数が続いたときの相手の6,7,8と6,6,6と6,4,5の違いとかもある。解けない問題ではないのだが、脳がスタックオーバーフローする。書き切るところまでは行ったが、残り数分で小さなミスを直せなかった。考え方は間違っていなかったようなのでよかったが、しかしこんなにしんどい実装しか思いつかないようでは力不足ということなのだろう。
