マラソン勉強するぞ！~過去問演習編3~
はじめに
こんにちは、tardigradeです。本ブログでは主に競技プログラミングのマラソンコンテスト(ヒューリスティックコンテスト)についての記事を書いていく予定です。そんなに固い記事を書くつもりはないので、のんびり気楽に読んでいただければ幸いです。
chokudaiコン003を解く！
AHC001も終わって、次のコンテストまでまだ時間がありそうなので、のんびり過去問演習したいと思います。今回は「Chokudai Contest 003」です。
問題把握
- N×Nの正方形ブロックが与えられる
- ブロックは「○」「×」「.」の三種類
- しばらくすると「.」が消されて上にあるブロックが自由落下する
- 「.」は、消滅しない「+」か消滅せず自由落下もしない「-」に置き換えられる
- ブロック消滅後の、残ったブロックについて、連結成分の大きさの最大値を足す
最初に考えたこと
- スコアを計算する関数書くの大変そう
- 連結はUnionFindで管理するのかな？
- 与えられた入力をそのまま出力するのが一番簡単に正の点数を得られる
- 「.」が多くなるように入力が作られるので基本的にはたくさん消したほうがよさそう
1回目のAC
入力を受け取って、それをそのまま出力。スコア関数の計算はとりあえず放置。
1759点。このコンテストはあまり高いスコアがでなさそうですね。
スコアを計算する
貪欲があまり見えないので乱択をしたくなったのですが、その前にまずスコアを計算する関数を書かなければなりません。関数の設計をしてみます(C++で書くことを想定しています)。
- 出力形式に合わせたvector<string>を引数に参照渡し
- 最初に「.」を消す
- 必要なブロックを下に落とす
- 残ったブロックについて、順番にBFSをして連結しているグループを作り、それをUnionFindで管理
- 各UnionFindでもっともグループ内の要素数が多いものを足し合わせ、それをreturn
2,3,4辺りでバグを生むのが非常に怖いです。どのように実装するかもう少しじっくり考えてみます。
最初に「.」を消す
「.」が消えるということは、もともと正方形だったブロックが歪な形に変わるということです。
この歪な形をした図形をそのまま配列で管理しようとすると結構大変そうです。そこで、ブロックが何もない空間を何らかの文字で表すことを考えてみます。こうすることで、配列や文字列の長さを変えることなくブロック消滅後の図形を管理できます。
必要なブロックを下に落とす
これに関しては、よくよく考えるとブロックの落下操作自体は列ごとに独立しているので、そこまで難しくなさそうです。計算を軽くするための工夫はいくつかあるとは思いますが、どれも愚直の域を出ない気がします。
残ったブロックについて、順番にBFSをして連結しているグループを作り、それをUnionFindで管理
ABCのD問題くらいで出そうな難易度。番兵を置いておくと場合分けがシンプルになりそう。UnionFindは無向グラフに対して作るものなので、[i][j]で得られるブロックの頂点番号をi*50+jと定義しておくと実装がスムーズになるでしょうか。
方針が固まったので実装してみます。………できました。多分バグはないと思いますが、手元にジャッジ環境が無いのでほんとに正しいかはわかりません(;・∀・)
2回目のAC
さて、スコアを計算する関数が用意できたので、まずは普通に乱択してみます。より具体的には
- ランダムで一カ所選択
- 選んだ場所が「.」なら「+」と「-」の両パターン試す
- 「変えない」「+に変える」「-に変える」の中で一番良いものを選ぶ
という感じです。
5228点。意外と伸びました。本番だと52位の点数ですが、Unratedのコンテストの順位は全然参考にならないとAHC001で学んだばかりなので何とも言えません。
高速化した先に未来はあるのか
愚直乱択でも意外と点数が伸びることがわかりました。スコア計算の部分の計算量を改善できそうな気はしているのですが、まず実行時間制限の10倍の時間手元で回してみて、高速化がどれほどスコアに影響するのか確かめてみます。
………変わらない！！！テストケース2で試してみたのですが、1点も向上しませんでした。局所解に陥ってしまっているようです。本質的な部分の改善が必要みたいですね。
3・4・5回目のAC
わりと早い段階で収束しているしている感があったので、シンプルに多点スタートにしてみて提出してみます。状態の数は多すぎても少なすぎてもスコアが伸びないので、ちょっと調整。
atcoder.jp↑は10個ver.で5637点。35位相当でした。
6・７・８・9回目のAC
最初からなんとなく感じていたことですが、下のブロックと上のブロックの価値(重み？)ってだいぶ異なる気がします。上ばっか使って改善していると下のブロックを変化させるのが改悪になりやすくなって、すべてのブロックを十分に使えない…みたいな。
下から上へ乱択していく感じに書き直してみて提出します。パラ調整を少々。
5860点。ギリギリ順位表1枚目に乗りましたね。ちなみに時間10倍にして手元で回してみましたが、ほとんどスコアが変わらなかったので、上を目指すにはまだまだ本質的な改善が必要そうです。
その後考えたこと
- 高速化
- 下からビームサーチみたいなことする(ちょくだいさーちでも可)
- 素直に焼き鈍しをする
- スコアの持ち方を変えてみる
- 列ごとで見てみる
1は大して伸びしろがないことを確認済み。2は結局遷移を乱択頼りにするなら今と変わらなそう。3は「焼き鈍しをする」=「DPする」くらいの重みしかないので、結局どうやるかみたいな話になってわからん。4は、今連結成分の最大値だけ見ているけど、平均値も加味して更新したら面白いそうという話。5は列単位で端から貪欲なりDPなりしてみたらどうなるかなっていう。DP苦手なので書ける気がしないけど。
10・11回目のAC
とりあえず、上の考察の4を実装してみます。
- 最大値が更新されたら確定更新
- 最大値が更新されない場合は連結成分の大きさの平均値が上がっていれば更新
- 最大値が下がっていたら更新はしない(焼き鈍し寄りの話になりそうなので安易に触れたくないというお気持ち)
という感じで書いてみました。
5927点。順位表1位とまだ1500点以上差がある…。
そろそろ終わり
今日の深夜からtopcoderのMMがあるので、過去問演習はそろそろ切り上げたいと思います。twwiterで共有されている解法を覗いてみると
- 焼き鈍し
- 列ごとの更新
- ビームサーチ
等の単語が拾えました。
chokudaiさんが言及されていた「追加するのはおじゃまブロック」という話は気づいていたはずなんですが、それが問題に与える影響まで正しく考えられなかったのは普通にミスですね。
下から改善していくという発想は割と初期の方からあったんですが、ビームサーチまで持っていけなかったのは悔しい。「下から改善した方が悪くなっちゃうパターンも考えられるから~」みたいなことを思ってたんですが、これはアルゴの弊害ですかね…。平均で俯瞰してみるという意識を忘れないようにしたいです。
個人的に気になっていたのは得点計算の部分なんですが、提出されたコードを見ていると大体BFSかDFSで、たまにUnionFindを使っている方も観測できました。変な道突っ走ってなくてよかったです…(*´▽｀*)
それでは、そろそろMMに備えたいので、この辺で切り上げさせていただきます。MMの解法も終わったら共有するつもりです。最後まで読んでいただきありがとうございました！
