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だけ期待順位が上がる。