Atcoder Beginners Contest 123 解いてみたかった【Python3】

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

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

123-A: Five Antennas

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

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

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

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

https://atcoder.jp/contests/abc123/tasks/abc123_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
k

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() という表記があるそうです。頭パンパンなので実行時間で詰まるようになってきたらまた読みます。

123-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)  # 解答を出力

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

123-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)で割った商を繰り上げた分だけ、移動が余計にかかる

123-D: Cake 123

AtCoder 洋菓子店は数字の形をしたキャンドルがついたケーキを販売しています。

ここには 1, 2, 3 の形をしたキャンドルがついたケーキがそれぞれ、X 種類、Y 種類、Z 種類あります。それぞれのケーキには「美味しさ」という整数の値が以下のように割り当てられています。

• 1 の形のキャンドルがついたケーキの美味しさはそれぞれ
• 2 の形のキャンドルがついたケーキの美味しさはそれぞれ
• 3 の形のキャンドルがついたケーキの美味しさはそれぞれ

高橋君は ABC 123 を記念するために、1, 2, 3 の形のキャンドルがついたケーキを 1 つずつ買うことにしました。そのようにケーキを買う方法は X × Y × Z 通りあります。

これらの選び方を 3 つのケーキの美味しさの合計が大きい順に並べたとき、1, 2, …, K 番目の選び方でのケーキの美味しさの合計をそれぞれ出力してください。

流石に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])

感想

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

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