読者です 読者をやめる 読者になる 読者になる

競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

ABC#004

ARCもぼちぼち始めていきたいんですがARC4問はわしにはしんどいのじゃ、、、

- A問題「流行」

(http://abc004.contest.atcoder.jp/tasks/abc004_1)

問題概要:
借金を倍返しするのが流行らしいので入力された値の倍の値を出力します。

解法:
倍返しします。

ソースコード:
http://abc004.contest.atcoder.jp/submissions/339429


- B問題「回転」

(http://abc004.contest.atcoder.jp/tasks/abc004_2)

問題概要:
与えられた4*yの盤面を180度回転して表示するというもの。

解法:
入力された文字を逆順に表示していくだけでよい。スペースと改行の扱いには注意。

ソースコード:
http://abc004.contest.atcoder.jp/submissions/339433
B問題まではやるだけなんで書くことがないです。。。


- C問題「入れ替え」

(http://abc004.contest.atcoder.jp/tasks/abc004_3)

問題概要:
カードの入れ替えをします。
ある値i=tのとき、tを5で割った余りのカードとその右隣のカードを入れ替えます。
Nが入力されたらi=1,2,3,,,,Nのときの操作を行います。

解法:
例にもあるのですがi=0,1,2,3,4の一連の動作を行うと、最初の文字が最後にきているのがわかります。
したがってこの一連の動作が6回行われた時、カードは元の状態に戻ります。
なのでNのときとN%30のときのカードは同じ状態ということです。これを利用して計算量を減らせば時間内に間に合います。
ソースコード:
http://abc004.contest.atcoder.jp/submissions/339448
ソースコードは解法のものよりももう少し最適化をしていますが多分実行時間に変わりはないです。

- D問題「マーブル」

(http://abc004.contest.atcoder.jp/tasks/abc004_4)

問題概要:
3個の箱に入ったマーブルを他に箱に分けて箱内の個数を1個以内にしたいっていう問題です。
マーブルを移動させる数を最小にしなければならない。組み合わせ最適化の部類に入る問題だと思います。

解法:
全探索をします。といっても枝刈りが必要です。
まずマーブルがそれぞれ-100,0,100の位置に入っています。
これを他の箱に分散させたとき、明らかに最適解は同じ色のマーブルが入った箱が隣接しています。
マーブルをどの箱に入れるかを決定するとき、端を3か所見つけるだけでよくなります。
また、Rのマーブルの右端とGのマーブルの左端の差は100以内、GとBも同様になるはずです。
この二つをもとに枝刈りをするとループ回数は1800*100*100<10^8で間に合います。
1800っていうのはRの左端の開始地点-900~900です。実際はもっと狭めてもいいです。

ソースコード:
http://abc004.contest.atcoder.jp/submissions/337357
無駄に最適化を繰り返したせいか若干読みづらくなっていますが解法の方針は同じです。