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

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

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

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

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

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

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

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

順列(permutations) 　　　　　　　　　　　　・・・　問題C

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

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

AtCoder Beginner Contest 319

A問題：Legendary Players

A – Legendary Players

問題(要約)

“AtCoder”コンテストでの上位プレイヤーのハンドルネームとレーティングが提供され、特定のプレイヤーのハンドルネームからそのレーティングを出力する問題です。

解答

プレイヤーのハンドルネームとレーティングを辞書に格納することによりレーティングを呼び出します。

# プレイヤーのハンドルネームとレーティングを辞書に格納
players = {
    'tourist': 3858,
    'ksun48': 3679,
    'Benq': 3658,
    'Um_nik': 3648,
    'apiad': 3638,
    'Stonefeang': 3630,
    'ecnerwala': 3613,
    'mnbvmar': 3555,
    'newbiedmy': 3516,
    'semiexp': 3481
}

# ユーザーからの入力に対応するプレイヤーのレーティングを表示
player_name = input()  # ユーザーからの入力を受け取る
print(players[player_name])  # 入力されたハンドルネームに対応するレーティングを表示

プレイヤーの情報を辞書に格納します：
- 各プレイヤーのハンドルネームをキー（例：’tourist’）とし、対応するレーティングを値として辞書（players）に格納します。これにより、各プレイヤーとそのレーティングの対応が簡単に取得できます。
ユーザーからの入力を受け取ります：
- input()関数を使用して、ユーザーからプレイヤーのハンドルネームを入力するよう求めます。ユーザーはハンドルネームを入力します。
入力されたハンドルネームに対応するレーティングを表示します：
- 入力されたハンドルネーム（player_name）を辞書（players）のキーとして使用し、対応するレーティングを取得します。
- 取得したレーティングをprint()関数を使用して画面に表示します。

B問題：Measure

B – Measure

問題(要約)

与えられた正整数Nに対し、特定の条件に従って長さ(N+1)の文字列sを出力する。

各i（0からNまでの整数）に対して、Nの約数jでiがN/jの倍数である場合、最小のjに対応する数字をsiとし、そうでない場合はsiを-に設定します。

解答

整数Nの約数をリスト化し、条件 i が N/j の倍数であるかを確認していきます。最小の j を求めるために、条件が当てはまったらbreakで抜けるようにしています。

# 整数nの約数を求める関数
def find_divisors(n):
    divisors = []
    # 1から9までの整数で約数を求める
    for i in range(1, 10):
        if n % i == 0:
            divisors.append(i)
    return divisors

# ユーザーから整数nを入力
n = int(input())

# 答えを格納するリストの初期化（最初の要素を1に設定）
ANS = [1]

# 整数nの約数を求める
divisors = find_divisors(n)

# 1からnまでの整数に対して条件を検証
for i in range(1, n + 1):
    for j in divisors:
        # iが(n/j)の倍数である場合、最小のjを答えに追加
        if i % (n / j) == 0:
            ANS.append(j)
            break
    else:
        # 条件を満たすjが見つからない場合、'-'を答えに追加
        ANS.append('-')

# 答えをスペースなしで出力
print(*ANS, sep="")

以下詳細

find_divisors 関数:
- この関数は、整数nの約数（1から9までの整数）を見つけるための関数です。
- divisors という空のリストを初期化します。
- 1から9までの整数（i）に対して、nをiで割った余りが0の場合、iはnの約数であるため、divisors リストに追加します。
- 最終的に、divisors リストを返します。
ユーザーからの入力:
- n に整数としてユーザーからの入力を受け取ります。これは与えられた正整数Nです。
ANS リスト:
- ANS というリストを初期化し、最初の要素として1を追加します。このリストは後で生成される文字列の各文字を保持します。
  i = 0 の場合は、すべての N / (約数) が 0 の倍数になるため、最小値の1をあらかじめ入れておきます。
  倍数：ある整数を別の整数で割ったときに余りがゼロになるような整数
divisors リストの取得:
- find_divisors 関数を使用して、整数nの約数を計算し、divisors リストに格納します。
文字列の生成:
- 1からNまでの各整数（i）に対して以下の処理を行います：
  - divisors リスト内の整数（j）に対して以下の処理を行います：
    - もしiがn/jの倍数であれば、jをANSリストに追加し、ループを抜けます（最小のjが選択されます）。
    - そうでなければ、ループを続けます。
  - 内側のforループが全てのjに対して条件をチェックし終えても、jが選択されなかった場合、’-‘をANSリストに追加します。
- 最終的に、ANSリストの要素をスペースなしで連結して、長さ(N+1)の文字列を生成します。
結果の出力:
- 生成された文字列を表示します。

C問題：False Hope

C – False Hope

問題(要約)

