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

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

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

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

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

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

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

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

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

AtCoder Beginner Contest 343

A問題：Wrong Answer

A – Wrong Answer

問題文

0 以上 9 以下の整数 A,B が与えられます。

0 以上 9 以下の整数であって A+B と等しくないものをいずれかひとつ出力してください。

解答

# AとBの和を求める
sumAB = sum(map(int,input().split()))

# 0から9までの数字の中で、A+Bと等しくないものを見つけ、そのうち最初のものを出力する
print(list(x for x in range(10) if x != sumAB)[0])

考え方）

下記の考え方を用いて解いています。

a + b の値(sumAB)を計算
for文を用いて0~9の数字を取得（ここから下記は内包表記を用いて一文に集約）
- ただし、sumABと一致するものは除外
上記のリストの一つ目を出力

コード詳細

input().split()で入力されたAとBを受け取り、map(int, ...)を使って整数に変換します。
sum(...)を使って、変換した整数AとBの和を求め、sumABに代入します。
range(10)で0から9までの整数を生成します。
リスト内包表記[x for x in range(10) if x != sumAB]を使って、sumABと等しくない整数のリストを作成します。
そのリストの最初の要素（[0]）を出力します。

B問題：Adjacency Matrix

B – Adjacency Matrix

問題(要約)

N頂点の単純無向グラフが与えられ、そのグラフの隣接行列が入力されます。各頂点について、その頂点と直接結ばれている頂点の番号を昇順で出力してください

解答

# 頂点の数Nを入力から受け取る
n=int(input())

# N回のループを回して、各頂点について処理を行う
for i in range(n):
    # 頂点iの隣接情報をリストとして受け取る
    lineA = list(map(int,input().split()))
    # 頂点iに直接結ばれている頂点の番号を格納するリスト
    lineANS = []
    # 頂点iについて、他のすべての頂点jが直接結ばれているか調べる
    for j in range(n):
        if lineA[j] == 1:
            # 直接結ばれている場合、頂点jの番号（j+1）をlineANSに追加
            lineANS.append(j+1)
    # 頂点iに直接結ばれている頂点の番号を昇順で出力
    print(*lineANS)

解き方）

問題文では、単純無向グラフ、直接結ばれているという用語で難しく思えてしまいますが、シンプルに、A_i,j が1になっている部分の列番号を行毎に出力すればいいです。

コード詳細

int(input())でN頂点の数を入力から受け取ります。
for i in range(n):で各頂点iについての処理をN回繰り返します。
list(map(int,input().split()))で頂点iの隣接情報をリストとして入力から受け取ります。
空のリストlineANSを用意し、頂点iに直接結ばれている頂点の番号を保存するためのリストを作ります。
for j in range(n):で他のすべての頂点jが頂点iと直接結ばれているかを調べます。
if lineA[j] == 1:で頂点iと頂点jが直接結ばれているかをチェックし、結ばれている場合はlineANSに頂点jの番号を追加します。
print(*lineANS)で頂点iに直接結ばれている頂点の番号を昇順で出力します。

C問題：343

C – 343

問題(要約)

与えられた正整数N以下で、次の2つの条件を満たす最大の数（回文立方数）を求めることが求められています。

ある正整数xが存在し、その立方がK（x³ = K）となること。
Kが10進法で表記した際に回文（つまり、前から読んでも後ろから読んでも同じ数）になること。

具体的には、正整数Nが与えられたとき、N以下でこれらの条件を満たすKの最大値を見つけ出す問題です。

解答

import math

# 文字列が回文かどうかを判定する関数
def is_palindrome(word):
    return word == word[::-1]

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

# Nの立方根の天井関数を計算し、探索する最大の数を決定
num = math.ceil(n**(1/3))

# numから1まで逆順でループを回す
for i in range(num,0,-1):
    # iの立方を計算
    cnt = i**3
    # 計算した立方数がN以下であり、かつ回文であるかを判定
    if cnt <= n and is_palindrome(str(cnt)):
        print(cnt)  # 条件を満たす最大の回文立方数を出力
        break  # 最大のものを見つけたらループを抜ける

解き方）

N≦10¹⁸と非常に大きいため、Nを順番に回文かどうかを確認すると、制限時間超過になってしまいます。この問題においては、x³=K が成り立つ条件も与えられいますので、x³の条件が成り立つかを確認し、その後、回文かどうかを判断することにより制限時間内で回答することができます。

変換用のアルファベットの一覧表を作成
作成したアルファベット一覧表にクエリを適用
変換前後のアルファベットテーブルを作成
変換テーブルを用いて、文字列Sを置換

変換用のアルファベットの一覧表に対して、今回のクエリを適用していきます。

math.ceil(n**(1/3))を用いて、Nの立方根の天井値を求めます。これが探索する数値の上限となります。
is_palindrome関数は、与えられた文字列が回文（前から読んでも後ろから読んでも同じ）であるかどうかを判定します。
for i in range(num,0,-1):で、上限のnumから1まで逆順にループを回します。これにより、大きい数から順に調べることができ、最大の回文立方数を効率的に見つけることができます。
各iについて、i**3を計算し、それがN以下であるかつ回文であるかを判定します。
条件を満たす最大の回文立方数を見つけたら、その数を出力し、ループを抜けます。