春告げ鳥

興味のあることをごちゃ混ぜで書いているので、.カテゴリー別に閲覧することをオススメします

AOJ1193 - Chain Disappearance Puzzle

ICPC 国内予選の問題が今の自分はどれぐらい解けるのか気になり、去年の問題を眺めていたら解けるのは解けるのだけど、あまり美しくない解き方しか思いつかない問題があったので考察してみました。

ICPC 2014 国内予選のProblem B「Chain Disappearance Puzzle」という問題です。

Chain Disappearance Puzzle | Aizu Online Judge

問題概要

N×5のマス目があり、それぞれ1~9の数字が書かれている。
横向きに数字が3つ以上揃うとその数字は消え、消えたマスには上の数字が落ちてくる。
(パズドラとかぷよぷよとかイメージするといいかも

最終的に消えた数字の和を答えなさいという問題です

考察

この手の問題はシミュレーションと呼ばれます。
最初問題文読んでうわぁって思いました。
というのも、下に落ちるの考えるのって結構面倒臭いんですよね。
2行同時に消える列があると列全体を2つ下ろさなければいけないし、でも綺麗な解法が思い浮かばなかったので結局思いついたとおりに書きました。
形としては、

  1. 入力
  2. 3つ以上揃うところを足していって、0で上書きする
  3. 下からループしていって、0を見つけたら上に向かって0以外の数字を探して交換する
  4. 合計が変わるまで2と3をループする
  5. 合計の出力

実際に書いたコード

後の考察

他の人のソースコードを見ていると結構自分と同じやり方でやっている人がいて、意外でした。(冗長すぎると思っていた
ただ、自分の場合はこういうソースコード書いた時点でバグが多発して"オンラインプログラミングコンテスト""オンラインデバッギングコンテスト"になりかねないので、少なくとも落ちるところの処理を簡潔にしたいなぁと探していたらclimpetさんがいいソースコード書いていました。

書いたコードでは配列に数字を格納していましたが、C++にはvectorとかいうイケメン配列(個人的なイメージです)があり、それを使ってうまく解かれていました。

fill(remove(v[j].begin(), v[j].end(), 0), v[j].end(), 0);

どうもvectorの属しているSTLにはremoveという「指定した値を取り除いて、勝手に切り詰められる関数」があるようです。
切り詰められたあとの余った領域には余計な値が残っているので、fillで残った箇所に0を入れていかにも重力で落ちたようにシミュレーションをしているようです。

5 5 4 4 3 (4を取り除く)
5 5 3 ? ? (残ったところを0で埋める)
5 5 3 0 0

あと他にもあらかじめ消滅させる場所を記憶させておいて数え上げるなどを参考にして書き直しました。
repとか意気って使った。