ABC234 A～E問題 ものすごく丁寧でわかりやすい解説 python 灰色～茶色コーダー向け #AtCoder

ABC234(AtCoder Beginner Contest 234)　A～E問題の解説記事です。
灰色～茶色コーダーの方向けに解説しています。

その他のABC解説、動画などは以下です。

A - Weird Function

今回のA問題は「やや難」です。
普段のA問題はもっと簡単なので、今回解けなかった人も落ち込まずに競技プログラミングを続けてください。

fという関数を作ってしまえば問題文に書いている計算をそのまま行うことが出来ます。
関数を作るときは
def 関数名(引数):
　　処理内容
　　return 返り値
と書きます。

本文の場合
tを引数　→　t^2+2t+3を返り値
とするので関数fは以下のようになります。

def f(t):
    return t**2+2*t+3

これを書いておくと例えばt=2の場合
f(2)=2^2+2*2+3=11
と計算ができます。

そもそもプログラミングにおける関数って何？という人は以下のページがわかりやすいので読んでみてください。

関数が作れたらあとは問題文に記載の通り、f(f(f(t)+t)+f(f(t)))を計算して出力します。

入力の受け取り、出力がわからない方は以下の記事を参考にしてください。

【提出】

# 入力の受け取り
t=int(input())

# 関数の定義
# 引数；t　返り値：t^2+2t+3
def f(t):
    return t**2+2*t+3

# 答えの計算
ans=f(f(f(t)+t)+f(f(t)))

# 答えの出力
print(ans)

B - Longest Segment

Nは最大で100なので全部の組み合わせを試しても100C2=4950通りしかありません。
よって全組み合わせの線分の長さを確認し、一番大きいものを出力します。

(i,j)の組全部を試すときは以下のように書きます。

# i=1~(N-1)
for i in range(N):
    # j=(i+1)~(N-1)
    for j in range(i+1,N):

こう書くことでいい感じに(i,j)組み合わせを作ることができます。
試しにN=5として(i,j)を出力してみましょう。

N=5

# i=1~(N-1)
for i in range(N):
    # j=(i+1)~(N-1)
    for j in range(i+1,N):
        print(i,j)

【出力結果】
0 1
0 2
0 3
0 4
1 2
1 3
1 4
2 3
2 4
3 4
i=0についてj=1,2,3,4
i=1についてj=2,3,4、
i=2についてj=3,4、
...
と組み合わせを作れています。jの範囲を(i+1)からスタートとするのがコツです。
本問に限らずこの書き方は非常によく使うので自分で書けるようになりましょう。

2点(xi,yi),(xj,yj)の距離は以下の式で求まります。
√((xi-xj)^2+(yi-yj)^2)

ルートの計算はmathをインポートしてsqrtを使います。
from math import sqrt
と書くことでxの平方根をsqrt(x)と計算できます。

【提出】

# 入力の受け取り
N=int(input())

# 座標の格納用
x=[]
y=[]

# i=0~(N-1)
for i in range(N):
    # 入力の受け取り
    xi,yi=map(int,input().split())
    # 座標の格納
    x.append(xi)
    y.append(yi)

# ルートの計算用
from math import sqrt

# 答え
ans=0

# i=1~(N-1)
for i in range(N):
    # j=(i+1)~(N-1)
    for j in range(i+1,N):
        # 距離の計算
        length=sqrt((x[i]-x[j])**2+(y[i]-y[j])**2)
        # 答えより大きければ更新
        ans=max(ans,length)

# 答えの出力
print(ans)

C - Happy New Year!

問題文だけでは何を言っているのかよくわかりませんね。
こういう時はとりあえず入力例を見ます。

入力例1には
「10進数で表記したときに0,2のみからなる正整数を小さいほうから並べると2,20,22,...となります｣
と記載があります。これでなんとなく意味がわかります。

「10進数で表記したときに0,2のみからなる正整数」を小さい順に書いてみましょう.
1：2
2：20
3：22
4：200
5：202
6：220
7：222
8：2000
...

2進数の増え方に似ていますね。
実際2進数を書いてみると以下のようになっています。

1：1
2：10
3：11
4：100
5：101
6：110
7：111
8：1000
...

要するに「10進数で表記したときに0,2のみからなる正整数」とは
2進数表記における｢1」を｢2」に置き換えたのもの
ということがわかります。

よってNを2進数へ変換し、「1」を「2」に換えれば終了です。

