HHKB プログラミングコンテスト 2022(ABC235) A～D問題 ものすごく丁寧でわかりやすい解説 python 灰色～茶色コーダー向け #AtCoder

HHKB プログラミングコンテスト 2022(ABC235)　A～E問題の解説記事です。
灰色～茶色コーダーの方向けに解説しています。

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

株式会社PFU様について

本コンテストは株式会社PFU様が主催されています。
ちなみにHHKBはPFU様の製品であるHappy Hacking Keyboardの略称です。

気になる方は新卒採用ページをご覧ください。

社員有志の「プロコン部」というサークルもあるそうです。

A - Rotate

abcを受け取り、abc,bca,cabを作って足し算します。

まずabcを文字列として受け取ります。
pythonでは文字列の先頭を0文字目、次を1文字目、...と数えます。
よってabcをXという変数へ受け取った場合は以下のようになります。
a=X[0]
b=X[1]
c=X[2]
X[i]は「Xのi文字目」という意味です。

次にそれぞれを結合してabc,bca,cabを作ります。これは単純に「+」でつなげば良いです。
例えばbcaは
bca=b+c+a
となります。

このままでは文字列と認識され計算ができないので、結合したら文字列→整数へ変換します。
int(文字列)
とすることで整数へ変換できます。

最後にabc,bca,cabを足して答えを出します。

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

【提出】

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

# a=0文字目
a=X[0]
# b=1文字目
b=X[1]
# c=2文字目
c=X[2]

# a,b,cを結合
abc=a+b+c
# 整数へ変換
abc=int(abc)

# b,c,aを結合
bca=b+c+a
# 整数へ変換
bca=int(bca)

# c,a,bを結合
cab=c+a+b
# 整数へ変換
cab=int(cab)

# 足し算を行う
ans=abc+bca+cab

# 答えの出力
print(ans)

B - Climbing Takahashi

問題文の条件をそのまま書ければOKです。

高さの情報をHというリストに受け取ります。

今いる台をi番目の台とした場合、右の台へ進む条件は以下のようになります。
・右端の台でない⇔i<N-1
・右の台の方が高い⇔H[i]<H[i+1]
両方が満たされている間「右の台へ進む」⇔「iに+1」を行います。

pythonのリストは0インデックス(先頭が「0番目」、次が「1番目」、...)なので右端の台はH[N]ではなくH[N-1]となることに注意してください。

【提出】

# 入力を受け取り
N=int(input())
H=list(map(int,input().split()))

# i番目の台の高さを確認していく
# 最初は左端
i=0

# 右端の台でなく　かつ　右の台のほうが高ければ
while i<N-1 and H[i]<H[i+1]:
    # 右の台へ移動
    i+=1

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

C - The Kth Time Query

「k回目に出てくるx」を連想配列へ記録します。

入力例1を使って説明します。
N：6
Q：8
a：1 1 2 3 1 2

「count」というのはその数が何回目に出てきたかを表します。
例えばi=5(a5)の「1」は3回目に出てくる「1」なのでcountは3になっています。

連想配列へ
青い部分(aの値,count)をキー
赤い部分(インデックス番号)を値
として記録していきます。

連想配列(defaultdict)を使ったことがない人は以下を参照してください。

defaultdict(連想配列)について
辞書または連想配列と言います。
キー：値
というような対応付を行えるデータ構造です。
連想配列はdict()と書くことでも使えますが、デフォルトの値(初期値)が設定できません。そのため存在チェックなど色々面倒が発生します。
その面倒を避けるためにdefaultdictを使います。
import：from collections import defaultdict
作成(デフォルト0)：変数名=defaultdict(int)
キー、値の登録：変数名[キー]=値
値の取り出し：変数名[キー]
【使用例】

# インポート
from collections import defaultdict

# 作成(デフォルト0)：変数名=defaultdict(int)
dictionary=defaultdict(int)

# キー、値の登録：変数名[キー]=値
dictionary[5]=1

# 値の取り出し：変数名[キー]
x=dictionary[5]

詳しく知りたい人は以下を参照してください。

キーには複数の値を登録することも出来ます。今回は(aの値,count)をキーにします。
記録するときには何回目に出てきた数かを確認するため、出てきた数をカウントする連想配列(count)を用意しておきましょう。

記録が出来たらクエリの値をキーに値を出力していくだけです。
条件を満たす要素が存在しない場合、defaultdictはデフォルトの値(=0)を返すので、その場合のみ「-1」を出力するようにしておきます。

