ALGO ARTIS プログラミングコンテスト2023 秋 （AtCoder Regular Contest 168）

　Bまで二完。Cは方針はあっていたので悔しいが、こういうのを詰めるの時間がかかってしまうんだよなぁ。

コンテストへのリンク

コンテスト後のツイート

ALGO ARTIS プログラミングコンテスト2023 秋 （AtCoder Regular Contest 168） Bまで。
A 各">"*nについて考えればOK。
B 総xorが0でないときは-1。あとは、k+1で割った余りのxorを考える。
C 交換するAの位置を決め、そこと交換するB or Cを決め、残りのB/Cの交換を行う、とやったが答えが合わない。

— titia (@titia_til) November 19, 2023

C - Swap Characters

　自力AC。コンテスト中に書いていたコードをもう一度眺めてみたらどこを修正すれば良いか分かった。

　まず、A、B、Cの個数だけ見れば良いことは分かって、その上で、

・"A"を何個交換するか決める（aとする）。さらに、"A"と交換する"B"の個数を決める（bとする）。このとき、"A"と"C"の交換する個数はa-b個。

　これで"A"と何かを交換するのは終了。

・元々"A"があった位置にある"B"、”C"内で交換する必要はない（どの位置と交換するか選べるので）。ただ、元々"A"があった位置にある"B"や"C"の個数を増減させたいことはあるので、何個増減させるか決める。

・あとは、今までで交換していない"B"と"C"の交換を考えればOK（他のものについては、交換した後の場所で自由に動かせる）。それらを何個交換するか決める。

　この手順で探索して、各ステップで「何個ある中から何個選ぶのか？」を二項係数で書いた掛け算していく。それだけといえばそれだけなのだが、手順が複雑だと時間がかかってしまう。

D - Maximize Update

　解説放送を見てAC。

　コンテスト中、区間DPか？　とは少し考えたけど、具体的にどうやれば良いかは全く分かっていなかった。言われればなるほど、という感じではあるけど、判定問題もそう簡単に解けた気はしないので、Cに集中して正解か。