あるぱかのブログ

AtCoder茶(レート578)

トヨタ自動車プログラミングコンテスト2024#4(AtCoder Beginner Contest 348)

A - Penalty Kick

リンク:A - Penalty Kick (atcoder.jp)

概要:3の倍数のときだけ×を、そのほかのときはoとした長さ Nの文字列を出力してね

空の文字列を用意して起き、1~Nまで順番に走査して3で割った余りが0となったときに×を、それ以外はoを文字列の末尾に付け足していきます。

range(N)だと0~N-1までを走査することになるので、range(1, N+1)とします。

#ABC348 A - Penalty Kick
N = int(input())
#空の文字列
ans = ''
for i in range(1, N+1):
#3の倍数のときだけ×を出す
    if i%3 == 0:
        ans += 'x'
    else:
        ans += 'o'
print(ans)  

提出リンク:提出 #52062289 - トヨタ自動車プログラミングコンテスト2024#4(AtCoder Beginner Contest 348)

B - Farthest Point

リンク:B - Farthest Point (atcoder.jp)

概要: N個の座標が与えられるので、各座標から最も遠い位置にある座標の番号を N行出力してね

 N \leq 100なので全探索しても N^{2}=10,000回の計算で済むため愚直に全探索します。

ユークリッド距離の計算をいっぱいするので関数として定義しておくと楽になります。

一方の座標を固定してもう一方の座標を小さい順に見て距離を計算していく中で最大値を更新します。

もし距離が同じ場合は番号の小さい座標を出す必要があるので最大値を更新する条件に注が必要です。( \geqではなく  \gtを使用)

またプログラムでは少数の扱いが苦手らしいので、距離の計算を本来 \sqrt{(x_1-x_2)^{2}+(y_1-y_2)^{2}}とするべきところ、ルートを取らずに済ませています。

今回は座標の最大値が1000なので2乗のままでも桁数がとんでもないことにはならないので問題ない(はず)です。

#ABC348 B - Farthest Point
def dist(A, B):
    x1, y1 = A[0], A[1]
    x2, y2 = B[0], B[1]
#平方根を取らず2乗のまま扱う
    d = (x1-x2)**2+(y1-y2)**2
    return d
N = int(input())
P = []
#座標の受け取り
for i in range(N):
    x, y = map(int, input().split())
    P.append((x,y))
#一方の座標を固定して
for i in range(N):
    mx = 0
#もう一方の座標を全探索
    for j in range(N):
        if dist(P[i], P[j]) > mx:
            mx = dist(P[i], P[j])
#1-indexedに合わせる
          mx_node = j+1
    print(mx_node)  

提出リンク:提出 #52072957 - トヨタ自動車プログラミングコンテスト2024#4(AtCoder Beginner Contest 348)

C - Colorful Beans

リンク:色ごとに一番まずい物のまずさを比べて一番マシなものを出力してね

概要:C - Colorful Beans (atcoder.jp)

題意の理解にすこし時間がかかりました。

やりたいこととしては

・同じ色の中で味の数値が最小のものを見つける

 →dictを用意して各色の最も不味いときの数値を記録する

・複数の色がある中で上記が最大のものを選ぶ

 →上記のdictの最大値を返す

ということになろうかと思います。

#ABC348 C - Colorful Beans
from collections import defaultdict
N = int(input())
#0で初期化したdictを用意
num = defaultdict(int)
for i in range(N):
  A, C = map(int, input().split())
#初回は味にかかわらず記録
  if num[C] == 0:
        num[C] = A
#2回目以降は記録より不味いときだけ値を更新
    elif num[C] > A:
        num[C] = A
mx = 0
#全色の最マズを並べて一番マシなものを出力
for key in num:
    mx = max(mx, num[key])
print(mx)  

提出リンク:提出 #52081817 - トヨタ自動車プログラミングコンテスト2024#4(AtCoder Beginner Contest 348)

D - Medicines on Grid

リンク:D - Medicines on Grid (atcoder.jp)

概要:二次元盤面に壁や薬があるのでゴールできるか判定してね

二次元盤面の迷路=最短距離=BFSだけなら良かったのですがエネルギーを管理しないといけないのでバグらせ散らかして80分間椅子を温めることに成功・・・

公式解説の解法2の方針で特に工夫もなくやろうとしてたのでたぶんバグをとれてもTLEしてたと思います。

下のように脇道にそれて薬を回収して元の道に戻る、なんかの場合もあり得るなあなんて考えて無駄にごちゃらせたように思います。

この機に二次元盤面BFSの関数準備しようかな、と思いつつ直近で緑diff以下にBFSやDFSを見た気がしないのでたぶんやらないです()

結果

A~Cまで3完22分で4,866位、レート更新して548→559に微増です。