ARC053 A, B, C 考察

ARC053 A - ドミノ色塗り

横 2 マス縦 1 マスを考えると (W - 1) * H 個。縦 2 マス横 1 マスを考えると (H - 1) * W 個。合計して (W - 1) * H + (H - 1) * W を求める。

https://atcoder.jp/contests/arc053/submissions/16052774

ARC053 B - 回文分割

雰囲気で AC した。

回文を構成する文字はすべて偶数か一種が奇数でほかが偶数になる。これを利用して何個の回文に分割すべきかを調べる。まず S の各文字の出現回数を Map で数える。それらのうち奇数回出現するものを数える。これを O とする。 S を O 個の回文に分割しないといけない。 O が 0 なら全体が回文になるので |S| が答えになる。 O が 0 でないとき (|S| - O) / O はひとつの回文あたりの文字数になる。これが偶数なら各回文にうまく割り当てられるので商に中央の 1 を加えたものが答えになる。割り切れないなら回文に長いものと短いものがあるはず。商を 2 で割って切り捨てて 2 を掛けることで短いもの側に割り当てられる個数が分かる。あとは同様に中央の 1 を加えたものが答えになる。

解説の式が簡潔だった。

https://atcoder.jp/contests/arc053/submissions/16053036

ARC053 C - 魔法使い高橋君

これも雰囲気で AC した。 WA 3 回。

各魔法の X の推移を考える。開始位置 L から A 上がって M になり B 下がって R になる。どれもこの山形になっている。これを L と R の関係で分類する。 L < R / L > R / L = R の三種類がある。

右上がり (L < R) の魔法を先に唱えると損する。唱えた後に位置が上がっていしまう魔法を唱えると後の魔法はより高くなってしまうのだから良いことはない。まずは右下がりで目一杯位置を下げてから唱えると良さそうだ。つまり全体の流れとしては L > R → L = R → L < R と唱えるのが良いだろう。

次にそれぞれの部分についてどう呼ぶかを考える L > R のうち何から呼べばいいか。 M - L = A が最も小さいものが良い。唱えたあと (R) で大きく位置を下げられるものがあったとしても中央 (M) が上がりすぎてしまうなら損だ。 A の昇順に並べるのが良いだろう。

L > R を一通り唱えたので L の位置としては底にある。 L = R については唱えたあとの状況は変わらないのでどんな順で唱えても変わらないはずだ。

ここからは上がっていく。ここで何度も WA を出した。改めて考えると L > R のときを左右反転して考えてると良さそうだ。底の L から R の和で考えると最終地点は決まっている。あとはどう並べると M を抑えられるのかだ。逆向きにたどるなら最終地点から底まで下がっていく動きになるので前半部分と同じだ。唱えたあとの位置を抑えられるものがあったとしても中央 (M) が上がりすぎてしまうなら損だ。 M - R = -B が最も小さいもの B の降順に並べるのが良いだろう。

https://atcoder.jp/contests/arc053/submissions/16060681

リングフィットアドベンチャー。最後の光の玉を手に入れた。本当に最後かは知らない。