Help us understand the problem. What is going on with this article?

【競プロ初心者向け】AOJ 「ITP I」40問をpythonで解いてみた

はじめに

本記事では「レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【初級編:競プロを始めよう】」で紹介されているAOJの「Introduction To Programming I」の40問をPythonで解説します。

 僕自身、プログラム未経験で競技プログラミングをはじめました。入門書である「独学プログラマー Python言語の基本から仕事のやり方まで」を読んでから「Introduction To Programming I」に取り組みました。あくまで個人の話ですが、40問を解いたあとにはAtcoderで開催されいているAtCoder Beginner Contest(ABC)で茶パフォが出せるようになっていたので競技プログラミングをするうえでの基本的な知識は身につくのだと思います。

ITP1_1_A Hello World

ITP1_1_A
print("Hello World")

【解説】 printHello Worldを出力します。

ITP1_1_B X:Cubic

ITP1_1_B
x=int(input())
print(x**3)

【解説】 input()は文字列として受け取るのでint()で数値にしてから処理します。

ITP1_1_C Rectangle

ITP1_1_C
a,b=map(int,input().split())
print(a*b,2*(a+b))

【解説】 1行/複数列の入力はinput().split()が利用できます。ただし文字列として受け取るのでmapintで数値にしてから処理します。入力については「AtCoderで始めるPython入門」が参考になります。

ITP1_1_D Watch

