AtCoder Beginner Contest 123 解いてみたかった【Python3】

先週から何も知らない状態でAtCoder（競技プログラミングってやつ）に興味本位で取り組んでいます。数学の問題っぽくて楽しいし、これなら続けられそうということで。

ほとんど何も知らない状態でのスタートなので、色々書き方をググりながら解いてますが、記録しとくと後々リファレンスっぽく使えるかな〜ということで記録していきます。Python3で書いてます。

ABC123 A – Five Antennas

AtCoder市には、5つのアンテナが一直線上に並んでいます。これらは、西から順にアンテナ \(A, B, C, D, E\) と名付けられており、それぞれの座標は \(a, b, c, d, e\) です。

2つのアンテナ間の距離が \(k\) 以下であれば直接通信ができ、\(k\) より大きいと直接通信ができません。

さて、直接通信ができないアンテナの組が存在するかどうか判定してください。

ただし、座標 \(p\) と座標 \(q\) \((p \leq q)\) のアンテナ間の距離は \(q – p\) であるとします。

https://atcoder.jp/contests/abc123/tasks/bc123_a

直接通信できないアンテナの組が存在するかどうかだけを判定すれば良いので、一番距離がデカイ e - a について調べれば十分であることが分かります。

こんな答えを書いてみました。ちゃんとACいただきました。

a, b, c, d, e, k = int(input()), int(input()), int(input()), int(input()), int(input()), int(input())
if e - a > k:
    print(":(")
else:
    print("Yay!")

調べた感じ、入力の読み込み方はもっと簡潔にできそうで、

# 入力
a
b
c
d
e

に対して

a, b, c, d, e, k = eval("int(input())," * 6)

としたりとか

a, b, c, d, e, k = [int(input()) for i in range(6)]

とリストにしたりとか、ここだけでもバリエーションがありますね。
まだ自分の経験では最適解が分かっていないので、この辺りの書き方はたくさん知っておきたいですね。

標準入力にも、input() 以外に sys.stdin.readline() という表記があるそうです。頭パンパンなので実行時間で詰まるようになってきたらまた読みます。

ABC123 B – Five Dishes

AtCoder 料理店では、以下の 5 つの料理が提供されています。ここで、「調理時間」は料理を注文してから客に届くまでの時間とします。

・ABC 丼： 調理時間 A 分
・ARC カレー： 調理時間 B 分
・AGC パスタ： 調理時間 C 分
・APC ラーメン： 調理時間 D 分
・ATC ハンバーグ： 調理時間 E 分

また、この店には以下のような「注文のルール」があります。
・注文は、\(10\) の倍数の時刻(時刻 \(0, 10, 20, 30, …\))にしかできない。
・一回の注文につき一つの料理しか注文できない。
・ある料理を注文したら、それが届くまで別の注文ができない。ただし、料理が届いたちょうどの時刻には注文ができる。

E869120 君は時刻 \(0\) に料理店に着きました。彼は \(5\) つの料理全てを注文します。最後の料理が届く最も早い時刻を求めてください。
ただし、料理を注文する順番は自由であり、時刻 \(0\)に注文することも可能とであるとします。

https://atcoder.jp/contests/abc123/tasks/abc123_b

10 の倍数の時刻にしか注文ができないことから、最後の注文以外は 1 の位が繰り上げられてしまってあまり影響しないことが分かります。よって、調べるべきは、この繰り上げが発生しない最後の注文に何が来ればよいかで、 1 の位を比較すればよいわけです。

0 以外の 1 の位の最小を求める際はちょっと考えましたが、-1 倍したものの 1 の位の最小を考えれば良いと分かりました。頑張って慣れないコードに起こしてみます。これもAC。

import math

minutes = [int(input()) for i in range(5)]
m = [math.ceil(minutes[k] / 10) * 10 for k in range(5)]

last = min((minutes[l] - 1) % 10 for l in range(5))  # 最後に注文するやつを決める
last += 1

print(m[0] + m[1] + m[2] + m[3] + m[4] + last - 10)  # 解答を出力

コードテストで色々な書き方を探り探りやっています。

ABC123 C – Five Transportations

AtCoder 社は成長し、2028 年になってついに \(6\) つの都市 (都市 \(1, 2, 3, 4, 5, 6\) ) からなる AtCoder 帝国を作りました！
AtCoder 帝国には \(5\) つの交通機関があります。