【提出】

# 入力を受け取り
N,Q=map(int,input().split())
a=list(map(int,input().split()))

# defaultdictのインポート
from collections import defaultdict

# 何回目に出てきた数かカウントする連想配列
count=defaultdict(int)
# k回目のxが出てくるインデックス番号
indx=defaultdict(int)

# i=0~(N-1)
for i in range(N):
    # count[a[i]]をプラス1
    count[a[i]]+=1
    # インデックス番号を記録
    # 0インデックスなのでi+1とすることに注意
    indx[(a[i],count[a[i]])]=i+1

# Q回
for i in range(Q):
    # 入力の受け取り
    x,k=map(int,input().split())
    # k回目のxが存在しない場合
    # ⇔デフォルトの値=0が記録されている場合
    if indx[(x,k)]==0:
        # 「-1」を出力
        print(-1)
    # そうでない場合
    else:
        # 答えを出力
        print(indx[(x,k)])

D - Multiply and Rotate

BFS(幅優先探索)を使います。

「1」からスタートして2つの操作で作れる数へとどんどん進みながらそこに至るまでの操作回数を記録していきます。

2つの操作どちらを行っても桁数が減ることはないです。
2≤N<10^6という条件から操作の結果10^6を超えた数は無視して良いことがわかります。

どうやって「1」から次の数へどんどん進んでいくかですが、これにBFSを使います。
BFSはグラフを探索するアルゴリズムです。
本問は一見グラフに見えませんが操作によって次の数に進んでいくということをグラフ上の頂点間移動とみなせばBFSが使えます。

具体的な手順は以下です。
※キューがよくわからない人は後述の「dequeについて」を見てください。
(1)各数の操作回数を記録するリスト(num)を用意(初期値は-1)
(2)キューに「1」(=最初の数)を入れる
(3)キューの左端から要素を取り出し、その数にたどり着くまでの操作回数を確認
(4_1)a倍して10^6未満　ならば
　　num=-1　ならば(まだ一度もその数にたどり着いていないなら)
　　操作回数を記録
　　キューへ追加
(4_2)10より大きい　かつ　10で割り切れない　ならば
　　末尾を先頭へ移動
　　num=-1　ならば(まだ一度もその数にたどり着いていないなら)
　　操作回数を記録
　　キューへ追加
(5)(3)~(4)をキューが空になるまで繰り返す

キューが空になったらnumに記録した「N」の操作回数を出力して終了です。

dequeについて
dequeはリストのようなものですが、先頭から要素を取り出す操作をO(1)で行うことができます。
(リストだとO(N)かかります)
import：from collections import deque
作成：変数名=deque()
末尾に要素追加【O(1)】：変数名.append(要素)
先頭から要素を取り出して削除【O(1)】：変数名.popleft()
【使用例】

# インポート
from collections import deque

# 作成：変数名=deque()
que=deque()

# 末尾に要素追加 O(1)：変数名.append(要素)
que.append(1)

# 先頭から要素を取り出して削除 O(1)：変数名.popleft()
x=que.popleft()

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

本問についてではないですが、BFSについては動画での解説を作っていますのでそちらも是非ご覧ください。

【提出】

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

# 操作回数の記録リスト
# 初期値は「-1」
num=[-1]*10**6

# dequeのインポート
from collections import deque
que=deque()

# キューに「1」を追加
que.append(1)

# 「1」への操作回数は0
num[1]=0

# キューが空になるまで
while 0<len(que):
    # 今の数
    now=que.popleft()

    # 今の操作回数
    k=num[now]

    # a倍した場合の数
    to=now*a
    # a倍した時10^6を超えていなければ
    if to<10**6:
        # まだ一度も出てきていない数の場合
        if num[to]==-1:
            # 操作回数(k+1)を記録
            num[to]=k+1
            # キューへ
            que.append(to)
    
    # 今の数が　10より大きい　かつ　10で割り切れない
    if 10<=now and now%10!=0:
        # 文字列へ変換
        now_str=str(now)
        # 末尾を先頭へ
        to_str=now_str[-1]+now_str[:-1]
        # 整数へ変換
        to=int(to_str)
        # まだ一度も出てきていない数の場合
        if num[to]==-1:
            # 操作回数(k+1)を記録
            num[to]=k+1
            # キューへ
            que.append(to)

# 答えの出力
print(num[N])

【広告】

『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】