CODE FESTIVAL 2017 qual A
CODE FESTIVAL 2017 qual A - AtCoder
↑のURLの問題を考察した流れを書こうと思います。
結果は3完、ダメでした。
A問題
問題
文字列が与えられるので、先頭が"YAKI"で始まるなら"Yes", そうでないなら"No"を出力せよ。
考察
問題文を読むと先頭4文字のみを比較すれば良いと分かる。
部分文字列を生成する関数とか使っても良かったけどパッと思い出せなかったので、if 文でごまかすことに。
書いている途中に配列外参照が気になったので if 文する前に入力の文字列が4文字以上かを確認した。
こういうエラーに書きながら気付けるようになるのは経験かなぁと思ったりした。
100回位配列外参照すれば勝手に気付くようになりそうなので、そういう部分で苦しんでいる方は頑張って経験を積むと良いと思います。僕は昔こういう部分ですごく苦しんでいました…
if (a = b) とか for (int i = n; i >= 0; i++) とかね。
B問題
問題
n 行 m 列のマス目があり、最初は全てのマスが白い。
各行各列に対して操作を行う。操作は以下の2つ。
ある行のマスの色を全て反転する。すなわち、白なら黒、黒なら白に色を変える。
・ある列のマスの色を全て反転する。すなわち、白なら黒、黒なら白に色を変える。
操作は好きな回数行うことができる。
この時、黒く塗られたマスの個数をちょうど k 個にすることができるかどうか判定しなさい。
考察
こういう問題は、どの行列から順番に操作しても、最終的に同じ行列を操作して反転していれば同じ結果になる、つまり操作の順番は関係ないという事が一般に知られている。
また、同じ行列を複数回反転させても、意味がないことも知られている。
これは操作が可換なことから、一通り操作した後ある行について5回反転させてみることを考えると分かると思う。1回反転した結果と一致する。
実際に操作をシミュレーションしてみる（紙に書いてみる）と、各行列についてどこを操作しても結果が変わらないことに気付く。
■□■□ ■■□□
■■■■ ■■□□ おなじだなあ
■□■□ ■■■■
上記により、行の操作も列の操作も端からやっていくと考えやすいな〜という発想になった。
制約が O(N*M) を許すので、全通りの反転を試して、その結果黒くなったマスの数を記録してゆき、最後に k が生成できていたかを確認するのが解法。
ある反転をした時何マスが黒くなるのかは計算すると分かるので計算する。
C問題
問題
H 行 W 列の行列 A が与えられる。
この行列の要素は小文字アルファベットからなる。
この行列の要素を交換していって、どの行もどの列も回分になるように出来るか判定しなさい。なお交換の操作は何度でも可能である。
考察
ｹﾞｪｯ回文 となったが、がんばる。
操作が何回でも可能なので、まずはじめに脳内で行列内のアルファベットを全て取り出して良い感じに並べていくイメージを作った。
回文系の問題で一つの鍵になるのは、回文の中心点である。
一つの要素について、所属する回文は2種類（その行と列のやつ）のみなので、とりあえず適当な場所に a と置く。
すると回文なのでその水平、垂直の線対称の部分にも a と入る。同様に点対称の場所にも入る。
これで、1つ決めると4つ決まる事が分かった。
この考えを拡張すると、行列を4分割した時左上を決めれば左下、右上、右下も決定する事が分かる。
しかし、回文なので文字列が奇数の時は中心の文字が唯一になる。そのため行と列の遇奇次第で4分割のどこにも含まれない範囲ができる事がわかる。
行も列も奇数だと、中点を含んで十字になる部分のこと。
その部分は1つの行或いは列にしか回分のペアを持たない。
これらを踏まえると、行列はこんな感じになる。
４２４
２１２
４２４
数はそのアルファベットの回文のペアの個数。同じ数字には同じアルファベットが入る。
行列のサイズの偶奇によって十字の部分が存在するかしないかが変わるので、それぞれによって場合分けをする。
左上を埋めていくと４字ずつアルファベットを消費する。十字の部分の中心でない部分を埋めていくと２次字ずつアルファベットを消費する。中心点は１つ消費する。
シミュレーションをしても良いが、計算すれば答えが分かる。
各アルファベットの個数を数えて、4で mod を取る。あまりが3のものは1と2に分けて考える。
D問題
問題
考察
コンテスト中に解けなかった。
コンテスト中は左上から、ある頂点からマンハッタン距離が K の全ての点を見て、ある頂点と同じ色だったら色を変える、という方針でやっていたが、既に決定した左上の方の頂点が後から変更されてしまうせいで WA だったっぽい。じゃあ渦巻きっぽくやっていけばよいのでは？と思ったが渦巻き型に頂点を参照していく実装が出来ず断念。
次にマンハッタン距離が K の頂点を Union-Find で管理して盤面に復元することを考えたが、復元が出来ず断念。
正しい解法は、マンハッタン距離なので45度回転をする。
方法は全ての頂点について point(i, j) -> point(i+j, i-j)
距離 K 以内だと色が同じで良いので、K で各座標を割ると圧縮ができる。
その結果によって敷き詰めをする。この辺りは公式の解説がとても分かりやすい。
実装時に、割った値の偶奇によって塗りつぶす色の判断ができるので mod の計算をしているが、この時負で mod を取りたくないので考え得る最大の j の値を足すことで対処している。まるごと座標が j の最大値分動くイメージ。
とある Redcoder 様のソースを参考にした。
コドフェス行きたいなぁ