・電車: 都市 \(1\) から \(2\) まで \(1\) 分で移動する。\(1\) つの電車には \(A\) 人まで乗ることができる。
・バス: 都市 \(2\) から \(3\) まで \(1\) 分で移動する。\(1\) つのバスには \(B\) 人まで乗ることができる。
・タクシー: 都市 \(3\) から \(4\) まで \(1\) 分で移動する。\(1\) つのタクシーには \(C\) 人まで乗ることができる。
・飛行機: 都市 \(4\) から \(5\) まで \(1\) 分で移動する。\(1\) つの飛行機には \(D\) 人まで乗ることができる。
・船: 都市 \(5\) から \(6\) まで \(1\) 分で移動する。\(1\) つの船には \(E\) 人まで乗ることができる。

それぞれの交通機関は、各整数時刻 ( \(0, 1, 2, 3, …\) ) に、都市から出発します。

いま、 \(N\) 人のグループが都市 \(1\) におり、全員都市 \(6\) まで移動したいです。全員が都市 \(6\) に到着するまでに最短で何分かかるでしょうか？なお、乗り継ぎにかかる時間を考える必要はありません。

https://atcoder.jp/contests/abc123/tasks/abc123_c

例を参考に実験してみると分かりますが、定員の人数が一番小さいところがボトルネックになり、この分だけ移動が余計にかかることが分かります。いわゆる律速ってやつ？全体のスピードを支配している点を発見すると楽になりますね。

スムーズに進む分から、ボトルネック分だけ移動が余計にかかると考え、次のように書いてみました。AC。

import math
N, A, B, C, D, E = eval("int(input())," * 6)  # 入力値を定義
print(4 + math.ceil(N / min(A, B, C, D, E)))  # Nをmin(A~E)で割った商を繰り上げた分だけ、移動が余計にかかる

アルゴリズム自体は考えられたけど、実装知識に乏しいので慣れるまで適切にコードに起こすのが大変…

ABC123 D – Cake 123

AtCoder 洋菓子店は数字の形をしたキャンドルがついたケーキを販売しています。
ここには \(1, 2, 3\) の形をしたキャンドルがついたケーキがそれぞれ、\(X\) 種類、\(Y\) 種類、\(Z\) 種類あります。それぞれのケーキには「美味しさ」という整数の値が以下のように割り当てられています。
1 の形のキャンドルがついたケーキの美味しさはそれぞれ \( A_{1}, A_{2}, \ldots, A_{X} \)
2 の形のキャンドルがついたケーキの美味しさはそれぞれ \( B_{1}, B_{2}, \ldots, B_{Y} \)
3 の形のキャンドルがついたケーキの美味しさはそれぞれ \( C_{1}, C_{2}, \ldots, C_{Z} \)
高橋君は ABC123 を記念するために、\(1, 2, 3\) の形のキャンドルがついたケーキを 1 つずつ買うことにしました。そのようにケーキを買う方法は \(X × Y × Z\) 通りあります。
これらの選び方を \(3\) つのケーキの美味しさの合計が大きい順に並べたとき、\(1, 2, …, K\) 番目の選び方でのケーキの美味しさの合計をそれぞれ出力してください。

https://atcoder.jp/contests/abc123/tasks/abc123_d

流石にD問題は一番難しいのもあって、一人では頭がパンクしてしまいました。慣れたらできそうな気もしますが、友達に思考の整理を助けてもらいつつ解いてみます。

明らかに計算量が膨大になりそうなので、順番に細かくタスクを分割して、なるべく処理を少なくできるよう意識してみます。（結局↓でTLE食らったけど）

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
D = [0] * (X * Y)
E = [0] * (K * Z)
m, n = 0, 0

for i in range(X):
    for j in range(Y):
        D[m] = A[i] + B[j]
        m += 1

for k in range(len(sorted(D)[:: -1][: K])):
    for l in range(Z):
        E[n] = sorted(D)[:: -1][: K][k] + C[l]
        n += 1

for p in range(K):
    print(sorted(E)[:: -1][p])

A + B を先に処理して、K個取り出してからCを足すようにしたのですが、これでもTLEくらいました。計算量抑えるのムズイ。流石にまだそこまで意識を回す暇がねぇな。だれか強い人読んでいたらアドバイスください。

感想

• 知識ほぼ0からでもググりながら粘り強くやればそれなりの成果が出せそう
• とりあえずCまでは頑張ればできることがわかった
• 過去問を解こうと思った
• 受験数学解いてる感覚に似てて楽しい

また解いた問題の感想とか、勉強したことなど時間見つけて書きます。