ZONE2021

全体的に難しかった(と思ったけどいつもと比べて難しいのは前半だけか)。力不足で全完できない悔しさ。

A - UFO襲来 / UFO Invasion

substrで12通り比較(9通りでいいけど12でもいいのでそのほうが楽)。

B - 友好の印 / Sign of Friendship

Bでここまで難しいことやらせるか。しかも自然な形で求めようとすると逆さになる(UFO視点で斜め下を見る)のでそこも地味に難しい。地面に食い込まないようにmaxとるの最後にしたんで、計算過程では最小値をとっていくところとかその初期値をでかくするところとか混乱しまくった。スピード出したいならこの解き方じゃだめだ。

C - MAD TEAM

5種類を3つに分ける分け方を全探索とかも思いついてはいたけど使い方が見えず。全然解けなくて後回し。二分探索で行けないか探ってみると、N人を順番に見ていってそれまでにK人選んだとき32通りそれぞれについて達成できているかをDPできるので、二分探索できる。こういう簡単なDPを詰まらず書けるようになったのはいいね。ビット演算使えるかはわかんなくて普通にやったけど。

(追記)2人を全探索は、その2人を除いた最大を簡単に計算できないと思っていたけど、除く必要がない。和とかじゃなく最大なので、その2人が最大値を持っていれば3人目が誰でも全体の最大を達成できる。これがわかっていないのが致命的で、32通り前計算して3人ぶん32^3全探索の解法へも行けなかった。また、3人がそれぞれどこの最大値を受け持つか場合分けが要ると思っていたが、3人のうち2人で必ず4種類以上をカバーしている。

D - 宇宙人からのメッセージ / Message from Aliens

似たような問題最近見たね。それはいいとして、同じ文字の削除を、反転や末尾追加の操作毎に行うと誤読し、「取り除く順番によらない」ってどういうことだ1箇所しかないじゃんと悩んでいた。誤読しても答えは変わらない。というか「順番によらない」ので。解説にあるように、削除を最後にやると少し楽だね(自分はfrontとbackの両方で削除処理を書いたので)。

E - 潜入 / Sneaking

かなり読みづらいけど、要するにR*Cの格子点があって縦横に隣り合った2点の間の移動コストが与えられるってこと。ダイクストラやるだけ、と思ったらプログラムが落ちて上移動を読み落としたことにも気づく。落ちたのはRとCをfor文で逆にしていたため。上移動は、コストがiじゃなくて1+iなのが嫌らしい。色々考えたけど、上層を作ってそこへ行くのにコスト1、その世界では上隣(あ、上がかぶった)へコスト1で行けて、元の層へ戻ってくるのはコスト0。

F - 出会いと別れ / Encounter and Farewell

まず立方体を描いた。18次元の超立方体で考えるといいかなと思って。ただ、ちょっと違うか。A_iが追加されると各頂点から辺が1個減る。まあ2個残ればカバーできるんじゃねと思い書くが、これは間違い。18次元だったら18方向をコントロールできないといけない。各頂点から18本の辺が出ているだけならその辺たちを全て見て全域木を求めることができる。必要なのはA_iというよりAがカバーしていない場所。それをいい感じに18個まで選べばいい。なんかORで全ビットが立っていればいいみたいに思って提出するもWA。でも少し考えると全然違ってて、斜めに移動してもそのループから抜け出せないわけで要するに掃き出し。掃き出しに気づいたとき残り2分とかで、さっきのWAの原因に「アホか!」と叫んだ。終了後もやり続け、以前の掃き出しを貼って読んで使って7分ちょい遅れでAC。いやあ。

(追記)noshi基底というシンプルで難しいやつ。UnionFindだけで新しい基底を見つけるたびに全部つなぐやつ(つなぐ辺の数が半分になっていく)。基底を求めて次元を上げていくやつ(つなぐ辺の数が倍になっていく)。それと同じのを、現在張っている空間に0から行くのは使えなくすることで事前に基底を求めずにやるやつ。基底を求めてグレイコードで__builtin_ctz(x)番目の基底でxorしていきN個つなげるやつ。