3×3のマス目に1から9までの数字が書かれており、一部の数字は同じ数字が縦・横・斜めに連続していない条件下でランダムな順番で知ります。高橋くんは、次の条件を満たす場合にがっかりします：最初に知った2つのマスに書かれた数字が同じであり、最後に知ったマスに書かれた数字が異なる場合。高橋くんががっかりしない確率を求めてください。

解答

考え方）

9個の数字の順列 9! = 362880 通りを pythonの組み込み関数の permutationで作り、がっかりしない条件の数をカウントし、確率を求めています。

がっかりしない条件の判断を簡略化するために下記の事前準備を行います

マス目の初期配置を1次元化
縦・横・斜めの列の一覧のrowタプルを作成

from itertools import permutations

cells = []
# マス目の初期配置を受け取る
for _ in range(3):
    hline = list(map(int,input().split()))
    cells += hline

# 縦・横・斜めの列の一覧
row = [
    (0, 1, 2),  # 上から 1 行目
    (3, 4, 5),  # 上から 2 行目
    (6, 7, 8),  # 上から 3 行目
    (0, 3, 6),  # 左から 1 列目
    (1, 4, 7),  # 左から 2 列目
    (2, 5, 8),  # 左から 3 列目
    (0, 4, 8),  # 左上から右下
    (2, 4, 6),  # 右上から左下
]

order = list(range(9))  # 0から8までの数字

not_disappoint = 0  # がっかりしない開け方の個数
all_openings = 0  # 開け方の総数

# 順列を使って、9つのマスを開ける順番を生成
for perm in permutations(order):
    all_openings += 1
    disappoint_flag = False

    for a, b, c in row:
        # 条件を満たす場合、がっかりフラグを立てる
        if (
            cells[a] == cells[b]
            and perm[a] < perm[c]
            and perm[b] < perm[c]
        ) or (
            cells[a] == cells[c]
            and perm[a] < perm[b]
            and perm[c] < perm[b]
        ) or (
            cells[b] == cells[c]
            and perm[b] < perm[a]
            and perm[c] < perm[a]
        ):
            disappoint_flag = True

    # がっかりしない場合、not_disappointを増やす
    if not disappoint_flag:
        not_disappoint += 1

# がっかりしない確率を計算して出力
print(not_disappoint/all_openings)

以下詳細

マス目の初期配置を受け取り、それをcellsというリストに格納します。2次元配列ではなく、+=を用いることにより、1次元配列で受け取りしています。
入力例1 ) cells = [3, 1, 9, 2, 5, 6, 2, 7, 1]
　　　　 1行目の左→右、2行目の左→右、3行目の左→右の順番
縦・横・斜めの列の一覧をrowに定義します。これは、条件に合致する列の組み合わせです。たとえば、(0, 1, 2)は上から1行目を示し、(0, 3, 6)は左から1列目を示します。
0から8までの数字の順列を生成し、それぞれの順列に対して以下の操作を行います
1. all_openings（開け方の総数）をインクリメント(1を足す)します。
2. disappoint_flag（がっかりフラグ）を初期化します。
3. 各列について、特定の条件を満たすかどうかをチェックします。条件は次のとおりです：
  - 同じ数字が2つのマスに書かれており、それらのマスを開けた順番（perm）が、残りの1つのマスを開ける順番よりも前である場合、disappoint_flagを立てます。この条件は、がっかりするケースを判定するためのものです。
4. もしdisappoint_flagが一度も立たなかった場合、その順列は「がっかりしない」開け方であるとみなし、not_disappoint（がっかりしない開け方の個数）をインクリメントします。
すべての順列について、がっかりしない開け方の個数not_disappointを開け方の総数all_openingsで割り、確率を求めます。これが、高橋くんががっかりせずにすべてのマスに書かれた数字を知る確率です。

感想

問題の解釈が非常に難解なコンテストでした。

A問題は、辞書型に登録してすぐに回答できました(*＾▽＾)／

しかし、B問題から苦難の始まりでした。質問の意味が理解できず、入力例１の解説を読んでも更に混乱しました(´；д；`)

i = 0 の時にN/jの倍数となっており、0が何かの倍数というのが混乱
(倍数の定義をちゃんと理解できていなかったことが問題ですけど・・・)
入力例1で i = 1 の時に ‘ – ‘ になっていることが理解できませんでした
(約数の制限が1 – 9 のためにハイフンになっています。今だから分かりますけど・・・）

結局、B問題を解くのに、30分かけてようやく回答まで辿り着きました (^_^)

C問題は更に難解で、問題文の意味は難しかったのですが、入力例１が役に立ちました。愚直に解くと膨大な数になるため、組み合わせパターンを検討しましたが、正解まで辿り着かずに時間切れになりました。

苦しい戦いでしたが、C問題の復習と今回の経験を活かしつつ、来週のコンテストに励みます。

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