ABC201参戦記

マイナビさんが主催してくれたAtCoder Beginner Contest 201の参加記録です。

レート600前後の私が自分が理解した内容を書いていきます。
使用言語はPython3です。

A – Tiny Arithmetic Sequence

標準入出力とソート、条件分岐の問題。

他の方法もあるとは思うのですが、A問題でソートに関する問題が出るとは予想外でしたね。

等差数列の条件については問題文に書いているので、ソートして、記載通りの条件式を書き、Trueなら”Yes”、Falseなら”No”を出力すればOKです。

# マイナビプログラミングコンテスト2021（AtCoder Beginner Contest 201）
# A - Tiny Arithmetic Sequence

A=list(map(int,input().split()))

A.sort()

if A[2]-A[1]==A[1]-A[0]:
    print("Yes")
else:
    print("No")

今回の出力は、”Yes”や”No”の大文字/小文字が違っているとWAになるので注意する必要があります。

B – Do you know the second highest mountain?

繰り返し処理と、2次元配列のソート、ソートするkeyのデータ型(strとintの違い)について問われる問題。

最近のB問題難しくないですかね。

この問題が特に難しいと考えるポイントは2つです。

• 型が異なる入力が1行で与えられること。
• 入力は、 山名 高さ の順番で与えられるが、ソートするのは高さでソートすること。

繰り返し処理はfor文を利用するとして、二次元配列のソートは各要素(一次元配列)を順番に見ていき、はじめに異なるものが来たら、その値の大小関係でソートされるようです。
また、要素同士で比較する対象が存在しない場合は、短いほうが、小さくなるようです。
詳しくは、こちらのサイトや公式ドキュメントを確認ください。

まず、Pythonで1行で複数の入力を受け取るときには、それぞれの変数を用意して、map関数を利用するのが良いと思います。
しかし、map関数では、標準入力で受け取る型を通常一つしか設定できません。

制約から、山名は英字が使用されることがわかっているので、str型で受け取るしかありませんね。

また、二次元配列のソートは比較対象となるものの中の要素を順番に見ていき、異なるもの同士を比較するようです。
入力の順番通りに二次元配列を用意し、普通にソートすると、山名の順番でソートされてしまいます。
今回比較したいのは、山名ではなく、高さです。
二次元配列に格納する際に、入力時に用意した変数の順番を入れ替えて格納すると高さでソートすることが可能になります。

あとはソートして、最後から2つ目を出力すればOKかと思いきや、高さをstr型でソートしてしまうとWAになります。

nums_1=["10","1"]
nums_1.sort()
print(nums_1)
 # -> ['1', '10']

nums_2=["2","10"]
nums_2.sort()
print(nums_2)
 # -> ['10', '2']

これは、数字を文字列としてソートしてしまうことによる弊害なので、文字列として受け取っている高さを整数型へ変換すれば、数値でソートしてくれるようになります。

整数型への変換は　int() 関数を利用すればOKです。

これでようやく正しい状態にソートできているので、最後から2番目の山名を取得し答えを出力すればACします。

最後から2つ目は、Python3の配列では、スライス操作の[-2]を利用すればOKです。制約から2つ以上の山はあることが保証されているため、配列外参照のエラーも起こりません。

# マイナビプログラミングコンテスト2021（AtCoder Beginner Contest 201）
# B - Do you know the second highest mountain?

N=int(input())
mountains=[]

for i in range (N):
    S,T=map(str,input().split())
    T=int(T)
    mountains.append([T,S])

mountains.sort()

print(mountains[-2][1])

私はコンテスト中には、ここまでソートの特性を理解していなかったので、二次元配列の2つ目の要素(index=1)でソートするよう、ソートするkeyをlamda関数で指定するという無駄な記述してしまいました。

C – Secret Number

全探索の問題。

今回、コンテス中にC問題解くことが出来ませんでした。
ずっと筋の良くない包含と排除の原理(包除原理)の方針で考えていて、最後10分で全探索のコードを書き始めたのですが、間に合いませんでした。解説を見ずに提出して、2回のWAの後にACしました。

解法については、暗証番号になりえるパターンを”0000″から”9999″まで全部確認し、条件に合う場合を数え上げていけばよいですね。

二重ループになるため、TLEになると考えてしまい、包除原理で解こうと思ったのですが、二重ループの中の実行回数が少ないことに気づけませんでした。

全探索する中でのポイントは3つだと思います。

• 3桁以下の数を4桁の数字にする。
• 確実に含まれていなかった数字の場合は、数え上げない。
• 確実に含まれていた数字がすべて使用されていない場合は、数え上げない。

3桁以下の数(num)を4桁の数字にするには、文字列にして、str(num).zfill(4) とすればOKです。

解くための方針は次のような感じです。

• 記憶をもとに、各indexに3種類のデータを持つ。今回私は、"x"=-1, "?"=0, "o"=1 と持ちました。
• 4桁の暗証番号をfor文で回して以下の条件で判定する。
• 確実に含まれていない数が使用されていたらbreakする。
• 確実に含まれている数は、使用したら、使用済みのチェックをする。(“?”と同じ扱いということで、データの値を0にする。)
• 確実に含まれている数が残っていたら数え上げない。
• これらを確認するため、毎回記憶をコピーする。

これらを実装して、ACしました。

# マイナビプログラミングコンテスト2021（AtCoder Beginner Contest 201）
# C - Secret Number
S=input()

memory=[0]*10

for i in range (10):
    if S[i]=="o":
        memory[i]=1
    if S[i]=="x":
        memory[i]=-1
    if S[i]=="?":
        memory[i]=0

cnt=0

for i in range (10000):
    n=list(str(i).zfill(4))
    temp_memory=memory[:]
    for j in range (4):
        if memory[int(n[j])]==-1:
            break
        if memory[int(n[j])]>=0:
            temp_memory[int(n[j])]=0
    else:
        temp_memory=set(temp_memory)
        if 1 not in temp_memory:
            cnt+=1

print(cnt)