アルゴリズムの学習改善のための自身の備忘録及び学習の一環として記事を書くことにしました.
読んでくれた方で何かありましたら気兼ねなくコメントしてください.お待ちしております.
A - Digit Machine
問題文
1 桁の数字が表示される画面と、ボタンからなる機械があります。
画面に数字 k が表示されているとき、ボタンを 1 回押すと画面の数字が a
kに変わります。
0 が表示されている状態からボタンを 3 回押すと、画面には何が表示されますか？
制約
0≤$a_i$≤9
入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
$a_0 \ \ a_1 \ \dots \ \ a_9$
考察
1回目の操作で0 $\rightarrow a_0$
2回目の操作で$a_0 \rightarrow a_{a_0}$
3回目の操作で$a_{a_0} \rightarrow a_{a_{a_0}}$となり、これが答えになる.
サンプルコード
a=list(map(int,input().split()))
print(a[a[a[0]]])
B - Pasta
問題文
高橋君の家には N 本の麺からなるパスタがあり、i 本目の麺の長さは$A_i$です。
高橋君はこれから M 日間の食事計画を立てており、 i 日目にはパスタの麺のうち長さがちょうど$B_i$であるようなものを 1 本選び、食べようと考えています。 もし、1 日目から M 日目の間に 1 日でもそのような麺が無い日があれば、食事計画は失敗となります。 また、同じ麺を複数の日に食べることはできません。
高橋君が食事計画を最後まで実行することは可能ですか？
制約
1≤M≤N≤1000
$1≤A_i≤10^9$
$1≤B_i≤10^9$
入力はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
$N \ \ M$
$A_1 \ \ A_2 \ \dots \ \ A_N$
$B_1 \ \ B_2 \ \dots \ \ B_M$
考察
手元にある麺を配列Aとおき食べる麺を前から順にAから削除する.これをM本すべて出来るかで判定出来る.
これは$B_i$を探索するのに$O(N)$,削除に$O(N)$必要となる.これをM回繰り返すので$O(MN^2)$となり、最悪$10^9$制約から実行時間2sではまにあわない.
追記:削除ではなく値を範囲外(ex.-1,0)に変更する場合$O(NM)$で十分間に合う.
高速にするため、$A$を"key"に長さ、"value"に個数を入れた連想配列とし、$B_i$が$A$のkeyにあればvalueを1減らす、$A$に存在しないかvalueが負になったら'No' をそれ以外で'Yes'を出力すればよい.
pythonはsetによる存在判定は$O(1)$で出来るので$O(N+M)$で答えが出せる.この解法は十分高速である.
サンプルコード
n,m=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
d={}
s=set()
for i in a:
if i in s:
d[i]+=1
else:
d[i]=1
s.add(i)
ans="Yes"
for i in b:
if i not in s:
ans="No"
break
d[i]-=1
if d[i]<0:
ans="No"
break
print(ans)
C - Connect 6
問題文
N 行 N 列のマス目があり、それぞれのマスは白または黒で塗られています。
マス目の状態は N 個の文字列 $S_i$で表され、$S_i$の j 文字目が # であることはマス目の上から i 行目、左から j 列目のマスが黒く塗られていることを、 . であることは白く塗られていることをさします。
高橋君はこのマス目のうち高々 2 つの白く塗られているマスを選び、黒く塗ることができます。
マス目の中に、黒く塗られたマスが縦、横、ななめのいずれかの向きに 6 つ以上連続するようにできるか判定してください。
ただし、黒く塗られたマスがななめに 6 つ以上連続するとは、N 行 N 列のマス目に完全に含まれる 6 行 6 列のマス目であって、その少なくとも一方の対角線上のマスがすべて黒く塗られているようなものが存在する事をさします。
制約
6≤N≤1000
$∣S_i∣=N$
$S_i$は # と . のみからなる。
入力
N
$S_1$
$S_2$
$S_3$
$\vdots$
$S_N$
考察
左上から順に右、下、右下、左下へのそれぞれ6マスが条件を満たすかを全探索すれば漏れなく判定出来る.
探索の際、範囲外参照しないように注意しなければならない.
これは$O(N^2)$で判定できる.pythonは遅い言語なので間に合わないが、pypyは高速なので十分に間に合う.
追記:定数倍が24倍程度必要となり高速な言語出なければTLEを起こす可能性がある.
サンプル
n=int(input())
s=[input() for _ in range(n)]
for i in range(n):
for j in range(n):
check=0
if s[i][j]==".":
check+=1
if j+6<=n:
cnt=check
for k in range(1,6):
if s[i][j+k]==".":
cnt+=1
if cnt>2:
break
if k==5:
print("Yes")
exit()
if i+6<=n:
cnt=check
for k in range(1,6):
if s[i+k][j]==".":
cnt+=1
if cnt>2:
break
if k==5:
print("Yes")
exit()
if i+6<=n and j+6<=n:
cnt=check
for k in range(1,6):
if s[i+k][j+k]==".":
cnt+=1
if cnt>2:
break
if k==5:
print("Yes")
exit()
if 0<=i<=n-6 and 5<=j:
cnt=check
for k in range(1,6):
if s[i+k][j-k]==".":
cnt+=1
if cnt>2:
break
if k==5:
print("Yes")
exit()
print("No")