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つ下ろさなければいけないし、でも綺麗な解法が思い浮かばなかったので結局思いついたとおりに書きました。
形としては、
- 入力
- 3つ以上揃うところを足していって、0で上書きする
- 下からループしていって、0を見つけたら上に向かって0以外の数字を探して交換する
- 合計が変わるまで2と3をループする
- 合計の出力
実際に書いたコード
後の考察
他の人のソースコードを見ていると結構自分と同じやり方でやっている人がいて、意外でした。(冗長すぎると思っていた
ただ、自分の場合はこういうソースコード書いた時点でバグが多発して"オンラインプログラミングコンテスト"が"オンラインデバッギングコンテスト"になりかねないので、少なくとも落ちるところの処理を簡潔にしたいなぁと探していたら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とか意気って使った。
NYC2015 - A問題
塾とAtCoderの定期開催の時間が絶妙に被っていてなかなか参加できなかったのですが、年末年始は塾がお休みだったのでNew Year Contestというのに参加しました。
AtCoderは順位表がリアルタイムで変わるので、競技している感が出ていいのですが、
早い人はA問題1分程度で解いていて、自分は30分ぐらいかかってしまうのでA問題ぐらいはなんとかしたいなぁと復習を書くことにしました。
A 2015
問題概要
2015というタイトルの問題です。いや～去年はいろいろありましたね。
この問題は、与えられた数字を二進数に変換してその数字列が回文*1であるかどうかを調べなさいという問題です。
考察
後で強そうな人のソースコードを見てみた限り、二進数に変換せずに回文かどうか判定する方法はなさそうなので
1.二進数に変換する
2.回文かどうかチェックする
というまあやるだけみたいな問題ですね。
(やるだけに30分もかかってしまってつらい
実際に書いたコード
後の考察
進数変換とかまともに勉強したことないので他の人を参考にしながら書いてみました。
これが自分の中で一番気持ちいいコードです。
ビット演算とか使ったことないので新年記念に
前のコードだと、どこからどこまでループを回すかというところを考えながらやる必要があったのでそれだけで時間が取られてしまうのですが、後のコードはループを出来るだけ使わずに関数に任せているのでその分デバッグがしやすいという利点があります。
普段からプログラムを書いていてもいかに早く書き上げられるかというのはあまり意識しないので、そういった意味で競技プログラミングはいい勉強になります。
*1:左から呼んでも右から呼んでも同じ文字列
