【ABC333】競プロのA-C問題を40代サラリーマンがPython解説！初心者にもわかりやすく

AtCoder

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

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

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

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

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

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

AtCoder Beginner Contest 333

A問題：Three Threes

A – Three Threes

問題文

1 以上 9 以下の整数 N が入力として与えられます。

数字 N を N 個繋げて得られる文字列を出力してください。

解答

# 整数 N を入力として受け取る
n = int(input())

# N を N 回繋げて得られる文字列を出力
print(str(n) * n)

解き方）

  1. 整数Nを入力として受け取ります。このNは1から9までの整数です。
  2. 受け取った整数Nを文字列に変換するためにstr(n)を使用します。
  3. NをN回繋げてできる文字列を生成します。これはstr(n) * nという式で行われます。例えば、Nが3の場合、”3″を3回繋げた文字列”333″が生成されます。
  4. 生成された文字列を出力します。

B問題：Pentagon

B – Pentagon

問題

以下の図で表される正五角形 P があります。

P の点 S1​ と点 S2​ を結ぶ線分と、点 T1​ と点 T2​ を結ぶ線分の長さが等しいか判定してください。

解答

# 文字列 S と T を入力
S = input()
T = input()

# 文字を数値に変換し、リストに格納
num_S, num_T = [], []
for i in range(2):
    num_S.append(ord(S[i]) - 65)  # 文字をASCIIコードに変換して A (65) からの差を取得
    num_T.append(ord(T[i]) - 65)  # 同様に T についても処理

# S と T の各文字の数値の差を計算
dis_S = abs(num_S[0] - num_S[1])
dis_T = abs(num_T[0] - num_T[1])

# 特別なケースを処理（A から E への移動を 1 とみなす）
if dis_S == 4:
    dis_S = 1
if dis_T == 4:
    dis_T = 1

# S と T の差が異なる場合 "No" を、同じ場合 "Yes" を出力
if (dis_S == 1 and dis_T != 1) or (dis_S != 1 and dis_T == 1):
    print("No")
else:
    print("Yes")

解き方）

各頂点を数字変換し、差分が 1 になっている場合とそうでない場合で判定を行っています。点Aと点Eの部分だけ例外処理を行っています。

  1. 文字列 S と T を入力として受け取ります。
  2. 文字を数値に変換し、num_S と num_T というリストに格納します。ord() 関数を使って文字をASCIIコードに変換し、それから ‘A’ のASCIIコード (65) を引いています。この結果、A=0, B=1, C=2, D=3, E=4 という対応が得られます。
  3. 点 S1 と点 S2 の距離を dis_S に、点 T1 と点 T2 の距離を dis_T に格納します。絶対値を取っているのは、どちらの方向に進んだかに関係なく距離を求めるためです。
  4. 特別なケースを処理します。正五角形の角を移動する際、A から E に移動することは実際には1の距離しか進んでいないとみなされます。したがって、dis_S または dis_T が4の場合、それを1として扱います。
  5. 最後に、dis_S と dis_T の値を比較して、条件に応じて “Yes” または “No” を出力します。特に、dis_S と dis_T がともに1またはともに1でない場合、”No” を出力します。それ以外の場合は “Yes” を出力します。

C問題：Repunit Trio

C – Repunit Trio

問題(要約)

十進法ですべての桁の数字が 1 である整数をレピュニットと呼びます。レピュニットを小さい順に並べると 1,11,111,… です。

ちょうど 3 つのレピュニットの和として表せる整数のうち N 番目に小さいものを求めてください。

解答

# 入力としてNを受け取る
n = int(input())

# レピュニット（1, 11, 111, ...）のリスト
Repunit = [1, 11, 111, 1111, 11111, 111111, 1111111, 11111111, 111111111, 1111111111, 11111111111, 111111111111]

# 求めた整数を格納する集合を初期化
ANS = set()

# 3つのレピュニットの和を計算して、集合に追加
for a in Repunit:
    for b in Repunit:
        for c in Repunit:
            ANS.add(a + b + c)

# 集合を昇順にソートし、N番目に小さい整数を出力
print(sorted(ANS)[n - 1])


解き方）

入力例3より、今回の制限の中では、12桁が最大であることがわかります。12桁分のレピュニットを準備して、集合を用いて解いています。

  1. n を入力として受け取ります。これは求める整数の順番を表します。
  2. Repunit というリストには、1, 11, 111, 1111 などのレピュニットが含まれています。これらは、10進法の整数で全ての桁が1で構成されています。
  3. ANS という空の集合を初期化します。この集合には、3つのレピュニットの和として表せる整数が格納されます。
  4. 3つのレピュニットの和をすべて試すために3つのforループを使用します。これらのループは、3つの異なるレピュニットを選択し、その和を計算します。
  5. 和を計算した後、ANS 集合にその値を追加します。ここで集合を使用することで、重複する値を排除できます。
  6. 最終的に、ANS 集合を昇順にソートし、N番目に小さい値を出力します。N-1 は0から始まるインデックスなので、sorted(ANS)[n-1] でN番目の値を取得しています。

感想

C問題まで解けました！解法は少々力技に頼った感が否めませんが、「力も実力のうち」と自分を励ますことにします。^^;

A問題は、与えられた数字を桁数分だけ繰り返すというシンプルな問題でした。コンテスト中はリストを使って解決しようとしましたが、余分なスペースの削除に手間取ってしまいました。振り返って解いてみたら、文字列x繰り返し回数 で簡単に解決できました。

B問題は、正五角形の与えられた点を数字化し差分で判断しました。点Aと点E部分の例外処理などを行いつつ回答まで辿り着きました。もっとスマートな解法があったかもしれませんが、ともかくゴールにたどり着けてホッとしています。

C問題には少し時間がかかりましたが、問題の趣旨を理解し、自ら予め用意したリストを駆使して解答へと辿り着きました。少し乱暴な解法だったかもしれませんが、柔軟な思考でクリアできたことを喜びたいと思います。

Ratingは少しだけ上がりました(553点)。D問題まで解かないと劇的な上昇は難しいのではと思い始めていますが、来週も引き続き頑張ります！

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

コメント

タイトルとURLをコピーしました