Nを2進数へ変換するときは
bin(N)
と書きます。こう書くとNを2進数に変換したものが「文字列として｣得られます。
ただし頭に2進数であることを表す｢0b｣という文字が入ります。
例えばbin(5)="0b101"となります。

「1」を「2」に置き換えるにはreplaceを使います。文字列中の文字を別の文字へ変換してくれるコマンドです。
使い方は以下です。
文字列.replace("変換前の文字列","変換後の文字列")

出力のときは頭の「0b」はいらないので2文字目～を出力します。

【提出】

# 入力の受け取り
N=int(input())

# 2進数へ変換
N_bit=bin(N)

# 「1」→「2」へ変換
ans=N_bit.replace("1","2")

# 答えの出力
# 0文字目、1文字目は不要のため2文字目～
print(ans[2:])

D - Prefix K-th Max

こういった問題は紙とペンを使って自分で書きながら考えるのがよいです。
入力例2を使って考えましょう。
解けなかった人は実際に紙に書きながら読んでください。

N：11
K：5
P：3 7 2 5 11 6 1 9 8 10 4

「i=5」
まずP1～P5までです。
「3 7 2 5 11」
K(=5)番目に大きい値は最小値の「2」であることがすぐにわかります。

「i=6」
次にP1～P6です。i=5までの数列にP6=6が加わります。
「3 7 2 5 11 6」
K(=5)番目に大きい値は「3」です。
ここで重要なのはこれ以降のiについて「3」より小さい「2」は絶対に答えにならないということです。

「i=7」
P1～P7です。i=6までの数列にP7=1が加わります。
「3 7 2 5 11 6 1」
K(=5)番目に大きい値は「3」です。
同様にこれ以降のiについて「3」より小さい「1」は絶対に答えになりません。

ここまでの操作を見ていると各iについて「P1～P(i-1)でK番目に大きい数」と「Pi」の大小関係が重要であることがわかります。
具体的には各iについて
・Pi<「P1～P(i-1)でK番目に大きい数」の場合
　「P1～P(i-1)でK番目に大きい数」が答えです。
　Piがこれ以降答えになることはありません。
・「P1～P(i-1)でK番目に大きい数」<Piの場合
　「Pi」が答えです。
　「P1～P(i-1)でK番目に大きい数」が答えになることはありません。

しかしPiの追加毎に最小値の確認なりソートなりしていては間に合いません。

そこで最小値を高速で取り出せるデータ構造heapを使います、
heapqを使ったことがない人は以下を参照してください。

heapについて
heapはリストから最小値をO(logN)で取り出せるデータ構造です。
import：import heapq
リストのheap化 O(N)：heapify(リスト)
要素の追加 O(logN)：heappush(リスト,要素)
最小値の参照 O(1)：リスト[0]
最小値の取り出し O(logN)：heappop(リスト)
【使用例】

# インポート
import heapq

# リストを用意
que=list()

# リストのheap化 O(N)：heapify(リスト)
heapq.heapify(que)

# 要素の追加 O(logN)：heappush(リスト,要素)
heapq.heappush(que, 6)
heapq.heappush(que, 1)

# 最小値の参照 O(1)：リスト[0]
print(que[0])

# 最小値の取り出し O(logN)：heappop(リスト)
min_x=heapq.heappop(que)

詳しく知りたい人は以下のページを見てください。

heap化したリスト(que)を用意し、各i(K<i)毎に以下の操作を行います。
①queの最小値を取り出す
②「queの最小値」と「Pi」のうち大きい方をqueに戻す
③「queの最小値」を出力

それでは入力例2で上記操作を行うとどうなるか見てみましょう。

「i=5」
que=[3 7 2 5 11]
まずi=kについては素直にP1～PKの最小値を確認します。
最小値は「2」です。

queをheap化します。
これでこのqueから最小値を取り出す操作を高速で行うことができます。

「i=6」
que=[3 7 2 5 11]
①queの最小値を取り出す
最小値は「2」です。
②「queの最小値」と「Pi」の大きい方をqueに戻す
「queの最小値」=2
「P6」=6
大きいのは「P6」=6です。これをqueに追加します。
que=[3 7 5 11 6]
「2」は①で取り出したため無くなっていることに注意してください。
③「queの最小値」を出力
最小値は「3」なので「3」を出力します。

「i=7」
que=[3 7 5 11 6]
①queの最小値を取り出す
最小値は「3」です。
②「queの最小値」と「Pi」の大きい方をqueに戻す
「queの最小値」=3
「P7」=1
大きいのは「queの最小値」=3です。queに追加(戻す)します。
que=[7 5 11 6 3]
③「queの最小値」を出力
最小値は「3」なので「3」を出力します。

この操作を繰り返せば答えを出すことが出来ます。

【提出】

# 入力の受け取り
N,K=map(int,input().split())
P=list(map(int,input().split()))

# heapqのインポート
import heapq

# リストを用意
que=[]

# K個目までをリストへ入れる
for i in range(K):
    que.append(P[i])

# 最小値を出力
print(min(que))

# queをheap化
heapq.heapify(que)

# i=K~(N-1)
for i in range(K,N):
    # ①queの最小値を取り出す
    x=heapq.heappop(que)
    # ②「queの最小値」と「Pi」の大きい方をqueに戻す
    heapq.heappush(que,max(x,P[i]))
    # ③「queの最小値」を出力
    print(que[0])

E - Arithmetic Number

等差数列は(初項,公差,項数)の3つが決まれば作れます。
等差数は各桁が0～9でなければなりません。
あり得る初項は1～9です。
あり得る公差は-9～9です。
あり得る項数(桁数)は1～18です。
(Xは10^17以下ですから、19桁以上の等差数は考える必要がありません)

以上を考えると答えになりうる等差数は最大でも9*19*18=3078個以下しかないことがわかります。
※実際には等差数を作れない組み合わせがあるのでもっと少ないです。

よって等差数を全て作り、ソートしてX以上で最小のものを探せばよいです。

【提出】

# 等差数を作る関数
# 引数：a(初項),d(公差),n(桁数)　返り値：対応する等差数　作れなかったら「-1」
def make_num(a,d,n):
    # 等差数
    num=""
    # n桁分
    # i=0~(n-1)
    for i in range(n):
        # i桁目
        x=a+d*i
        # 0以上9以下になっていれば
        if 0<=x<=9:
            # i桁目を記録
            num+=str(x)
        # そうでなければ
        else:
            # 「-1」を返す
            return -1
    # 整数にして返す
    return int(num)

# 等差数を記録するリスト
num_list=[]

# 初項：1~9
for a in range(1,10):
    # 公差：-9~9
    for d in range(-9,10):
        # 桁数：1~18
        for n in range(1,19):
            # 対応する等差数を作る
            num=make_num(a,d,n)
            # 「-1」でなければ
            if num!=-1:
                # 追加
                num_list.append(num)

# ソート
num_list.sort()

# 入力の受け取り
X=int(input())

# 初めてX以上になるところを確認
i=0
while num_list[i]<X:
    i+=1

# 答えの出力
print(num_list[i])

【広告】

『AtCoder　凡人が『緑』になるための精選50問詳細解説』

AtCoderで緑になるための典型50問をひくほど丁寧に解説した本(kindle)、pdf(booth)を販売しています。
値段：100円(Kindle Unlimited対象)
【kindle】

【booth(pdf)】

1～24問目まではサンプルとして無料公開しています

『AtCoder ABC201～225 ARC119～128 灰・茶・緑問題 超詳細解説』

ABC201~225、ARC119~128 の 灰・茶・緑DIfficulty問題(Dif：0～1199) を解説しています。
とにかく 細かく、丁寧に、具体例を豊富に、実装をわかりやすく、コードにコメントをたくさん入れて 解説しています。

サンプルを5問分公開しています

Qiitaにて無料公開している『ものすごく丁寧でわかりやすい解説』シリーズをベースにしていますが、 【キーワード】【どう考える？】【別解】を追加 し、 【解説】と【実装のコツ】を分ける ことでよりわかりやすく、 具体例や図もより豊富に 書き直しました。
Qiitaには公開していない ARC119~128の灰・茶・緑DIfficulty問題も書き下ろし ています。

値段：300円(Kindle Unlimited対象)
【kindle】

【booth(pdf)】

ARC119~128の部分のみ抜粋した廉価版 もあります。
値段：200円(Kindle Unlimited対象)
【kindle】

【booth(pdf)】

『Excelでリバーシを作ろう!!　マクロ、VBAを1から学ぶ』

Excelのマクロ(VBA)で「三目並べ」「マインスイーパー」「リバーシ」を作る解説本です！
マクロ、VBAが全くわからない人でも大丈夫！　丁寧な解説と図でしっかり理解しながら楽しくプログラミングを学ぶ事ができます！
値段：300円(Kindle Unlimited対象)

サンプルとして「準備」～「三目並べ」を無料公開しています。

【kindle】

【booth(pdf】