ABC276のA,B,C,D,E問題をpythonで解説していきます。
A問題
考察
最後に現れる “a” の位置が知りたいので、末尾から探索を行います。
末尾から探索した結果、最初に “a” が出てきた場所が、文字列Sにとって最後に現れる “a”の位置になります。
コード
import sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def II(): return int(sys.stdin.readline())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def S(): return sys.stdin.readline().rstrip()
readline = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
letter = S()
for i in range(len(letter)-1,-1,-1):#末尾から探索
if letter[i] == "a":
print(i+1)#pythonはindexが0始まりなので、+1
exit()
print(-1)#最後まで探索しても出てこなかったら -1B問題
考察
どの都市が、どの都市とつながっているかを記憶しなければならないので、都市ごとにつながっている都市リストを作成します。
(※そのため、二次元配列になります)
その後、都市ごとにある都市リストをソートして、出力すれば良いです。
コード
import sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def II(): return int(sys.stdin.readline())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def S(): return sys.stdin.readline().rstrip()
readline = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
N,M = MI()
node = [[] for i in range(N)]#都市ごとに(空の)都市リストを用意
for i in range(M):
a,b = MI()
a -= 1#0 始まりに揃えるため -1
b -= 1# 0始まりに揃えるため -1
node[a].append(b+1) #けど出力するときは +1しなきゃいけない
node[b].append(a+1) #けど出力するときは +1しなきゃいけない
for i in range(N):
node[i].sort()
print(len(node[i]),*node[i], sep=" ")C問題
考察
まず、最初にどのような条件が辞書順最小と言えるかを考えます。
ex) [1,2,3]の場合
123, 132, 213, 231, 312, 321
となります。
このことから何が言えるかというと、
「辞書順を1だけ小さくしたいのなら、末尾から変化させる必要がある」
ことがわかります。
では、次に 「どのようなときに辞書順は-1されるのか」について考えます。
sample2では
input) 9 8 6 5 10 3 1 2 4 7 output) 9 8 6 5 10 2 7 4 3 1
となっており、7桁目(1)から10桁目(7)までは、数字が単調に増加していることがわかります。
つまり、7~10桁目の[1,2,4,7]は、すでに辞書順最小になっていることがわかります。
しかし、6桁目(3) > 7桁目(1)より、6~10桁目までの [3,1,2,4,7]はまだ辞書順小さくすることができます。今回は、辞書順を1だけ小さくしたいので、
- 6桁目の数字を3よりも小さくかつ、一番近い数字にする
- 7桁目以降は、辞書順最大にする
にすれば、辞書順を1だけ小さくすることができました。
コード
import sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def II(): return int(sys.stdin.readline())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def S(): return sys.stdin.readline().rstrip()
readline = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
import copy
N = II()
P = LI()
for i in range(N-1,-1,-1):
if P[i] < P[i-1]:
ans = P[:i-1]# 先頭からi-1桁目までは変化なし
flg = P[i-1:]#i桁目からN桁目までは変化する
break
flg_copy = copy.copy(flg)#変化する数列
flg_copy.sort()#小さい順に並び替え
ind = flg_copy.index(flg[0])#i桁目の数字が何番目に小さいか調べる
head = [flg_copy[ind-1]]#i桁目の数字より辞書順が1小さい数字(head)を取る
flg_copy.pop(ind-1)
flg_copy.sort(reverse=True)#headを除いた、 i~N番目の項を辞書順最大にする
ans1 = head + flg_copy
final_ans = ans+ans1# くっつけて出力
print(*final_ans, sep=" ")D問題
考察
まず、最初にa1 = a2 = an を満たすのがどうゆうときかを考えます。
それは、a1 から an までのすべての数字が、2と3で割り続けたときに、同じ数字になるときです。
ですが、2と3で割り続けて、最終的に同じ数字なったら、その操作回数を出力すれば良いというわけでもありません
例えば、 [2,2,2]という数列が与えられたとき、上記の操作だと、3回操作を行ってしまいますが、実際は0を出力する必要があります。
なので、その数を2と3で割った回数を記憶しておき、その割った回数が最小の数分だけ、全体から引けば良いです。
コード
import sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def II(): return int(sys.stdin.readline())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def S(): return sys.stdin.readline().rstrip()
readline = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
N = II()
A = LI()
def two_by_three(x):
two_cnt = 0
three_cnt = 0
while x%2==0 or x%3 == 0:
if x%2 == 0:
x//=2
two_cnt += 1#2で割った回数を記憶
if x%3 == 0:
x//=3
three_cnt += 1#3で割った回数を記憶
return x,two_cnt,three_cnt
box = []
two_box = []
three_box = []
ans = 0
for i in range(N):
x,two,three = two_by_three(A[i])
box.append(x)
two_box.append(two)
three_box.append(three)
ans += two
ans += three
if len(set(box)) != 1:#全部、同じ数字じゃないなら -1
print(-1)
exit()
two_box.sort()
min_two = two_box[0]
three_box.sort()
min_three = three_box[0]
print(ans - min_two*N -min_three*N)#全体で割った回数- 2で割らなくても良かった回数 - 3で割らなくても良かった回数 E問題
考察
スタート位置から、同じ道を通らないようにして、スタート位置に帰ってこられるかという問題です。(同じ道を通らないのであれば、必ず4つ以上のマスを移動するため)
そのため、dfsを用いて、大きく一筆書きする経路の途中で、現在地を通ることができるかを考えれば良いです。
※ pypy3 だと 通らなかったので、python3.82で通しました。
コード
import sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def II(): return int(sys.stdin.readline())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def S(): return sys.stdin.readline().rstrip()
readline = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
H,W = MI()
box = []
for i in range(H):
a = S()
box.append(a)
for j in range(W):
if a[j] == "S":
start = [i,j]
drdc = [[-1, 0], [1, 0], [0, -1], [0, 1]]
seen = [[False]*W for _ in range(H)]
dist = [[0]*W for _ in range(H)]
#本来は初期位置はTrueにして、スタート位置に戻れないようにしますが、今回は大丈夫
def dfs(y,x,prex,prey):
for dr,dc in drdc:
nx = x+dr
ny = y+dc
if prex == nx and prey == ny:#もし現在地が、過去から来た場所からなら× startへの逆戻りを防ぐため
continue
if 0 <= nx < W and 0 <= ny < H:
if seen[ny][nx]== True or box[ny][nx] == "#":
continue
seen[ny][nx] = True
dist[ny][nx] = dist[y][x]+1
if ny == start[0] and nx == start[1]:
break
dfs(ny,nx,x,y)
dfs(start[0],start[1],-1,-1)
# for x in dist:
# print(x)
if dist[start[0]][start[1]] >= 4:
print("Yes")
else:
print("No")
コメント