CODE FESTIVAL 2017 qual A
作成日：2017.09.24
カテゴリー：競プロ 参戦記録
目次
コンテスト前の計画
配点が$100-200-400-700-1600-1600$だったので、D問題までの早解きをまずは目指す。
早解きに失敗、すなわちD問題までを40分前後で解けなかったらE,Fのいずれか簡単そうな方に時間をつぎ込む。
コンテスト中
コンテスト開始直後、A問題を見る。さすがに簡単なのでその場で解く。02:48 AC
その後B問題を見るも、すぐに解放が思い浮かばない。
そこでC問題に移る。ここは少し手を動かせば解けそうな感じであるが一旦保留する。
そしてD,E,Fの順に問題文を読んで雰囲気だけつかみB問題に戻る。
戻った時にすぐ解法が見えたので実装。17:37 AC
すぐにC問題に取り組むが、条件判定に少し手間取り時間がかかる。29:08 AC
D問題に進んだが、すぐに解けそうにないこととすでに30分経過していることからE,Fのどちらかを解くことに決める。
Eは面倒そうなのでFに取り掛かる。
直後に貪欲にシミュレーションすると$O(N \; log \: max(a_i))$で解けそうだとひらめく。
しかし貪欲のやり方が間違っていたため、例3が手計算で合わず50分近く時間を溶かす。
手動のシミュレーションのやり方を変えようとしたら、ひらめきが訪れサンプルが合ったので実装。
思いついた貪欲のやり方が正しいことの証明はできていないが提出。91:36 AC
残りの時間はD問題に費やすことにする。
しかし嘘解法を思いついてしまい、そこから抜け出せなくなって時間切れとなる。
コンテスト後(結果)
4完2300点の48位。パフォーマンス3073、新レート2365(+118,highest)。
ただF問題でうまくいかないと分かった方法を何度も繰り返し試すという無駄なことをしていたので、そこは大きな反省点である。
また、D問題では「マンハッタン距離が出てきたならば45度回転してみる」という定番のアプローチを忘れていたので猛省である。
各問題の(軽い)解説
- A : Snuke's favorite YAKINIKU
- B : fLIP
- C : Palindromic Matrix
- D : Four Coloring
- E : Modern Painting
- F : Squeezing Slimes
A : Snuke's favorite YAKINIKU
問題文
問題の言う通りにする。
B : fLIP
問題文
同じ行または列に対して2回以上反転操作をするのは無意味であること(結構よく出てくる気がする)に気付いた上で、反転すると決める行及び列はそれぞれ個数が同じなら結果に影響しないということに気付く必要がある。
その2つに気付ければ、反転する行及び列の個数を全探索してみれば良いことが分かる。
C : Palindromic Matrix
問題文
はじめに与えられる文字の配列は無視してよく、各文字が何回出てくるかが重要である。
条件を満たすように文字を置いていく時に、1つの文字を決めると他の位置の文字が決まることがある。
そのような位置をグループ化すると各グループの要素は1,2,4個のいずれかになる。
各個数を含むグループがいくつあるかは縦横の偶奇によって決まる。
それが分かれば、小さいグループからどの文字に当てはめるかを端数が出ないように決めていけば良い。
D : Four Coloring
問題文
定番である「マンハッタン距離が出てきたならば45度回転してみる」を実行する。
するとマンハッタン距離はチェビシェフ距離(x座標の差とy座標の差のうち大きい方)に変化する。
よって$d \times d$の正方形内に収まるマスは互いに制約を受けないことが分かるので同じ色で塗れる。
そこでマス目全体を$d \times d$の正方形で切ると、すべての正方形は隣接する8つの正方形と異なる色であれば条件を満たすことになる。
このような色の割り当て方は、正方形に新たに1違いの座標$(s,t)$を振った時に$s$の偶奇と$t$の偶奇がともに同じである正方形に限り同じ色で塗ることで達成される。
E : Modern Painting
問題文
人が1人もいなかったら答えが$1$であることは明らかであるので、その場合は以下では考えない。
1人が色を塗り終わった時盤面は2つの箇所に分かれるが、いずれも高々3方向にしか人はいない(状態$P$)。
よって、3方向にしか人がいない時の塗り方を素早く求められれば良い。
4方向のうち人がいない方向の向かい側を$X$とする。
$X$でない位置にいる人が色を塗ると、向かい合った方向にのみ人がいる部分と状態$P$の部分に分かれるが、前者の部分の塗り方は簡単に求められる。
$X$にいる人が色を塗ると、隣り合った2方向にのみ人がいる可能性のある(状態$Q$)部分2つに分かれる。
状態$Q$の部分では、各列及び行において隣り合っている角から一番遠い人のいずれかが色を塗ると決めて問題ない。
この時の塗り方は各方向に$a$人と$b$人いるとすると、左下から上に$a$マス右に$b$マス行く時の行き方と等しい。
これを2つ合わせて考える。
状態$P$において$X$にいる人数を$x$、残りの2方向にいる人数を$y,z$とすると、この場合の塗り方は$\sum_a{{}_{a+y-1} C_{y-1} \: {}_{x-a-1+z} C_{z}}$である。
なぜなら重複なしで数えるためには、2つの状態$Q$のうちの片方は$X$でない方向にいる人がはじめに色を塗る必要があるからである。
実は、先の総和は左下から上に$x-1$マス右に$y+z$マス進むときの行き方に等しい。
これは2つの状態$Q$の部分それぞれで等価だった左下から右上に進む行き方を合成すれば分かる。
以上により状態$P$における塗り方が高速に求められる。
これにより、はじめに色を塗る人を端から順に決めていくことで$O(N+M)$で求まる。
具体的には$0$で初期化した2つの変数$s,t$を持ち、人がいる行(列)にたどり着くたびに以下の操作を行う。
$s$に今まで通過した部分に限った時の塗り方を加算する。
その後、今見ている行(列)の両側に人がいたら$s$を2倍する。
そしてまだ見ていない部分に限った時の塗り方に$s$をかけたものを$t$に加える。
この操作の中で部分の塗り方を求める時は、$X$にいる人から色を塗り始める。
2つの方向においてこのように求めた$t$の和が答えである。
F : Squeezing Slimes
問題文
厳密な証明をしていないので、アルゴリズムだけ紹介する。
はじめは$29$である$n$が正である間以下を繰り返す。
$a_i$で$2^n$より大きいもので隣り合うものをペアにしていく。
この時$2^{n+1}$であるものはないものとしてみなす。
ペアの数と余りの数だけ答え(はじめは$0$)に加え、$a_i = min(a_i , 2^n)$とし、$n$を$1$減らす。
このアルゴリズムに至った経緯を以下で説明する。
スライムを合成すると大きさは大きい方の2倍以下であるから、大きさ$a_i$にするには$log(a_i)$回程度の操作をすれば十分である。
また、各操作後にすべてのスライムの大きさが$1$となると思っても答えは変わらない。
こう思った時、$a_i$は操作をすることで$a_i / 2$以上の値に変化する。
また操作を$a_i$1つに対して行うよりも複数まとめて行った方が明らかに良いのでそうしたい。
2つであれば無条件でまとめられる。
それ以上まとめるためには両端以外が$a_i$をちょうど半分にするような操作にならなければならない。
このような状況を多く作るには$a_i$を2の累乗になるようにすれば良い。
＜(古い記事)
関連
CODE FESTIVAL 2017 qual B (新しい記事)＞
＜(古い記事)