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

ferinの競プロ帳

競プロについてのメモ

ABC004を解いてみた

ABC 競技プログラミング

abc004.contest.atcoder.jp

A問題

 入力を2倍して出力する問題です。特に引っかかることもなく成功です。

B問題

 次のように2次元配列を用意して入力元のデータを2重ループ内で入れ替えていきます。

for i in range(4):
    for j in range(4):
        b[i][j] = a[3-i][3-j]

 ここまではパッと思いついだのですが、Pythonのデータ構造についてよく理解していなかったため手間取ってしまいました… mapでこの処理を行おうとしたところmapはPython2系ではリストを返していたものの、Python3系ではmapはiterator objectが返されるようでそのままでは計算対象とすることができないようです。そのため内包表現を利用してリストとして初期化して実装しました。

a = [[i for i in input().split()] for j in range(4)]

C問題

 左側から(1, 2)(2, 3)(3, 4)(4, 5)(5, 6)番目の組を入れ替える処理を5回1セットとして考えると、この処理を繰り返し行うことになります。そしてこの処理を1セット行うと左から1番目を左から6番目の位置に移動させ、残りの数を一つずつ左にずらす処理となります。そのため、この処理を6セット、すなわち30回行うと元の数の並びに戻ります。よって、入力された数字Nの30の剰余を求めてその回数入れ替えの処理を行うことで求めるべき結果を出力できます。

D問題

 まず真ん中の緑をどうやって横に広げていくかを決め、それに合わせて赤と青を一番効率が良い方法で移すのにかかる手数の合計を求めます。(両側に半分ずつ移していくのがおそらく効率が一番いい方法だと思ったのでそれができる場合はその手数、できなければできるだけ目一杯中央まで寄せその後外側に移していくパターンの手数)そして、緑の広げ方の全パターンを試し一番最小のものを出力するという方針で実装しようとしたのですがif文の条件分けなどでこんがらがって考えているうちに2時間経ってしまいました…
 解説を読んだところ方針としては問題なかったようなので実装スピードをもっと上げなければといったところです。

 今回はD問題の途中で2時間が経過してしまいました… B問題に手間取ってしまったのとD問題の実装に時間がかかりすぎたのが主な要因かなーと思います。実装方法を一つずつでも覚えていってスピードを上げていきたいです。今回は紙に書いて値がどのように変化していくのかなどを見ていくのが理解しやすかったので今後は使って行きたいと思います。あとここまで解いていて大体数学的な特徴を見つけて答えを求めているのでもうちょっと競プロらしく探索や動的計画法なども使っていきたいと思います。