【ABC339】緑コーダーの競プロ参加記録 #1
note初投稿です。
noteで記事を書くに至った経緯はまた別の機会にじっくり書きたいなぁと思っていますが、競プロの観点で言うと「数学的正しさより雰囲気のつかみやすさを優先した灰コーダー茶コーダー向けの記事があったらなぁ」と自分が茶コーダーの頃に思っていたのがはじまりです。
さっそく行きましょう。
今回はAtCoder Beginner Contest 339。使用言語はPythonです。
【解説】 A問題 - TLD
コンテスト中の提出https://atcoder.jp/contests/abc339/submissions/49918224
文字列 S が与えられる。
文字列 S は「長さ 2 以上 100 以下」かつ「'.' が1つ以上含まれる」。
'.' で分割したときの末尾の文字列を出力してね。
ABCのA問題では、プログラミング言語の基礎的な処理を問われることが多いです。この問題も例にもれず、入力・出力、forループ、if文の使い方が問われています。
まずは入力と出力から見ていきましょう。
Pythonではinput関数を利用することで入力を受け取ることができます。そしてinput関数は入力1行をまるまる文字列として受け取ります。今回は与えられる値が文字列 S の1つだけなので単純にinput関数を呼ぶだけでOKです。
出力はprint関数を利用します。ABCではprint関数で出力された値をユーザーの答えとして扱うので、必要以上にprint関数を実行して不正解にならないよう気を付けましょう。
問題によっては文字列のほかに、整数、リストとして入力を受け取りたいことも多いです。いずれのケースでもinput関数で1つの文字列として受け取ることからスタートする点で変わりはありません。
受け取り方がピンとこない場合は「文字列を数値に変換する方法」「文字列を空白区切りでリストにする方法」を考えてみるとよいですね。
# 入力を受け取る
S = input()
# 問題を解く処理
# 答えを出力
print(ans)公式解説ではforループを使用して「文字列Sの中で最も後ろにある '.'」を探して「それより後ろの文字を1文字ずつ出力」して答えを出しています。Pythonにおける「1文字ずつ出力」はちょっとややこしいので答え用の変数 ans を用意して「1文字ずつ連結」することにします。
# 入力を受け取る
S = input()
# 問題を解く処理
N = len(S)
start = 0
for i in range(N):
if S[i] == '.':
start = i
ans = ''
for i in range(start + 1, N):
ans += S[i]
# 答えを出力
print(ans)(2行目) input関数で入力を受け取る。
(5 - 7行目) N を文字列 S の長さとしてforループをＮ回まわし、前から1文字ずつ文字を見ていきます。「文字列 S の i 番目」を参照する方法は S[i]です。（ i は0からスタートすることに注意しましょう）
(8 - 9行目) '.' が現れるたびにその位置 i を変数 start にメモしておきます。今回は「一番後ろの '.' の位置」が知りたいので変数 start の値を上書きして問題ありません。
(11行目) 変数 start は「一番後ろの '.' の位置」なので、その1つ次の位置から1文字ずつ文字を見ていきます。ループの始点が変わっただけで、7行目と内容的には同じです。
(12行目) 答えを記録する変数 ans に1文字ずつ連結。Pythonでは文字列を '+' 演算子で連結できます。 ans += S[i] は ans = ans + S[i]と同じ意味です。
(15行目) print関数で答えを出力。
これを提出するとACです。
なお「1文字ずつ出力」する方法は以下の通りです。
for i in range(start + 1, N):
print(S[i], end = '')余談ですが、実はPythonにおいて '+' 演算子で文字列を連結していると非常に時間がかかるケースがあります。高速に文字列を連結する方法については次のB問題で触れますが、文字列の出力パターンはいくつか知っておくとよいですね。
さて、この問題にはもっと楽で便利な解法が存在します。
上で少し触れた「入力をリストで受け取る方法」に関連しますが、Pythonには「文字列を特定の文字列で区切ってリストに変換する」split関数なるものが存在します。
# 入力を受け取る
S = input()
# 問題を解く処理
S_list = S.split('.')
ans = S_list[-1]
# 答えを出力
print(ans)入力例2のように、文字列 S が「translate.google.com」だった場合、S.split('.') は 長さ3のリスト ['translate', 'google', 'com'] になります。リストの一番後ろはインデックスを -1 にすることで参照できます。
また、これを1行にまとめることもできます。
print(input().split('.')[-1])ABCのA問題は競プロに慣れてくると簡単な問題に思えてきますが、意外といろいろなコードの書き方や解法があったりするので、解説を読むと新しい発見があるかもしれません。
【解説】 B問題 - Langton's Takahashi
コンテスト中の提出
https://atcoder.jp/contests/abc339/submissions/49921789
H行W列の真っ白なグリッドを考える。
グリッドはトーラス状である（？？？？？？？？？？）
移動1「現在いるところが白マスなら黒マスに変更して、時計回りに90度回転してから1マス前進」
移動2「現在いるところが黒マスなら白マスに変更して、反時計回りに90度回転してから1マス前進」
最初(1, 1)にいて、上を向いている高橋君がN回移動した後のグリッドの状態を出力してね。
トーラス状って何ですか・・・？（私は初めて聞きました。）
意味不明な用語が飛び出しても大体は問題文に説明があるので何度か読み返してみましょう。要は、右端と左端、上端と下端がつながっているということですね。昔のゲームみたいな挙動です。
この手の設定、250点とはいえB問題にしてはややこしいことを問われているなと感じましたが最近のABCってこんなもんなのかな・・？
まず出力に合わせてグリッドの状態を文字列のリストで持っておきたいところですが、Pythonでは文字列の一部を変更しようとするとエラーで怒られてしまう（イミュータブル）ので、1マスずつ分割して文字のリストのリストでグリッドを管理しましょう。
# NG
grid = ['.' * W for _ in range(H)]
grid[i][j] = '#'
# TypeError: 'str' object does not support item assignment
# OK
grid = [['.'] * W for _ in range(H)]
grid[i][j] = '#'なお、このような二次元リストの宣言時に次のように書くと大変なことになります。H行W列のリストであることは同じですが、簡単に言うと、H個のリストの中身が連動してしまいます。
H, W = 3, 4
# NG
grid = [['.'] * W] * H
# 1か所だけ値を変更したつもりが・・・
grid[0][0] = '#'
for row in grid:
print(row)
# 3か所も値が変更されてしまった
# ['#', '.', '.', '.']
# ['#', '.', '.', '.']
# ['#', '.', '.', '.']さて、公式解説にあるように、グリッドや平面座標を1マスずつ進んでいくタイプの問題では移動する距離を管理した配列を用意すると実装が楽になります。
# 現在位置
i, j = 0, 0
# 向きを表す変数 d
d = 0
# i, j方向の移動距離を表す変数 Di, Dj
Di = [-1, 0, 1, 0]
Dj = [0, 1, 0, -1]
# 移動
i += Di[d]
j += Dj[d]ぱっと見で何をやっているか分かりづらいので図解します。
つまり d を 0 → 1 → 2 → 3 → … と変化させることは時計回り90度回転を表し、d の向きに1マス進むことは現在位置 ( i, j ) から ( i + Di[d], j + Dj[d] ) に移動することを指します。
Di, Dj は長さ 4 のリストなので d = 4 は困ります。すなわち d の値を 0, 1, 2, 3 で周期的にループさせたいので d を増減するたびに d を 4 で割った余りを計算します。周期性は「余り」で表せることがあります。90度回転を4回くり返したら360度回転で元の位置に戻ってくるイメージです。
Pythonは負の値に対する余りの計算をいい感じにやってくれるので反時計回りのとき d を -1 することにしてOKです。
一方でc++は仕様が異なるため公式解説では -1 する代わりに +3 しています。4 で割った余り、いわゆる mod 4 の世界では -1 することと +3 することが同じ意味をもちます。
さて、高橋君の向いている向きを変数 d で管理し、移動距離もリストDi, Dj で管理できたので、あとは移動の規則に従って実際に高橋君を動かしていきます。移動回数 N が最大1000なので素直にプログラムを書いても実行時間制限2 secに間に合います。
forループは単に「N 回移動を行う」ために回すので、高橋君が現在いる位置 ( i, j ) は別に用意しておきましょう。
ここで問題になるのは、このグリッドがトーラス状であるということです。壁に向かって進んだとしても反対側の壁から出てきてループするようにしないといけません。0 → 1 → 2 → … → (H - 1) → 0 → … という風に。
この処理をどう書くかですが「特定の周期で値をループさせる」といえば余りをとればいいんでしたね。H行W列なので、縦方向は H で割った余り、横方向は W で割った余りをとればよいです。
for _ in range(N):
if grid[i][j] == '.':
grid[i][j] = '#'
d += 1
else:
grid[i][j] = '.'
d -= 1
d %= 4
i = (i + Di[d]) % H
j = (j + Dj[d]) % W最後にグリッドの状態を出力をします。リストのリストになっていることに気を付けて、各行の出力が文字列になるようにマスを連結しましょう。joinすると高速です。
他には各行を表すリストをアンパック(*)してprint関数の区切り文字（sep）を空文字に指定する方法もアリです。
# どっちでもOK
for row in grid:
print(''.join(row))
for row in grid:
print(*row, sep='')「余りを利用するなんて知らないよ！」という場合でもif文を多めに書くことでこの問題を解くことができます。余りを利用すると実装が楽になりますが全体の計算量に大きな差があるわけではないですからね。
B問題にはスマートな解法が思いつかなくてもパワープレイで解ける問題がたびたび出題されるイメージがあります。自分自身がタイピングを頑張ることで解けるのであればそれも立派な解法のひとつです。
計算量に関しても同様に、O(N)解法でもO(N**3)解法でも、ACになるならどちらを選んでもOKなんです。
また他の解法として、数学の世界では座標の回転を計算式で表せることを利用します。詳細は割愛しますが、xy平面上で点(x, y)を原点中心に反時計回りに90度回転させると点(-y, x)に移動します。
ABCのC, D問題でたまに役に立ちます。
H, W, N = map(int, input().split())
i, j = 0, 0
di, dj = -1, 0
grid = [['.'] * W for _ in range(H)]
for _ in range(N):
if grid[i][j] == '.':
grid[i][j] = '#'
# 時計回りに90度回転
di, dj = dj, -di
else:
grid[i][j] = '.'
# 反時計回りに90度回転
di, dj = -dj, di
# 余りをとらない方法
i += di
j += dj
if i < 0:
i += H
elif i == H:
i = 0
if j < 0:
j += W
elif j == W:
j = 0
for row in grid:
print(''.join(row))【解説】 C問題 - Perfect Bus
コンテスト中の提出
https://atcoder.jp/contests/abc339/submissions/49925509
最初、0人以上がバスに乗っている（何人？？？）
N 回バス停に停まった。
i 個目のバス停では、客が乗ったり降りたりして差し引き + Ai 人
Ai は負の値なこともある。
今現在、最低でも何人乗っていれば矛盾しないか出力してね。
よく分からないのでとりあえず最初に乗ってる人を0人として、与えられた乗降をシミュレーションしてみます。多分どこかで乗客数がマイナスになるケースがあるんだろうなということが予想されます。
たとえば「5人降りて乗客数が -3 になった」状況を想像してみると「5人降りた記録があるのに実際は2人しか降りてない」とか「無が3人降りた」ような感じになります。
じゃあ足りない分は最初から追加で乗せておけばいいのかな～ということで、乗客数がマイナスになるたびに最大で何人不足するのかをメモしておきます。マイナス幅の最大なので max ではなく min を取って変数 first に保存しておきます。
N = int(input())
A = list(map(int, input().split()))
first = 0
total = 0
for a in A:
total += a
if total < 0:
first = min(first, total)最初の乗客数が0人の場合の最終的な乗客数がsum(A)なので、そこに不足分を足します。不足分 first は0か負の値なので-1をかければOKです。
ans = -first
for a in A:
ans += a
print(ans)以上で解くことができました。
各バス停での乗客数が [0, -3, 5, -3, 7] のようなケースがあったとして「3人不足してる瞬間が2回あるから追加で6人必要なんじゃないの？」という気もしてきます。これは「ある時点での乗客数はその後の乗客数に含まれている」とか「不足が発生するたびに屋根の上にその人数いたことにする」とかイメージするとそうでないことが分かりやすい…かも。
ややオーバーな解法になりますが「最初に乗客がX人いるとき、乗降データに矛盾が生じますか？」という判定問題を考えて、X を二分探索することで解くこともできます。
これは「X人でOKなら (X + 1) 人でもOK」「X人でNGなら (X - 1) 人でもNG」といった単調性を利用した解法です。
# 判定
def is_valid(x):
total = x
for a in A:
total += a
if total < 0:
return False
return True
N = int(input())
A = list(map(int, input().split()))
# 二分探索
ng, ok = -1, 10 ** 15
while ok - ng > 1:
mid = (ok + ng) // 2
if is_valid(mid):
ok = mid
else:
ng = mid
ans = ok + sum(A)
print(ans)二分探索は茶diffレベルの問題で頻出するアルゴリズムです。上のコードのように自分で書くパターンと、Pythonの標準ライブラリbisectを利用するパターン、どちらも実装できるようにしておくと解ける問題の幅がかなり広がると思います。
解説はここまでです。ありがとうございました。
D問題 - Synchronized Players
コンテスト中に解けませんでした！！！
N行N列のグリッドが与えられる。
'#' は壁、'.' は空きマス、'P' はプレイヤー(2人)。
プレイヤー2人の動きは連動。
二人を重ねるための最小回数を出力してね。
Baba Is Youでやったことある操作。BABA ON BABA IS WIN.
N が最大60。怪しい制約。
実行時間も4 secでしたが終了20分前まで気付きませんでした。
何か法則性があるか考えるものの、なさそうだし全探索っぽい。思いついた中で一番いけそうな雰囲気あるのが盤面を頂点としたBFS。盤面といってもグリッドをまるごと使う必要はなくて、プレイヤーの位置だけあればよさそう。これさえ分かればあとはシンプル（？）な最短経路問題。
途中でE問題に行ってたのもあり思いついた時には残り15分。
グリッドの外部判定を楽にするために周囲に番兵を置く。便利なやつ。
N = int(input())
S = ['#' * (N + 2)] + ['#' + input() + '#' for _ in range(N)] + ['#' * (N + 2)]プレイヤーの位置をタプルにしてdefaultdictで操作回数をメモしていくことに。実装がすこし煩雑なもののBFSしながら操作回数をメモするだけ…なのですがバグらせてしまいました。TLEも消えず。
他の人のコードを調べていると、四次元リストを使ってる人もいれば2プレイヤーの座標を整数に変換して一次元で管理してる人も。後者は発想になかったので真似てupsolve。
def convert(pos1, pos2):
(a, b), (c, d) = pos1, pos2
res = a
res += b * N
res += c * N * N
res += d * N * N * N
return resタプル + defaultdictだと4000 msオーバー、このconvert関数を使ったdefaultdictで3000 ms、一次元リストで1000 ms。速度にこんな差が出るとは思ってなかったので勉強になりました。
あとがき
今回のコンテストの結果はABC3完14分でした。順位は3008位、パフォーマンスは1016でレート微増したのでよしとします。
今後もこの熱量で続くか分からないけど、何か書きたいと思ったときに気ままに書くスタイルでいいのかなとも思ってます。
よろしくお願いします。
この記事が気に入ったらサポートをしてみませんか？