初心者必見！40代サラリーマンが競プロでPythonチャレンジ【ABC313_A-C問題】

こんにちは、こんぶちゃ(茶コーダー)です！

初心者視点から競プロAtCoderのABC313のA問題〜C問題の自身の解答と解答説明をしていきます。

こんな人にオススメしたい

競技プログラミング初心者で、問題の解き方がわからない方
AtCoderの公式解説は読んだが、内容が理解できなかった方
Pythonでの解法を知りたい方

まだまだ学習の身ですので、最適コードではない部分も多々あるかと思いますが、その部分は同じ学習者として温かい気持ちで応援＆ご助言頂けば嬉しいです。

では早速行ってみましょう！

今回使用している機能・アルゴリズム

DFS (深さ優先探索)　　　　　　　・・・　問題B

今回の参加コンテスト(ABC313)
感想

今回の参加コンテスト(ABC313)

AtCoder Beginner Contest 313

A問題：To Be Saikyo

A – To Be Saikyo

問題(要約)

人１がN人の中で最強になるためには、プログラミング力をいくつあげる必要があるか

解答

# 番号1
n=int(input())
P=list(map(int,input().split()))

# 番号2
P1=P[0]-1
ans=0

# 番号3
for i in range(1,n):
    ans=max(ans,P[i]-P1)

# 番号4
print(ans)

考え方 (下の番号は、コード内のコメント番号と連携している)

P1と Pi を比較し、その差が一番大きな値を出力する。ただし、他の人より1 抜き出る必要があるため、P1 の値をあらかじめ 1 引いている

以下、プログラム内容詳細

入力 n, P を受け取る
- n: 整数型で受け取る
- P: 整数型に変換し、リストで受け取る
人1 (P1) とプログラミング力の差を格納する ans (初期値 0) を用意する
＊ P1 は、あらかじめ 1 を引いておくことで他の相手より1分抜きに出ることができる
P1以外の人をfor文で順次とりだす。range範囲を1からにする
- P[i] – P1 を行うことによりそれぞれの人に対して必要なプログラミング力を求められる
- 現行のansとmaxをとることにより、最大で必要なプログラミング力がわかる
ansを出力する

B問題：Who is Saikyo?

B – Who is Saikyo?

問題(要約)

N人の競技プログラマーがいる。プログラマー間には強さの関係性がある。また、強さは推移律が成り立つ。つまり、３人組 (人X, 人Y, 人Z) に対して次の条件が成り立つ

人X が人Y よりも強く、かつ人Y が人Z よりも強いとき、人X は人Z よりも強い。

M個の強さに関する情報が与えれる時に最強のプログラマーを特定することができるか

解答

# 番号1
import sys
sys.setrecursionlimit(10 ** 8)

# 番号2
n,m=map(int,input().split())

# 番号3
g=[0] + [list() for _ in range(n)]

# 番号4
for _ in range(m):
    a,b=map(int,input().split())
    g[a].append(b)

# 番号5
def dfs(pos,visited):
    if visited[pos]==0:
        visited[pos]=1
        for nex in g[pos]:
            dfs(nex,visited)

# 番号6
for i in range(1,n+1):
    # 番号6-1
    visited=[0] * (n+1)
    dfs(i,visited)
    
    # 番号6-2
    if sum(visited)==n:
        exit(print(i))
# 番号7
print(-1)

考え方(下の番号は、コード内のコメント番号と連携している)

大枠としては、有向グラフに置き換えて、深さ優先探索(DFS)を用いて解く

強さ関係情報を有向グラフとして置き換える
深さ優先探索 (DFS) を適用する
特定番号からスタートした場合に全てのノード (人) に訪問できれば、最強が明確
上記でスタート地点の特定番号が最強となる (グラフの根部分)

以下詳細

DFSは再帰を用いるため、再帰の制限を広げておく。
（再帰を用いる時のおまじないだと思っています。詳細理解はおいおい・・・）
入力 n, m を受け取る
- n, m: 整数型で受け取る
有向グラフを作成するために、各地点の接続先を格納する2次元変数 g を準備する
＊与えられた番号が 1 始まりのため、g[0]には 0 を代入する
入力 a, b を受け取り、g に登録する
- a, b: 整数型で受け取る
- a が b より強いため、ノード a からノード b の接続を設定する
  ( g[a].append(b) )
深さ優先探索 (DFS) を定義する
- 引数には、現在位置 (pos) と訪問先リスト (visited) を渡す
- 現在位置か訪問済みかを確認する
  - 未訪問だったら、訪問先リストを更新する(visited[pos]=1)
  - 接続先リストの次の接続先を調べる
    ( for nex in g[pos] 部分、nexは次の接続先になる)
  - dfsに次の接続先、訪問先リストを渡しDFSを実行(再帰)
