AtCoder Beginner Contest 004

 今日も今日とてABC。

結果

 400/400 76:07 17位相当

 

 開始時刻 2017/07/22 14:03:00 提出履歴

A: 流行 - AtCoder Beginner Contest 004 | AtCoder

 0:30(AC)

 やるだけ。早解き成功。

B: 回転 - AtCoder Beginner Contest 004 | AtCoder

 4:42(AC)

 (i, j)成分と(3-i, 3-j)成分をスワップする。

C: 入れ替え - AtCoder Beginner Contest 004 | AtCoder

 14:26(AC)

 5回スワップを6回繰り返すと元の配置に戻るので、N%30に対して解けばいい。下手にN/6の値で条件分岐したりせずに、N%30に落としたあとはマシンパワーに任せた方が良かった気がする。

D: マーブル - AtCoder Beginner Contest 004 | AtCoder

 76:07(AC)

 難しい。

 多分赤→緑→青の順に並べるのが最適で、緑の位置が決まれば最適な赤、青の位置はそれっぽく決まりそうと判断。考えながら実装することにした。

 赤の左端は最適な場所か、それより左にくる(右に持っていく意味がない)ので、(緑の左端)-Rと比較して、より左側のものを選ぶ。青も同様に、最適な左端と(緑の左端)+Gを比較して、より右側のものが左端。

 各色について端点が決まれば、あとはO(1)でその状態にするための移動数は計算できる。ただし、中心を跨ぐ場合と跨がない場合で3通りあるので気をつけないと危ない。移動数の総和を最小のもので更新していき、出力。

 解説見たけどDPでも解けるみたい(でも言ってる意味がわからなかった)。

感想

 割と手応えはあった。とはいえDに時間をかけすぎなので、だんだんにでもかける時間を減らしていきたい。そのためのABC解き漁りではあるけど。