2022年6月18日開催のAtcoder Beginner Contest 256を、備忘的にギリ茶の私の回答を残しておきます。
コンテンツ一覧
A - 2^N
問題文
N が与えられます。2N を出力してください。
制約
- 0≤N≤30
- N は整数である
回答へのアプローチ
速解優先で、単純に書きました。
N = int(input())
print(2**N)
#実行時間:70 ms他の書き方としては、Pythonにはpow関数があります。pow関数は第3引数に整数を指定でき、べき乗の結果を第3引数で割った剰余を出力します。
何も指定しない場合は、べき乗を出力します。PyPy3で実行していますが、Pow関数の方が実行時間は長くなりました。
N = int(input())
print(pow(2,N))
#実行時間:162 msまた、今回は2のべき乗なのでビットシフトでも求められます。なんとなくスマートな感じを受けますね。
N = int(input())
print(1<<N)ちなみに、累乗とべき乗の違いは、前者は指数が整数の時、後者は整数かどうかは問わない言い方らしいです。
B - Batters
問題文
高橋君は野球をモチーフにしたゲームを作ろうとしましたが、うまくコードが書けなくて困っています。
高橋君の代わりに次の問題を解くプログラムを作ってください。
マス 0, マス 1, マス 2, マス 3 の 4 つのマス目があります。はじめマスの上には何もありません。
また、整数 P があり、はじめ P = 0 です。
正の整数からなる数列 A = (A1,A2,…,AN) が与えられるので、 i=1,2,…,N について順番に次の操作を行います。
- マス 0 に駒を 1 個置く。
- マス上のすべての駒を番号が Ai 大きいマスに進める。言い換えると、駒がマス x にあればその駒をマス x + Ai に移動する。
ただし移動先のマスが存在しない (すなわち x + Ai が 4 以上になる) 駒たちに関しては、それらを取り除いて P に取り除いた個数を加算する。
すべての操作を行った後の P の値を出力してください。
制約
- 1 ≤ N ≤ 100
- 1 ≤ Ai ≤ 4
- 入力される値はすべて整数
数列の長さNと数列Aが与えられます。
回答へのアプローチ
題目通り野球をモチーフにしており、マス１・２・３が１塁２塁３塁を指し、マス０がバッターボックスのようなイメージでしょうか。
N人の打者がバッターボックスに入り、それぞれが Ai 塁打を打ちます。1 ≤ Ai ≤ 4 という制約から、凡打は無くヒット以上を打つ感じですね。野球盤のような感じです。
勿論、野球のルールを知らなくても問題なく解けるようにはなっていますが、野球でイメージできるとやるべきことがわかりやすい問題なのかもしれません。
と、偉そうにいってますが、本番では何故か野球でイメージが出来なくて苦戦したのでした。。。
私が本番で提出したコードは大変恥ずかしいです。Aiごとに条件分岐させ、各マスの状態をベタ書きで管理するという。。
N = int(input())
A = list(map(int,input().split()))
M = [0]*4 #マスの状態を管理するリスト
P = 0
for i,a in enumerate(A):
M[0] += 1
if a == 1:
P += M[3]
M[3] = M[2]
M[2] = 0
M[2] = M[1]
M[1] = 0
M[1] = M[0]
M[0] = 0
elif a == 2:
P += (M[2]+M[3])
M[3] = M[1]
M[1] = 0
M[2] = M[0]
M[0] = 0
elif a == 3:
P += (M[1]+M[2]+M[3])
M[3] = M[0]
M[2] = 0
M[1] = 0
M[0] = 0
else:
P += sum(M)
M = [0]*4
print(P)反省点
- 何故かマス状態を管理するリストを１つでやろうとしていた
- 一時的に各マスに複数人存在することは許容できたのに、頑なに0か1で管理
公式解説では、今のマス目の状態を管理するリストと、次の状態のリストを別管理していました。まあ、確かにという感じです。
ですが、今回の問題の性質から 1 つのマスに2人以上存在することはなく、かつ、全てのマス上の人が一律のマス数しか進まないので、マス3から処理していけばマス管理リストが 1 つでも割とシンプルに処理が出来ることに気づきます。
後出しじゃんけんですが、修正した回答が以下です。
N = int(input())
A = list(map(int,input().split()))
M = [0]*4 #マスの状態を管理するリスト
P = 0
for a in A:
M[0] = 1
for i in reversed(range(4)): #マス3から処理していく。
if M[i] and i + a >= 4: #マス上に人が存在かつ4以上なら、Pに加算
P += 1
elif M[i]:
M[i+a] = 1
M[i] = 0
print(P)C - Filling 3x3 array
問題
6 個の整数 h1,h2,h3,w1,w2,w3 が与えられます。
縦横 3×3 のマス目に、以下の条件をすべて満たすように各マスに正の整数を 1 つずつ書きこむことを考えます。
- i=1,2,3 について、上から i 行目に書きこんだ数の和が hi になる。
- j=1,2,3 について、左から j 列目に書きこんだ数の和が wj になる。
例えば (h1,h2,h3)=(5,13,10),(w1,w2,w3)=(6,13,9) のとき、以下の 3 通りの書きこみ方はすべて条件を満たしています。(条件を満たす書きこみ方は他にもあります)
さて、条件を満たす書きこみ方は全部で何通り存在しますか？
制約
- 3 ≤ h1, h2, h3, w1, w2, w3 ≤ 30
- 入力される値はすべて整数
回答へのアプローチ
まずは横軸の時だけを考えます。それぞれの横軸での和のパターンを全列挙し、リストに格納します。
3行あるので3つのリストを3重ループにかけ、今度は縦軸の条件に合致するかを判定していき、合致数を出力します。
h1,h2,h3,w1,w2,w3 = map(int,input().split())
def pattern(N): #１以上の整数を３つ足して引数Nになるパターン全てを出力する関数。
P=[]
for i in range(N-2):
for j in range(N-2-i):
P.append([i+1,j+1,N-i-j-2])
return P
#横軸のみで条件に合致するパターンを全列挙します。
P1 = pattern(h1)
P2 = pattern(h2)
P3 = pattern(h3)
R = 0
#縦軸でも条件に合致するものを３重ループで探していきます。
for p1 in P1:
for p2 in P2:
for p3 in P3:
if (p1[0]+p2[0]+p3[0] == w1) and (p1[1]+p2[1]+p3[1] == w2) and (p1[2]+p2[2]+p3[2] == w3):
R += 1
print(R)h1が30の時、列挙されるパターンはこの制約上最大の406通りとなります。3重ループ全て406通りでも、実行時間は0.5秒程度だったので十分な速度です。
D - Union of Interval
問題
実数 L,R に対して、L 以上 R 未満からなる実数の集合を [L,R) と表します。このような形で表される集合を右半開区間といいます。
N 個の右半開区間 [ Li , Ri ) が与えられます。これらの和集合を S とします。S を最小の個数の右半開区間の和集合として表してください。
制約
- 1 ≤ N ≤ 2×105
- 1 ≤ Li < Ri ≤ 2×105
- 入力に含まれる値は全て整数である
回答へのアプローチ
とりあえず、制約の長さ2×105 のリストを作り、入力される区間の部分を全部 1 で埋めます。その後、リストを先頭から見ていき、1が連続している部分の区間を出力するというやり方をしました。TLEです。結局このTLEを解決できずじまいでした。
K = [0] * (2*(10**5)+1)
N = int(input())
for _ in range(N):
L,R = map(int,input().split())
K[L-1:R-1] = [1] * (R-L)
k_ok = False
R = []
for i in range(len(K)):
if K[i] == 1 and not(k_ok):
start = i+1
k_ok = True
elif k_ok and K[i] == 0:
k_ok = False
goal = i+1
R.append([start,goal])
for r in R:
print(r[0],r[1])公式解説では、Lをログイン時間、Rをログアウト時間と見立てて1人以上がログインしている時間の区間を求めると読み替えるとわかりやすいと書いてあります。
ログインユーザが0から1になる瞬間と、1から0になる瞬間を記録していけば良いことになります。
前処理として、LとRをまとめてソートしてしまいます。この時LとRの区別が付くように、二次元配列として保管します。また、ログインユーザの人数さえわかれば良いので、誰のログインかログアウトかを紐づけて保存する必要性はありません。
ログインとログアウトが同時刻に行われた際は、ログインを先に処理します。なのでソートして前から順に処理する際にログインから処理されるように、二次元配列として保管する際はログインを0、ログアウトを1とします。
N = int(input())
Q = []
for _ in range(N):
L,R = map(int,input().split())
Q.append([L,0]) #ログイン
Q.append([R,1]) #ログアウト
Q.sort()
active = 0 #ログインユーザ数を管理する変数
R = [] #出力リスト
for q,f in Q:
if f == 0 and not(active): #ログインかつ誰もログインしていない状態の時に、startに時刻を入れます。
active += 1
start = q
elif f == 0:
active += 1
else: #ログアウトで、ユーザを減らします。
active -= 1
if active == 0: #ユーザが0になってしまったら、goalに時刻を入れ、startとセットにして出力リストに入れます
goal = q
R.append([start,goal])
for r in R:
print(*r)