Zenn
🤥

【AtCoder】ABC399をPythonで解く

に公開
Python
競技プログラミング
AtCoder
tech

1. はじめに

目的

ABCを解くことにより、とにかくRatingを上げていく。

フィードバックして欲しい点

私は競技プログラミング初心者のため、いただいたアドバイスをすぐに理解できず、何度も質問してしまうかもしれません。それでも構わないという心優しい方がいらっしゃれば、ぜひアドバイスをいただけると嬉しいです。丁寧に教えていただけると、とても助かります！

  1. アルゴリズムの選択と最適化
    • 今の実装よりも効率的なアルゴリズムがあるか？
    • 計算量を減らせる部分や、ボトルネックになっている処理はないか？
  2. コードの可読性と整理
    • もっとシンプルに書ける部分はないか？
    • 変数名や関数名が分かりやすいか？
  3. エッジケース・例外処理の検討
    • 想定外の入力でバグが発生する可能性がないか？
    • 競プロのジャッジでWAになりそうなケースがあるか？

注意点

  • 言語はPython(PyPy 3.10-v7.3.12) を使用しています。

2. コンテスト情報

コンテスト名

AtCoder Beginner Contest 399

コンテストURL

https://atcoder.jp/contests/abc399

開催日

2025-03-29(土) 21:00 ~ 2025-03-29(土) 22:40 (100分)

配点

問題 点数
A 100
B 200
C 350
D 400
E 500
F 550
G 675

結果

順位：10001

総合 A B C D E F G
得点 300 100 200 (1)
時間 74:29 8:07 74:29

3. 解いた問題と解法

A: Hamming Distance

コード

N = int(input())
S = input()
T = input()
count = 0

for i in range(N):
  if S[i] != T[i]:
    count += 1

print(count)

解法

条件分岐を用いて、Sのi文字目とTのi文字目が異なった場合に、countに1を加えていく。

改善点

特になし。

B: Ranking with Ties

コード

N = int(input())
P = list(map(int, input().split()))
r = 1
rank = [0]*N

while not all(i == 0 for i in P):
  max_value = max(P)
  count = 0
  for j, v in enumerate(P):
    if v == max_value:
      P[j] = 0
      rank[j] = r
      count += 1
  else:
    r += count
    
for i in range(N):
  print(rank[i])

解法

まず初めに、0がN個のリストrankを作成する。
また、得点Pが最大となるインデックスを全て探し出し、それぞれに対して以下のことを同時に行なう。

  1. 最大となったPをすべて0とする。
  2. インデックスに注意しつつ、rankに順位を代入する。
  3. countの値を、順位を確定させた人数分にする。

そして、得点が最大となった人の順位を全て確定させたら、順位をcountの分だけ増やす。
この処理をPがすべて0になるまで繰り返すことで、1位から順位を確定させる。

改善点

n = int(input())
p = list(map(int, input().split()))
for i in range(n):
  rank = 1
  for j in range(n):
    if p[j] > p[i]:
      rank += 1
  print(rank)

この問題文は以下の形で言い換えることができる。

  • 人iの順位は、人iよりも真に得点が高い人の数に1を足したものである。

よって、自分より点数の高い人の数をループで調べて、その数と+1を足し合わせた値が人iの順位となる。

C: Make it Forest

模範解答のコード

現在研究中

模範解答の解法

与えられたグラフがK個の連結部分C_1,C_2,...,C_iを持つとすると、各C_iは|C_i|-1本の辺を残すことができる。
これをすべての連結成分に適応すると以下の式になる。

\begin{align*} \sum_{i=1}^K (|C_i|-1) &= \sum_{i=1}^K |C_i| - \sum_{i=1}^K 1 \\ &= N - K \end{align*}

ただし、\sum\limits_{i=1}^K |C_i|=(すべての連結成分の頂点の合計)=N
よって元のグラフを森にするための辺の本数の最小値は以下の値になる。

M-(N-K)

あとはKを求めればいい。

  • このアルゴリズムは勉強中です。

D~Gは研究中

現在の私には解くことができません。

4. 他の解法・考察

別のアプローチの可能性

  • 問題Bのように、問題文を別の形で言い換える力は必要になってくる。

計算量や工夫点

  • 問題文に書かれていることを忠実に再現することを意識した。

5. まとめ

今回の気づき

  • 問題C以降の問題では、グラフ理論などの数学的能力とアルゴリズムの知識が求められる。

改善したい点

  • 問題AとBは必ず解くようにする。
  • C問題に挑戦できるように、大学の講義などで数学とアルゴリズムについて学ぶ。

Discussion