全てのノード(人) からスタートをさせて、DFSを実行する
1. 人番号は1スタートのため、for文は、1スタートにしている
  - 訪問先リストを設定する (人の数+1、初期値は全て0)
    ＊ for文の中で設定することによりスタート地点毎にリフレッシュ
  - スタート地点のi, 訪問先リストを引数として、dfsを実行
2. 全ての訪問先を訪れた場合、つまり、sum(visited) == n になっているかを確認する
  ＊未訪問は 0, 訪問時は 1 に設定している
  - 上記の条件を満たす場合は、最強プログラマーが明確なため、スタート地点の番号 i を出力し、プログラムを終了させる
最強プログラマが見つからなかった場合は、 -1 を出力させる

C問題：Approximate Equalization 2

C – Approximate Equalization 2

問題(要約)

整数列 A において、下記の操作を好きな回数実施することができる

1≦i, j≦N を満たす整数 i, j を選ぶ。Ai を1減らし、Aj を1 増やす

Aの最小値と最大値の差を 1以下にするために必要な最小の操作回数を求める

解答

# 番号1
n=int(input())
A=sorted(list(map(int,input().split())))

# 番号2
sumA = sum(A)

# 番号3
B=[sumA//n if sumA%n < (n-i) else sumA//n+1 for i in range(n)]

# 番号3 (補足)
"""
B=[]
for i in range(n):
    if sumA%n < (n-i):
        B.append(sumA//n)
    else:
        B.append(sumA//n+1)
"""

# 番号4
cnt=0

# 番号5
for i in range(n):
    cnt+=abs(A[i]-B[I])

# 番号6
print(cnt//2)

考え方(下の番号は、コード内のコメント番号と連携している)

Aを操作した後の最終形を先に求め、その差分の回数を求める

Aを昇順に並び替える。数が大きい方を最終形の数が大きい部分と合わせるため
最終形Bを作る。Aの合計値の個数で割った商とその余りから求める
- 入力例１の場合）
- A=[4, 7, 3, 7]の場合、合計値 21。配列の個数は 4つ
- 商: 5, 余り: 1 より、B=[5, 5, 5, 6] とする
- Aを昇順にすることにより B[-1]=6 に当たるのがA[-1]=7に当たる
  ＊加減する回数が少なくすむ
A, B それぞれの差分を合計し、半分にした商が解答となる
（1回の操作が、増加と加減がセットであるため）

以下詳細

入力 n, A を受け取る
- n: 整数型で受け取る
- A: 整数型のリストでそれぞれ受け取り、昇順に並び替えを行う
入力Aの合計値を求め、sumAに代入する
＊次の配列Bの作成に毎回sum(A)をするとTLEになる(毎回計算になるので)
最終形の配列Bを作成する
- 内包表記を用いて1行で作成
  (使ってみたかった。スッキリ描けるのですが、慣れるまで時間はかかりそう）
- 内包表記の内容は、分解バージョンを#番号3 (補足)に記載
  - 空のリストBを準備する
  - sumA%n < (n-i) とすることにより、余りの数分を求めている
    ＊配列Bの左側に小さい数、右側に大きい数にするため、n-i を用いている
    - 余りの数分: sumA//2 + 1 入力例1では 6
    - 他の部分： sumA//2 　　入力例1では 5
入力A, Bの差分を記憶する変数cnt を準備する
for文を用いて、入力AとBの同じインデックスのところをとりだす
- 純粋な差分だけを取りたいため、絶対値のabs()関数を用いて引き算をする
cntを2で割った商が求める解答になり、出力する

感想

皆さん、今週の競プロコンテストも厳しい戦いでした(>_<)

A問題はすぐに解けましたが、B問題では行き詰まり…。問題文から木構造かな？と考えて調べてみましたが、適当なアプローチではうまくいかず、時間だけが過ぎていく有様で、ちょっとヤバかったです(´･_･`)

そこで、B問題は一旦棚上げして、C問題に挑戦。しばらく考えた後に解けそうな予感がしてコードを書き上げ提出しました(＾▽＾)期待に胸が膨らみながら結果を待つも、惜しくも不正解。がっくり(´；ω；`)

何度か修正を試みましたが、なかなか正解に辿り着けず、時間が刻々と過ぎていきました(´﹃｀)

A問題しか解けていないと焦りながら、先延ばしにしていたB問題に再チャレンジ。過去に解いた有向グラフ＋DFSの考えが思い浮かび、急いでコードを書き上げ提出。。。やっと正解！！やったーヽ(＾Д＾)ﾉ

B問題まで時間がかかってしまったので、結果はあまり良くなかったですが、A問題のみは免れたので、気を取り直して次に向けて頑張ります！皆さんも競プロライフを楽しんでくださいね〜ヽ(＾Д＾)ﾉ

それでは、良い競プロライフを〜！(*＾▽＾)／