トヨタシステムズプログラミングコンテスト2024（AtCoder Beginner Contest 377)に参加しました。
結果
A,B,Cの3問正解でした。 D問題はぱっと考えて解けそうな方法が思いつかなかったので飛ばしてE問題を解くことに。でもE問題はTLEが解決できず結局解ききれなかった。
A - Rearranging ABC
長さ3の英大文字の文字列が与えられるので並べ替えてABCにできるかどうかを判断する問題。
文字列をソートしてABCになるかどうかで判断して解いた。 ABCはたまたまソート済みだけど、別の文字列だったらABCをソートしたものと入力をソートしたものが一致するかどうかで判断すれば解ける。
B - Avoid Rook Attack
8×8のチェス盤にいくつかルークがいる。どのルークにも取られない位置のマスが何マスあるかを答える問題。
チェス盤自体が小さいので8つある行と列それぞれでルークがいるかどうかのフラグを用意して、 64マスそれぞれで同じ行、列にルークがいるかどうかをフラグをもとに判断して、数えていった。
C - Avoid Knight Attack
縦横Nマスのチェス盤が合ってM個ナイトがいる。ナイトの座標が与えられるのでナイトに取られない現在空いているマスの数を答える問題。
Nが最大でなので全マスを個別にチェックしていくのはTLEになって不可能。
なので逆にナイトの位置情報からナイトが移動できるマスの数を数えて（＝全マスの数）から引いた数を答えた。
ナイトの移動先には重複があるかもしれないので、setでナイトの位置とナイトの移動可能なマスの位置を保存して、 setのサイズ＝ナイトの移動可能なマスの数として考えた。
E - Permute K times 2
１～Nを並び替えた数列Pが与えられる。
次の処理をK回行う。
- を
に更新する※i＝1~Nに対して同時に更新する。
K回処理後のPを出力する。
例
処理前：5 6 3 1 2 4
処理後：2 4 3 5 6 1
Kは最大でなのでどうにかして処理を誤魔化して最終結果を取得する必要がある。
遷移の様子を手元で計算してみると、何回か処理することでループすることに気づいた。
各項を独立して考えて、x項目は何回処理するとループするかを検出して、Kからループ周期の剰余を求めると律儀にK回処理しなくても、ループ後に数回残っている処理の何ステップ目を答えれば良いかが計算できる。
上記の方針で実装して提出してみるとTLEになった。最終的にこのTLEが解決できなかった。
ループの検出とループ内の任意の位置の値を簡単に求めるって処理は時々出てくるから問題なく実装できるようになっておきたいなと思った。
