はじめに
以前と同様、atcoderの400～500点問題穴埋め時のメモに加え、ABC109参加のメモです。
ARC088-D Wide Flip
区間[l - 1, r]を反転させた後、区間[l, r]を反転させると、l - 1番目の1文字のみ反転させることができる。同様に区間[l, r + 1]を反転させた後、区間[l, r]を反転させると、r + 1番目の1文字のみ反転させることができる。ということは、選べる区間の最小の長さKが与えられたとして、左端からN-K個、右端からもN-K個、合計2(N-K)個の要素は自由に0,1を選べる、ということになる。
じゃあ、左端もしくは右端から何番目の要素まで自由に変えられるようにする必要があるかと考えると、真ん中の要素がいくつ連続で同じ文字かを見ればよいという結論に至る。つまり、中央N/2番目の要素から左右にC個が全て同じ要素だとすると、そのC個は変化させる必要がなく、左端から(N-C)/2番目までの要素もしくは右端から(N-C)/2番目までの要素のどれかが自由に0, 1を選べるようKを定めればよい。よって、N - K = (N - C)/2という方程式が出てくるので、これをKについて解いてK = N - (N - C)/2となる。
Cについては、普通に真ん中から見て同じ要素をカウントすればいいのだけど、文字列の長さが偶数か奇数かで話が変わってくるので、少し注意が必要（実際、1度for文回す回数間違えてWAになった）。
ARC064-D An Ordinary Game
まず個数に着目。1個ずつ文字を削除していくゲームなので、負けるときの文字数の法則性を見つけ出せれば、後は逆算して元の文字数から勝者がわかると考えた。じゃあ、負けるときの文字列とは？ってところについては、2パターン考えられる。ひとつはabのような文字数が偶数での負け、もうひとつはabaのような文字数が奇数での負け（この辺り、大体の予想は立ったが、じゃあ本当？っていうところが解説見るまで分からなかった）。では、どういうときに偶数負けパターンになるか？奇数負けパターンになるか？
ポイントはゲームの性質上、先頭の文字と後尾の文字は必ず最後まで残るということ。このことから、先頭の文字と後尾の文字が同じであれば奇数負けパターン、異なるのであれば偶数負けパターンになる。なぜなら、例えばa**b***a*b（*はaとb以外の文字）のように先頭と後尾が異なるなら、必ず*は取り除くことができ、最終的な負けパターンとしてはabかababになる（そうなるように、両プレイヤーがコントロール可能）。どちらになるかは、一意に定まらないが偶数の文字数になることはかわらない。これと同じような考えで、a*b**a*b**a等のように、先頭と後尾が同じ場合は、abaかa*aかababaかのいずれかが最終形になるので必ず奇数の文字数になる。ここまで来れば、上述の通り逆算して元の文字列数からどちらが勝つかはわかる。
どうもゲーム系は苦手意識があったが（未だに「互いが最適に行動を取る」ってことのイメージがつかめてない）、最終的に詰み（負け）となる形を考えて、そこから逆算していくっていう方法が有効そう。
この問題では一発でACを取れたが、根拠の薄い予想がたまたま当たったっていうパターンなので、あまりよろしくない*1。
ARC067-D Walk and Teleport
まず、いくつか移動パターンを考える。
- 西から東へ順々に移動するパターン（テレポートしても町は飛び越えない）。
- テレポートを使って、まだ移動していない町を飛び越え、その飛び越えた町へ行くため東から西へ逆走をするパターン。
- 全てテレポートで移動するパターン。
この中で2の移動パターンは使う必要がない。なぜなら、最終的には全ての町を訪れる必要があるため、逆走しても順方向に移動しても距離は変わらず、町を飛び越すメリットがないから。また、1のパターンはB<A(X[i + 1] - X[i])であればテレポートを使うし、そうでなければ徒歩で移動する。3のパターンは1の条件で、全ての町間の距離がテレポート使用条件に合うなら自動的に適用される。ということで、min(A(X[i + 1] - X[i]), B)を足しこんでいけばよい。
500点問題の中では明らかに簡単なような・・・
ABC 109参加メモ
2018/9/8開催のABC109に参加。4完達成もD問題の実装に時間がかかりすぎたのがよろしくない。
A問題
A*Bが奇数か偶数か。
B問題
setを使って既出かの判定と、前回の文字列の最後の文字と今見てる文字列の頭文字が同じかという判定を行う。
C問題
Xも数列に組み込んでソートしてx[i + 1] - x[i]の最大公約数を求めたが、解説読むとソートなんかしなくても|X - x[i]|の最大公約数でよかった。
D問題
着目しているマスのコイン数が奇数なら隣のマスにコインを1枚ずらし、着目するマスもそのずらした先に移動。逆に、着目しているマスのコイン数が偶数なら何もせず、着目するマスのみ隣にずらす。この操作を左端からジグザグでもグルグルでも何でもいいから順々に全てのマスに対して行えば、目的が達成される。
その理由としては、まず奇数のマスから奇数のマスへコインを一つずらすと両方偶数になる。その上で、ずらし元が奇数、ずらし先が偶数の場合、操作後はずらし先が奇数になるが、直後に奇数になったずらし先に対して操作を行えば、そのマスも偶数になる。この操作を続けていくと、どこかかでずらし元、ずらし先ともに奇数という個所が出てきて、両方偶数になる。もしそのような個所が出てこない場合、最後のマスまでコインが伝搬され最後のマスのみが奇数になる。従って、最適な最終形としては、コインの総枚数が偶数の場合は全てのマスが偶数になり、コインの総枚数が奇数の場合、1つのマスのみが奇数でそれ以外全手のマスが偶数になる。
ただ、いざ実装ってなると、配列のジグザグ操作またはグルグル操作の実装が面倒だなーと億劫になり、結局、既に操作済みのマスか？という情報を記録する配列を別途用意。ずらせるマスを探し、ずらした先の座標を次のずらし元とする作戦を取る。ACだったが実装に時間がかかりすぎた。
おわりに
最近、競プロ関連チラ裏ブログと化しているので、次回はもう少しまともな内容を書きます。
*1:もう少し正確に言うと、予想した負けパターンは、abのような2文字か、abaのような3文字、もしくは最初からabababのようなFirstプレイヤーが取れず負けるというパターンの3種類を考え、最後のパターンだけ（無駄な）例外処理をする実装でACになった。