ITP1_1_D
S=int(input())
print(S//3600,":",(S%3600)//60,":",S%60, sep="")

【解説】秒数を3600で割った商がhに、秒数を3600で割った余りを60で割った商がmに、秒数を60で割った余りがsになります。h,m,s:+で繋ぐにはh,m,sを文字列にする必要があります。文字列と数値が混じっていてもprintであれば問題なく出力できます。出力については「AtCoderで始めるPython入門」が参考になります。

ITP1_2_A Small, Large, or Equal

ITP1_2_A
a,b=map(int,input().split())
if a>b:
    print("a > b")
elif a<b:
    print("a < b")
else:
    print("a == b")

【解説】言われている通りに書きます。

ITP1_2_B Range

ITP1_2_B
a,b,c=map(int,input().split())
if a<b and b<c:
    print("Yes")
else:
    print("No")

【解説】a<b<cと記述しても問題ありません。

ITP1_2_C Sorting Three Numbers

ITP1_2_C
three_numbers=list(map(int,input().split()))
three_numbers.sort()
print(*three_numbers)

【解説】はじめてlistが登場します。listは複数の要素を含むオブジェクトです。「【Python入門】listの使い方とメソッドまとめ」が参考になります。もし余裕があればtuple、dictについても勉強しておくといいです。リストをソートするには、"list名".sort()もしくはsorted("list名")があります。これらの違いについては、「Pythonでリストをソートするsortとsortedの違い」が参考になります。

ITP1_2_D Circle in a Rectangle

ITP1_2_D
W,H,x,y,r = map(int,input().split())
Flag=True
if x+r>W or x-r<0:
    Flag=False
if y+r>H or y-r<0:
    Flag=False
if Flag:
    print("Yes")
else:
    print("No")

【解説】横と縦でそれぞれ円が長方形からはみ出さないかを確認します。Flagを作成しておき、条件を満たさなくなった時点でFalseにします。最後までTrueであれば、円が長方形に収まり、そうでなければ縦か横のどちらかがはみ出すことになります。TrueFalseはbool型と呼ばれます。「【Python入門】ブール型(Boolean)の用途と使い方を学ぼう!」が参考になります。

ITP1_3_A Print Many Hello World

ITP1_3_A
for i in range(1000):
    print("Hello World")

【解説】はじめて繰り返しのforの登場です。こちら「【Python入門】for文を使った繰り返し文の書き方」が参考になります。

ITP1_3_B Print Test Cases

ITP1_3_B
case_number=0
while True:
    x=int(input())
    case_number+=1
    if x==0:
        break
    print("Case {}: {}".format(case_number,x))

【解説】whileで入力が0になるまで実行します。whileについては「Pythonのwhile文によるループ処理(無限ループなど)」が参考になります。競技プログラミングではしばしばCase i:結果で出力することがあります。pythonではいくつかの出力方法がありますが、そのうちの1つとしてformatがあります。formatは文字列のメソッドで文字列内に変数を埋め込むことができます(Python2.6以降でのみ使用可能)。こちら「【Python入門】formatメソッドで変数の内容を出力する方法」が参考になります。

ITP1_3_C Swapping Two Numbers

ITP1_3_C
while True:
    x,y=map(int,input().split())
    if x==0 and y==0:
        break
    if x>y:
        print(y,x)
    else:
        print(x,y)

【解説】whileで入力が0 0になるまで実行します。あとはx,yの大小関係を確認して出力します。

ITP1_3_D How Many Divisors?

ITP1_3_D
a,b,c=map(int,input().split())
cnt=0
for k in range(a,b+1):
    if c%k==0:
        cnt+=1
print(cnt)

【解説】aからbまでの整数がcの約数かどうか1つずつ調べます。約数であればcnt(カウント)を1つ大きくします。

ITP1_4_A A/B Problem

ITP1_4_A
a,b=map(int,input().split())
print(a//b,a%b,"{:.6f}".format(a/b))
ITP1_4_A(別解)
a,b=map(int,input().split())
print(a//b,a%b,round((a/b),6))

【解説】a/bの小数の誤差をどう処理するかが問題です。formatを用いることで、数値の小数点の桁を指定できます。「Pythonのformat()メソッドを使いこなす」が参考になります。もしくは四捨五入を行い、小数の誤差を問題の制約内に抑えることも可能です。roundは厳密には四捨五入ではないので注意が必要です。四捨五入は「Pythonで小数・整数を四捨五入するroundとDecimal.quantize」が参考になります。

ITP1_4_C Simple Calculator

ITP1_4_C
while True:
    a,op,b=input().split()
    a=int(a)
    b=int(b)

    if op=="?":
         break
    if op=="+":
        print(a+b)
    if op=="-":
        print(a-b)
    if op=="*":
        print(a*b)
    if op=="/":
        print(a//b)

【解説】while?がでるまで実行します。あとは足し算、引き算、掛け算、割り算をそれぞれ出力します。

ITP1_4_D Min, Max and Sum

ITP1_4_D
N=int(input())
a=list(map(int,input().split()))
print(min(a),max(a),sum(a))

【解説】Pythonではlistの最大や最小、合計をそれぞれmax(list名)min(list名)sum(list名)で求めることができます。

ITP1_5_A Print a Rectangle

ITP1_5_A
while True:
    H,W= map(int,input().split())
    if H==0 and W==0:
        break
    for i in range(H):
        print("#"*W)
    print()

【解説】文字列では*は繰り返しになります。例えば"Hello World"*3とすれば"Hello WorldHello WorldHello World"となります。最後のprint()は長方形と長方形の間の1行を意味します。

ITP1_5_B Print a Frame

ITP1_5_B
while True:
    H,W= map(int,input().split())
    if H==0 and W==0:
        break
    print("#"*W)
    for i in range(H-2):
        print("#"+"."*(W-2)+"#")
    print("#"*W)
    print()

【解説】先ほどの問題に似ています。ただし、1行目とH行目は"###・・・###"ですが、2行目からH-1行目は"#…・・・…#"となります。そのため「1行目を出力」「2行目からH-1行目(つまりH-2行)までを出力」「H行目を出力」とします。

ITP1_5_C Print a Chessboard

ITP1_5_C
while True:
    H,W=map(int,input().split())
    if H==0 and W==0:
         break
    for h in range(H):
        for w in range(W):
            if (h+w)%2==0:
                print("#",end="")
            else:
                print(".",end="")
        print()
    print()

【解説】forのなかにforを書くことができます。二重ループと言われます。(参考:「Pythonで多重ループ(ネストしたforループ)からbreak」)出力したいチェック柄をじっと見ると、行数と列数を足した値が偶数の時は#、奇数の時は.であることに気づきます(Pythonでは0行目、1行目…と数えることに注意)。各行で順に出力していき、最後の列で改行します。ただprint("#")のようにすると#のあとに改行されてしまいます。それを避けるためにend=""で出力時に改行しないようにします。

ITP1_5_D Structured Programming

ITP1_5_D
N=int(input())
for i in range(1,N+1):
    if i%3==0 or "3" in str(i):
        print(" {}".format(i),end="")
print()

【解説】問題の意味をまずは理解します。C++のコードを読めないと辛い問題ですが、競技プログラミングの解説ではC++がよく使われるため、読めるようにしておくといいかもしれません。例えば通称「蟻本」と呼ばれる本もコードはC++で書かれています。今回の問題では「n以下の自然数のうち、3の倍数もしくは3がつく数を小さいものから順に出力しなさい」という問題です。3の倍数であることは3で割った余りを見ればすぐにわかります。3がつくことの確認は今回は文字列としてinを用いて行いました。任意の文字列を含むかの判定は「Pythonで文字列を検索(〜を含むか判定、位置取得、カウント)」が参考になります。

ITP1_6_A Reversing Numbers

ITP1_6_A
N=int(input())
a=list(map(int,input().split()))
a=a[::-1]
print(*a)

【解説】リストの順を逆順にするには、リスト型のメソッドreverse、組み込み関数のreversed、スライスによって並び替えることができます。今回はスライスを利用しました。リストの逆順は「Pythonでリストや文字列を逆順に並べ替え」が、スライスは「Pythonのスライスによるリストや文字列の部分選択・代入」が参考になります。

ITP1_6_B Finding Missing Cards

ITP1_6_B
N=int(input())
suits=["S","H","C","D"]
cards=[]
for _ in range(N):
    s,n=input().split()
    if s=="S":
        cards.append(int(n))   
    elif s=="H":
        cards.append(13+int(n))   
    elif s=="C":
        cards.append(26+int(n))
    else:
        cards.append(39+int(n))

for i in range(1,53):
    if i not in cards:
        print(suits[(i-1)//13],(i-1)%13+1)

【解説】トランプのマークと数字を一緒に表現する方法を考えます。スペードを1から13で、ハートを14から26で、クローバーを27から39で、ダイヤを40から52で表すことでマークと数字を同時に表せます。例えばハートの3は16となります。次に最初に持っていたカードのリストを作成します。あとは1から52までの番号(つまり52枚のトランプ全て)を一つ一つ持っているか確認して、持っていなければ出力します。

【メモ】実は計算量を意識する必要がある問題ではinを用いるのは注意が必要です。計算量については「計算量オーダーの求め方を総整理! 〜 どこから log が出て来るか 〜」が参考になります。ilistにあるか調べるi in listでの計算量は $O(n)$になります。これはlistにおける要素ひとつひとつとiが等しいかを確認していることになります。トランプ程度の枚数であれば問題ありませんが、大きな数になると膨大な計算量になることがあり注意が必要です。

ITP1_6_C Official House

ITP1_6_C
N=int(input())
room=[[[0]*10 for _ in range(3)] for _ in range(4)]

for _ in range(N):
    b,f,r,v=map(int,input().split())
    room[b-1][f-1][r-1]+=v

for i in range(4):
    for j in range(3):
        for k in range(10):
            print(" {}".format(room[i][j][k]), end="")
        print()
    if i!=3:
        print("####################")

【解説】この問題は多次元配列で解くことができます。「Pythonで多次元配列を扱う方法【初心者向け】」が参考になります。出力の形式を合わせるのが少し大変な問題です。

ITP1_6_D Matrix Vector Multiplication

ITP1_6_D
n,m=map(int,input().split())
A=[list(map(int,input().split())) for i in range(n)]
b=[int(input()) for i in range(m)]
for i in range(n):
    ans=0
    for j in range(m):
        ans+=A[i][j]*b[j]
    print(ans)

【解説】この問題も多次元配列で処理することで解くことができます。行列の計算になります。

ITP1_7_A Grading

ITP1_7_A
while True:
    m,f,r=map(int,input().split())
    if m==-1 and f==-1 and r==-1:
        break
    sum=m+f
    if m==-1 or f==-1 :
        print("F")
    elif sum>=80:
        print("A")
    elif sum>=65:
        print("B")
    elif sum>=50:
        print("C")
    elif sum>=30:
        if r>=50:
            print("C")
        else:
            print("D")
    else:
        print("F")

【解説】問題をよく読み、条件分岐を行います。

ITP1_7_B How many ways?

ITP1_7_C
while True:
    n,x=map(int,input().split())
    if n==0 and x==0 :
        break
    cnt=0
    for i in range(1,n-1):
        for j in range(i+1,n):
            if j<x-i-j<=n:
                cnt+=1
    print(cnt)

【解説】少し数学的な考え方が含まれる問題です。nまでの数のなかから重複無しで3つの数を足してxにすることを考えます。例えば1から5までの数から9をつくるとします。このとき、1+3+53+5+1は同じ数字の組み合わせなので同一の組み合わせとみなします。このような組み合わせを複数回数えることがないように、「次に選ぶ数は必ず前に選んだ数よりも大きい」というルールのもとで選んでいくことにします。はじめにiを選び、それより大きいjを選びます。あとはx-i-jjよりも大きくn以下であれば組み合わせとして成立します。

ITP1_7_C Spreadsheet

ITP1_7_C
r,c=map(int,input().split())
sheet=[list(map(int,input().split())) for i in range(r)]
for i in range(r):
    sheet[i].append(sum(sheet[i]))
Column_sum=[0]*(c+1)
for j in range(c+1):
    for i in range(r):
        Column_sum[j]+=sheet[i][j]

for i in range(r):
    print(*sheet[i])
print(*Column_sum)

【解説】はじめにr*cの2次元配列を作成します。各行の合計と、各列の合計をそれぞれ求めて加えていきます。今までの考え方を合わせることで解ける問題です。今回は行の合計はsumで、列の合計は各行のj列目の数を一つずつ足すことで求めています。

ITP1_7_D Matrix Multiplication

ITP1_7_D
n,m,l=map(int,input().split())
A=[list(map(int,input().split())) for i in range(n)]
B=[list(map(int,input().split())) for i in range(m)]

C=[]
for i in range(n):
    line=[]
    for j in range(l):
        c=0
        for k in range(m):
            c+=A[i][k]*B[k][j]
        line.append(c)
    C.append(line)

for line in C:
    print(*line)

【解説】2次元配列を用います。インデックスを理解して書く必要があります。

ITP1_8_A Toggling Cases

ITP1_8_A
words=input()
print(str.swapcase(words))

【解説】英字の大文字と小文字の変換に利用できるメソッドはいくつかあります。そのうちの一つであるswapcaseを用いると今回の問題は簡単に解くことができます。upperlowerなど他にも知っておくべきメソッドはあります。「Python 英字の大文字と小文字を変換(upper/lower/capitalize/swapcase/title)」を一読するといいと思います。

ITP1_8_B Sum of Numbers

ITP1_8_B
while True:
    str_n=input()
    if str_n=="0":
        break
    list_n=list(str_n)
    ans=0
    for n in list_n:
        ans+=int(n)
    print(ans)
ITP1_8_B別解
while True:
    str_n=input()
    if str_n=="0":
        break
    print(sum(list(map(int,str_n))))

【解説】今回はあえて数値を文字列として受け取ります。文字列をリストにします。例えば文字列"123"に対して、list("123")とすると["1","2","3"]となります。あとはforで各位の数を1つずつ取り出します。ただし取り出せるのは文字列としてなので、int()で数値に直してから足します。今まで標準入力で利用してきたmapを用いてより簡潔に書くこともできます。

ITP1_8_C Counting Characters

ITP1_8_C
import sys
texts=sys.stdin.read()
texts=texts.lower()
cnt=[0]*26

letters=list('abcdefghijklmnopqrstuvwxyz')
for x in texts:
    i=0
    for y in letters:
        if x==y:
            cnt[i]+=1
        i+=1
for i in range(26):
    print(letters[i]+" : "+str(cnt[i]))

【解説】今まではinputを用いて標準入力を受け取りました。今回は複数行かつ行数がわからない英文を読み取らなければいけません。whileinputを組み合わせることも可能ですが、sysモジュールのsys.stdin.readを利用します。複数行の文字列を複数行のまま受け取ることができます。詳しくは「Python】標準入力でキーボードからデータを受け取り(sys.stdin.readlines、input関数)」を参考にして下さい。入力後は、すべて小文字にしたうえで英文の1文字ずつアルファベットを確認して、カウントしていきます。

ITP1_8_D Ring

ITP1_8_D
s=input()
p=input()
s*=2
if s.find(p)!=-1:
    print("Yes")
else :
    print("No")

【解説】リング状の文字列からある文字列を作成できるかを考えます。リング状の文字列では始まりと終わりがなくどれだけでも長い文字列を作ることができます。ただし今回の問題ではpsよりも短いという条件がついています。そのためリング2周分で考えれば十分です。リング2周に該当する文字列を作成し、そこでpを作ることができるか調べます。pがあるかを確かめるために文字列のメソッドfindを利用します。findは特定の文字列の位置を取得しますが、文字列がなければ-1を返します。「Pythonで文字列を検索(〜を含むか判定、位置取得、カウント)」が参考になります。

ITP1_9_A Finding a Word

ITP1_9_A
import sys
word=input()
text=sys.stdin.read()
print(text.lower().split().count(word))

【解説】入力はsys.stdin.readで行います。text.lower().split().count(word)について解説します。lower()で小文字にします。split()でスペースごとに区切りリストにします。普段の標準入力でinput().split()splitと同様です。「Pythonで文字列を分割(区切り文字、改行、正規表現、文字数)」が参考になります。リストのなかに含まれる個数を調べるにはcountメソッドを利用します。「【Python】 特定の文字や文字列の出現回数を数える(count)」が参考になります。

ITP1_9_B Shuffle

ITP1_9_B
while True:
    cards=input()
    if cards=="-":
        break
    m=int(input())
    for i in range(m):
        sh=int(input())
        former=cards[:sh]
        later=cards[sh:]
        cards=later+former
    print(cards)

【解説】リストのスライスを利用して解くことができます。

ITP1_9_C Card Game

ITP1_9_C
n=int(input())
T=0
H=0
for i in range(n):
    card_t,card_h=input().split()
    if card_t==card_h:
        T+=1
        H+=1
    else:
        if card_h>card_t:
            H+=3
        else:
            T+=3
print(T,H)

【解説】文字列に><を用いると、辞書順で比較した結果が返されます。これを利用して解くことができます。

ITP1_9_D Transformation

ITP1_9_D
text=input()
n=int(input())
for i in range(n):
    order=input().split()
    a,b=map(int,order[1:3])
    if order[0]=="print":
        print(text[a:b+1])
    elif order[0]=="reverse":
        re_text=text[a:b+1]
        text=text[:a]+re_text[::-1]+text[b+1:]
    else :
        text=text[:a]+order[3]+text[b+1:]

【解説】先ほどと同じく、リストのスライスを利用して解くことができます。ただしreverseのときに少し注意が必要です。スライスでstep-1にするときstartendは文字通りの解釈がされません。こちらの質問が参考になります。今回はreverseしたい範囲のリストを作成してから逆順にしました。

ITP1_10_A Distance

ITP1_10_A
x1,y1,x2,y2=map(float,input().split())
print(((x1-x2)**2+(y1-y2)**2)**0.5)

【解説】ルートの計算はmathモジュールをインポートして、math.sqrt()で行うか、もしくは**0.5することで求めることができます。

ITP1_10_B Triangle

ITP1_10_B
import math
a,b,C=map(float,input().split())
θ=math.radians(C)
h=b*math.sin(θ)
S=(a*h)/2
c=math.sqrt(a**2+b**2-2*a*b*math.cos(θ))
L=a+b+c
print(S,L,h,sep="\n")

【解説】三角比はmathモジュールを利用します。ラジアンと度数法の変換は「ラジアンと度数法単位の相互変換」を、三角比は「Pythonで三角関数を計算(sin, cos, tan, arcsin, arccos, arctan)」が参考になります。cの長さは余弦定理で求めています。

ITP1_10_C Standard Deviation

ITP1_10_C
while True:
    n=int(input())
    if n==0:
        break
    score=list(map(int,input().split()))
    mean=sum(score)/n
    var_sum=0
    for i in range(n):
        var_sum+=(score[i]-mean)**2
    print((var_sum/n)**0.5)

【解説】統計量はstatisticsなどのモジュールを用いて求めることもできますが、今回は問題文にあるとおりに計算して求めます。まずは平均値を算出します。平均値との差の二乗の平均を求めます。これは分散に当たります。それのルートをとれば今回求める標準偏差になります。

ITP1_10_D Distance II

ITP1_10_D
def Distance(X,Y,p):
    s=0
    for x,y in zip(X,Y):
        s+=abs(x-y)**p
    print(s**(1/p))

n=int(input())
X=list(map(int,input().split()))
Y=list(map(int,input().split()))

for p in range(1,4):
    Distance(X,Y,p)
print(max(abs(x-y) for x,y in zip(X,Y)))

【解説】今までは既存のライブラリを利用してきましたが、自分で関数を定義することもできます。今回はDistanceという距離を出力する関数を定義します。関数の定義は「Pythonで関数を定義・呼び出し(def, return)」が参考になります。チェビシェフの距離だけは別に計算をします。またzip関数は複数のリストなどから要素を取得する時に役立ちます。「Python, zip関数の使い方: 複数のリストの要素をまとめて取得」が参考になります。

最後に

 解説を書くにあたり、できるだけ簡潔にかつできるだけ触れられる情報が多くなるように意識しました。複数のリストを用いれば解けるような問題でも敢えて多次元配列で解くようにしました。とはいえ、いきなり難しくならないように1問あたり新しいことは1つもしくは2つに収まるようにしました。ぼくもまだまだ初心者ですが、Pythonをはじめたばかりの自分が喜ぶような記事になっているとは思います。
 「Introduction To Programming I」のあとは、「レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【初級編:競プロを始めよう】」で紹介されている通りに全探索の問題に取り組めばいいと思います。ぼくは全探索の問題に取り組みつつ、ABCコンテストのA問題とB問題とC問題の3問を合計30分以内に解けるように早解きの練習も行いました。皆さんの参考になれば幸いです。最後まで読んでくださりありがとうございました。
 
 
 

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした