デンソークリエイトプログラミングコンテスト2022(ABC239) A～E問題 ものすごく丁寧でわかりやすい解説 python 灰色～茶色コーダー向け #AtCoder

デンソークリエイトプログラミングコンテスト2022(AtCoder Beginner Contest 239)　A～E問題の解説記事です。
灰色～茶色コーダーの方向けに解説しています。

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

株式会社デンソークリエイト様について

デンソークリエイト様はデンソーグループの中でも、ソフトウェア開発を対象とした先進技術の開発と標準化に取組んでいる会社です。
興味がある方は会社説明会動画等をご覧ください。

A - Horizon

素直に√(H(12800000+H)を計算して出力します。

pythonでルートを計算するにはmathというライブラリからsqrtを使います。(square rootの意味)
まず以下のように書きます。
from math import sqrt
これでsqrtが使えるようになります。sqrt(x)と書くことで√xが計算できます。

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

【提出】

# ルートの計算のためsqrtをインポート
from math import sqrt

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

# 答えの出力
print(sqrt(H*(12800000+H)))

B - Integer Division

「(Xを10で割った数)以下の整数の中で最大の整数」とややこしい書き方をしていますが、要するに「Xを10で割った商」です。
よってX//10を出力すれば終わりです。

Xがマイナスのときもちゃんと計算できるか心配ですが、pythonの場合はX//K=「(XをKで割った数)以下の整数の中で最大の整数」という仕様になっているので問題ありません。

ところで10で割ってから整数にする、すなわち
int(X/10)
でいけんじゃね？と思った人もいるかもしれません。

数学的には間違ってないのですが、コンピューターで少数の計算を行うと誤差が出る場合があります。
例えば入力例5を計算してみると
print(int(987654321987654321/10))
→98765432198765440
と全然違う値を出してきます。誤差のせいです。
プログラミングでは極力少数を避ける方法を取りましょう。

【提出】

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

# Xを10で割った商を出力
print(X//10)

C - Knight Fork

問題文にある図からわかるように、(x1,y1)から距離が√5になる格子点は8個しかありません。
この8個すべてについて(x2,y2)との距離を計算し、距離が√5になる点が一つでもあれば「Yes」です。

(x1,y1)から距離が√5にある格子点p(x3,y3)は以下の8個です。
p1(x3,y3)=(x1+2,y1+1)
p2(x3,y3)=(x1+2,y1-1)
p3(x3,y3)=(x1-2,y1+1)
p4(x3,y3)=(x1-2,y1-1)
p5(x3,y3)=(x1+1,y1+2)
p6(x3,y3)=(x1+1,y1-2)
p7(x3,y3)=(x1-1,y1+2)
p8(x3,y3)=(x1-1,y1-2)

これら全てについて(x2,y2)との距離を計算して確認します。
ただし(距離)=√5になるか？だと√5が少数になり、誤差が出る可能性があるので、(距離)^2=5になるか？を判定しましょう。

【提出】

# 入力の受け取り
x1,y1,x2,y2=map(int,input().split())

# 候補点
p=[]

# 候補点を格納
p.append([x1+2,y1+1])
p.append([x1+2,y1-1])
p.append([x1-2,y1+1])
p.append([x1-2,y1-1])
p.append([x1+1,y1+2])
p.append([x1+1,y1-2])
p.append([x1-1,y1+2])
p.append([x1-1,y1-2])

# 候補点を取り出し
for x3,y3 in p:
    # 距離^2を計算して「5」になれば
    if (x3-x2)**2+(y3-y2)**2==5:
        # 「Yes」を出力
        print("Yes")
        # 終了
        exit()

# 「No」を出力
print("No")

D - Prime Sum Game

A,B,C,Dは最大でも100なので、高橋くん、青木くんが選べる数を全パターン確認すれば良いです。
高橋くんの選んだ数について一つでも青木くんが勝てないものがあれば高橋くんの勝ち
高橋くんの選んだ数全てについて青木くんが勝てるなら青木くんの勝ちとなります。

高橋くんの数と青木くんの数の和は最大でも200までしかありませんので、1~200までの素数がわかれば勝敗判定ができます。
素数については公式解説の通りエラトステネスの篩であらかじめ作っておいてもいいのですがめんどくさいです。
Wikipediaの「素数」に1000以下の素数を一覧にしてくれていますから、ここからコピペしましょう。
https://ja.wikipedia.org/wiki/%E7%B4%A0%E6%95%B0

【提出】

# 入力の受け取り
A,B,C,D=map(int,input().split())

# 1~200までの素数
prime=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199]

# 高橋の選ぶ数：taka=A~B
for taka in range(A,B+1):
    # 高橋が勝っている間はTrue
    TakaWin=True
    # 青木くんの選ぶ数：ao=C~D
    for ao in range(C,D+1):
        # 和が素数なら(素数リストの中にあるなら)
        if taka+ao in prime:
            # 高橋君の負け
            TakaWin=False
            # 次の数へ
            break
    # 青木くんの選んだ数全てについて高橋くんが勝ちなら
    if TakaWin==True:
        # 「takahashi」を出力
        print("Takahashi")
        # 終了
        exit()

# 「Aoki」を出力
print("Aoki")

E - Subtree K-th Max

各頂点について「部分木に含まれる数を大きい順にソートしたリスト」を予め用意しておきます。

このリストが用意してあれば各クエリにはすぐに答えられます。
というわけでこのリストをどのように作るか考えましょう。

「葉」の部分、すなわち末端にある頂点(③,④,⑤)のPについては簡単です。
部分木は自分自身しかないのでPも自分自身のみになります。
P[3]=3(=X[3])
P[4]=4(=X[4])
P[5]=5(=X[5])

次に「親」と「子」の関係を考えます。
「親」「子」は上のグラフを家系図だと思ってみればわかりやすいと思います。
頂点②は「親」で、③,⑤は②の「子」です。
頂点①は「親」で、②,④は①の「子」です。
きちんとした定義はややこしいので興味のある人だけ調べてみてください。「親」「子」の雰囲気だけわかったら問題は解けます。

「親」のPは、「子」のPを全部合わせてソートすると作れます。

例えば頂点②のPは「子」である③と⑤のPを合わせればいいです。ついでに自分自身(=X[頂点番号])も入れます。
P[2]=[2]+P[3]+P[5]=[2,3,5]
大きい順にソートします。
P[2]=[5,3,2]
頂点①のPは「子」である④と②のPを合わせます。
P[1]=[1]+P[4]+P[2]=[1,4,5,3,2]
大きい順にソートします。
P[1]=[5,4,3,2,1]

ポイントは「葉」から上に向かって(「子」→「親」になるように)Pを作っていくことです。
「子」のPが全てできていれば「親」のPも作ることが出来ます。

ところで「大きい順にソートします」とありますがいちいちソートしていると間に合わない気がしますね。
しかしKの最大値は20ですから、Pも大きい方から20番目までの数をもっておけばいいです。
よって
子のPを足す→ソートする→20番目以降の要素を捨てる
とすることで計算量を抑えられます。

実装はDFSを使います。
ただし「葉」の頂点から処理する必要があるため、各頂点に2回ずつ訪問するという方法を取ります。
1回目の訪問では「子」の頂点をキューへ入れる
2回目の訪問では「子」のPを足す
という処理を行います。

(1)キューを用意する
　※キューに「今いる頂点、今いる頂点の親、訪問回数」を記録します
(2)スタート地点=頂点①をキューへ入れる
　(①の親はいないから0にしておく。訪問回数は1回目)
(3)キューの「右端から」要素を取り出す
　・1回目の訪問ならば
　　(3_1)「今いる頂点」を2回目の訪問としてキューへ記録
　　(3_2)「今いる頂点から行ける頂点」をキューへ1回目の訪問として記録
　・2回目の訪問ならば
　　(3_3)「今いる頂点」のPへ子(親でない)の頂点のPを足す
　　(3_4)大きい順にソート
　　(3_5)20番目以降の要素を捨てる

これで各頂点のPを作ることができます。

あとはクエリに対して答えを出力していくだけです。

【提出】

# 入力の受け取り
N,Q=map(int,input().split())
# 1インデックスにするため先頭に「0」を追加
X=[0]+list(map(int,input().split()))
# 辺の情報格納用
edge=[[] for i in range(N+1)]

# (N-1)回
for i in range(N-1):
    # 入力の受け取り
    A,B=map(int,input().split())
    # 辺の情報を格納
    edge[A].append(B)
    edge[B].append(A)

# (1)キューを用意する
que=list()

# (2)スタート地点=頂点①をキューへ入れる
# (今いる頂点,今いる頂点の親,訪問回数)
que.append([1,0,1])
# 部分木の頂点に書いている数を大きい順に格納したリスト
P=[[0]]

# i=1~N
for i in range(1,N+1):
    # Pへ自分自身に書いている数を追加
    P.append([X[i]])

# キューが空になるまで
while 0<len(que):
    # (3)キューの「右端から」要素を取り出す
    # (今いる頂点,今いる頂点の親,訪問回数)
    now,parent,count=que.pop()

    # ・1回目の訪問ならば
    if count==1:
        # (3_1)「今いる頂点」を2回目の訪問としてキューへ記録
        que.append([now,parent,2])
        # (3_2)「今いる頂点から行ける頂点」をキューへ1回目の訪問として記録
        # to：今いる頂点から行ける頂点
        for to in edge[now]:
            # 親でなければ
            if to!=parent:
                # キューへ記録
                que.append([to,now,1])

    # ・2回目の訪問ならば
    else:
        # to：今いる頂点から行ける頂点
        for to in edge[now]:
            # (3_3)「今いる頂点」のPへ子(親でない)の頂点のPを足す
            # 親ならば
            if to==parent:
                # 次の頂点へ
                continue
            # P[今いる頂点]にP[行ける頂点(葉)]を追加
            P[now]+=P[to]
            # (3_4)大きい順にソート
            P[now].sort(reverse=True)
            # (3_5)20番目以降の要素を捨てる
            P[now]=P[now][:20]

# Q回
for i in range(Q):
    # 入力の受け取り
    V,K=map(int,input().split())
    # Kをマイナス1(P[v]は先頭が0番目、次が1番目、...のため)
    K-=1
    # 答えを出力
    print(P[V][K])

【広告】

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

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

【booth(pdf)】
https://sano192.booth.pm/items/3179185

1～24問目まではサンプルとして無料公開しています
https://qiita.com/sano192/items/eb2c9cbee6ec4dc79aaf

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

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

サンプルを5問分公開しています
https://qiita.com/sano192/items/3258c39988187759f756

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

値段：300円(Kindle Unlimited対象)
【kindle】
https://www.amazon.co.jp/dp/B09TVK3SLV

【booth(pdf)】
https://booth.pm/ja/items/3698647

ARC119~128の部分のみ抜粋した廉価版 もあります。
値段：200円(Kindle Unlimited対象)
【kindle】
https://www.amazon.co.jp/dp/B09TVKGH17/

【booth(pdf)】
https://sano192.booth.pm/items/3698668

『AtCoder ABC226～250 ARC129～139 灰・茶・緑問題 超詳細解説 AtCoder 詳細解説』

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

サンプルを4問分公開しています
https://qiita.com/sano192/items/f8f09ea769f2414a5733

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

値段：300円(Kindle Unlimited対象)
【kindle】
https://www.amazon.co.jp/dp/B0B7G13QMS

【booth(pdf)】
https://sano192.booth.pm/items/4025713

ARC129～139の部分のみ抜粋した廉価版 もあります。
値段：200円(Kindle Unlimited対象)
【kindle】
https://www.amazon.co.jp/dp/B0B7G337YF

【booth(pdf)】
https://sano192.booth.pm/items/4025737

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

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

サンプルとして「準備」～「三目並べ」を無料公開しています。
https://qiita.com/sano192/items/9a47e6d73373d01e31fb

【kindle】
https://www.amazon.co.jp/dp/B09XLM42MW

【booth(pdf】
https://sano192.booth.pm/items/3785312