AtCoder Beginner Contest 395 A〜D問題をPythonで解いてみました

ABC395(AtCoder Beginners Contest 395)
A〜D問題をPythonで解いてみました。

• コードは雑めです
• 競技プログラミングの勉強一切したこと無いので、テクニックは知らないよ

A問題(diff=14)

提出コード

n = int(input())
a = list(map(int,input().split()))

def solve():
    for i in range(n-1):
        if a[i] >= a[i+1]:
            return 'No'
    return 'Yes'
print(solve())

• 狭義単調増加ではないケース、つまり一個先の値が現在値以下なら'No'それ意外なら'Yes'を関数を作って対応しました

B問題(diff=72)

提出コード

n = int(input())

line = '#'*n
all_line = [line for i in range(n)]
for i in range(1,n//2+(n%2)):
    bottom_y = n-1-i
    if (i%2) == 0:
        line_center = "#"*(n-i*2)
    else:
        line_center = "."*(n-i*2)
    right = n-i
    #print(i,line[0:i],line_center,line[right:])
    line = line[0:i] + line_center + line[right:]
    all_line[i] = line
    all_line[bottom_y] = line

for i in range(n):
    print(all_line[i])
    #print(i,all_line[i])

• 最初全部#で埋める（全部は必要なかったと思うけど）
• ループ中はまず真ん中を埋めるように文字列を作成する
• 1行ずつ下へ降りつつ、一番下から上の方向にも埋めていく
• 単純ですが、凡ミスが目立って結構時間がかかってしまいましたね

C問題(diff=161)

提出コード

n = int(input())
a = list(map(int,input().split()))

M = (10**6)+1
last_pos = [-1]*M
min_length = M

for i in range(n):
    a_i = a[i]
    if last_pos[a_i] < 0:
        last_pos[a_i] = i
    else:
        min_length = min(min_length,i-last_pos[a_i]+1)
        last_pos[a_i] = i

if min_length == M:
    print(-1)
else:
    print(min_length)

• 100万要素を持つ配列を用意して、最後の位置を保持しながら距離の最小値を取得していくだけです

D問題(diff=919)

提出コード

N,Q = map(int,input().split())

pigeon = list(range(N+1))  # 鳩→巣のインデックスが入る
nest = list(range(N+1))  # 巣の番号が入る
pigeon_nests = list(range(N+1))  # 中間テーブル

for i in range(Q):
    ope = list(map(int,input().split()))
    #print(i,ope)
    match ope[0]:
        case 1:
            # 鳩aを今いる巣から取り出し、巣bへ移動する。
            pigeon[ope[1]] = pigeon_nests[ope[2]]  # 鳩aがいる巣をbに変更
        case 2:
            # 巣aにいる鳩をすべて巣bへ移動し、巣bにいる鳩をすべて巣aへ移動する
            a,b = ope[1],ope[2]
            pigeon_nests_a, pigeon_nests_b = pigeon_nests[a], pigeon_nests[b]
            pigeon_nests[a], pigeon_nests[b] = pigeon_nests[b], pigeon_nests[a]
            nest[pigeon_nests_a], nest[pigeon_nests_b] = nest[pigeon_nests_b], nest[pigeon_nests_a]
        case 3:
            # 鳩 a が今いる巣の番号を報告する。
            print(nest[pigeon[ope[1]]])

• こちらは時間内に解けず
• 中間テーブルのような配列を用意して作れば解けるということがわかりました
• 次同じような問題出た時には、きっと解ける、、、はず！

感想

学生さん向け（いちおうHugkunやってるしね）

• A～Cは学生エンジニアとしてアルバイトしたい方など、プログラム練習中の方にはわりと丁度いい問題かと
• 競技プログラミングの勉強一切したこと無いので、テクニックは知らないです。たぶん、アイデアと力技で解いている方だと思うんですが、Hugkunでのスキルアップインターンの合格はだいたいC問題が解ければOKな感じなので、こんなんでも結構いけるとは思います（いちおうちょくちょく公表してるんですが、AtCoderレート300ぐらいの人が何人も1ヶ月以内で合格されていますので）

個人的な感想

• ジム行ってくっそ疲れてたので、疲労感から来る思考力低下・集中力欠如が響きましたね。4.7kmも走ったのは実はジムでは初めてでして・・・。
• D問題は中間テーブル的なものを使う問題で、解いてみるとすごく面白い問題でした
• 競プロはゲームとして楽しむと、やっぱりいいですね
• そういや鳩の問題が出ましたが、前も出たような・・・？AtCoderって鳩好きなんですかね？