アルゴリズムの学習改善のための自身の備忘録及び学習の一環として記事を書くことにしました.
読んでくれた方で何かありましたら気兼ねなくコメントしてください.お待ちしております.
A - Shampoo
問題文
高橋君の家には、高橋君、高橋君の父、高橋君の母の 3 人が住んでおり、全員が毎晩風呂で髪を洗います。
風呂には、高橋君の父、高橋君の母、高橋君の順に入り、それぞれシャンプーを A,B,C ミリリットル使います。
今朝の時点で、ボトルには V ミリリットルのシャンプーが残っていました。このまま補充しない時、初めてシャンプーが不足するのは誰が使おうとした時ですか？
制約
1≤V,A,B,C≤$10^5$
入力に含まれる値は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
V A B C
考察
3人全員が使える限り使い続けるため、V$\equiv$V (mod (A+B+C))とする.
V<Aであれば'F'、V<A+Bであれば'M'、V<A+B+Cであれば'T'を出力すれば良い
サンプルコード
V,A,B,C=map(int,input().split())
V%=(A+B+C)
cnt=0
if V<A:
print("F")
elif V<A+B:
print("M")
else:
print("T")
B - Hit and Blow
問題文
長さ N の整数列$A=(A_1,A_2, \dots,A_N),B=(B_1,B_2,\dots ,B_N)$ が与えられます。
A の要素はすべて異なります。B の要素もすべて異なります。
次の 2 つを出力してください。
- A にも B にも含まれ、その位置も一致している整数の個数。言い換えると、$A_i=B_i$を満たす整数 i の個数
- A にも B にも含まれるが、その位置は異なる整数の個数。言い換えると、$A_i=B_j,i \neq j$ を満たす整数の組 $(i,j)$ の個数。
制約
$1 \leq N \leq 1000$
$1\leq A_i \leq 10^9$
$1\leq B_i \leq 10^9$
$A_1,A_2,\dots ,A_N$はすべて異なる。
$B_1,B_2,\dots ,B_N$はすべて異なる。
入力はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
$N$
$A_1 \ \ A_2 \ \ \dots \ \ A_N$
$B_1 \ \ B_2 \ \ \dots \ \ B_N$
考察
1つ目の出力は愚直に調べれば求まる.
2つ目の出力について考える.
AとBに同じ値が含まれていれば集合を取ると重複なく数えることできる.
AとBの総数2Nからこれを引くと、同じ値の個数を得られる.
ここから同じ位置に当てはまる値の個数(1つ目の解)を引くと求める値となる
- 値と位置が一致する個数
- 2NからAとBの和集合の長さと位置と値が一致している個数を引いたもの
これを出力すればよい．
サンプルコード
N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
ans1=0
for i in range(N):
if A[i]==B[i]:
ans1+=1
ans2=2*N-len(set([*A,*B]))-ans1
print(ans1)
print(ans2)
C - Collision 2
問題文
xy 座標平面上に N 人の人がいます。人 i は $(X_i,Y_i)$ にいます。すべての人は異なる地点にいます。
L, R からなる長さ N の文字列 S があります。
人 i は $S_i=R$ ならば右向きに、$S_i=L$ ならば左向きに、一斉に同じ速度で歩き始めます。ここで、右は x 軸の正の向き、左は x 軸の負の向きです。
たとえば $(X_1,Y_1)=(2,3),(X_2,Y_2)=(1,1),(X_3,Y_3)=(4,1),S= RRL$ の場合は次の図のように動きます。
反対の向きに歩いている人同士が同じ地点に来ることを「衝突」と呼びます。すべての人が歩き続けたとき、衝突は発生しますか？
制約
$2 \leq N \leq 2 \times 10^5$
$0 \leq x_i \leq 10^9$
$0\leq y_i \leq 10^9 $
$i\neq j$ならば$(X_i,Y_i)\neq (X_j,Y_j)$である
$SはL および R からなる長さ N の文字列である。
入力
入力は以下の形式で標準入力から与えられる。
$N$
$X_1 \ \ Y_1$
$X_2 \ \ Y_2$
$\vdots$
$X_N \ \ Y_N$
$S$
考察
- y軸座標が同じかつL,Rの両方が無ければ衝突することが無い.
- 上の条件を満たす上で、左方向に向かって歩く人Aと右方向に歩く人Bのx座標がB<Aとなっている必要がある.
以上を満たすかを判定する.
y軸情報と左右どちらに動くのかを連想配列で保有する.
左右の移動情報は集合の形で保有することで1つ目の条件の判定が$O(1)$で出来る.
左右の両方に移動する条件を満たす際に2つ目の条件を満たすことを調べる．
1つ目の条件の判定で使用する連想配列のキーの値にx座標と左右のどちらに移動するかの情報も保有すると判定に必要な値を$O(1)$で取り出すことが出来る．
これを用い2つ目の条件を満たすかを調べる．
サンプルコード
N=int(input())
XY=[list(map(int,input().split())) for _ in range(N)]
S=input()
DICT=dict()
SET=set()
for i in range(N):
if XY[i][1] in SET:
DICT[XY[i][1]][0].add(S[i])
DICT[XY[i][1]][1].append([XY[i][0],S[i]])
else:
SET.add(XY[i][1])
DICT[XY[i][1]]=[set(S[i]),[[XY[i][0],S[i]]]]
ans="No"
for i in DICT:
if len(DICT[i][0])==2:
L,R=0,10**9
for j in DICT[i][1]:
if j[1]=="L":
L=max(j[0],L)
else:
R=min(j[0],R)
if R<L:
ans="Yes"
print(ans)
D - Moves on Binary Tree
問題文
頂点数${2^{10}}^{100}-1$の完全二分木があり、頂点には$1,2,\dots ,{2^{10}}^{100}-1$の番号がついています。
頂点 1 が根であり、各$1\leq i \leq {2^{10}}^{100}-1 $ について、頂点 i は 頂点 2i を左の子、頂点 2i+1 を右の子として持ちます。
高橋君は最初頂点 X におり、N 回移動を行います。移動は文字列 S により表され、i 回目の移動は次のように行います。
- S の i 番目の文字が U のとき、今いる頂点の親に移動する
- S の i 番目の文字が L のとき、今いる頂点の左の子に移動する
- S の i 番目の文字が R のとき、今いる頂点の右の子に移動する
N 回の移動後に高橋君がいる頂点の番号を求めてください。なお、答えが $10^{18}$以下になるような入力のみが与えられます。
制約
$1 \leq N \leq 10^6$
$\leq X \leq 10^{18}$
N,X は整数
S は長さ N であり、U,L,R のみからなる
高橋君が根にいるとき、親に移動しようとすることはない
高橋君が葉にいるとき、子に移動しようとすることはない
高橋君が N 回の移動後にいる頂点の番号は $10^{18}$以下である
入力
入力は以下の形式で標準入力から与えられる。
N
S
考察
多倍長整数の計算はとても遅く現実的ではない．
そこで高速化することを考えなければならない．
木であるため、子へ移動の後に親に移動すると、元いた位置に戻ってくることは容易に想像出来る．
移動先を先に計算することにより、同じ頂点に移動すること無く最短で答えにたどり付ける．
現在の位置を$x$とするとき、完全二分木なので親への移動は$\left\lfloor \frac{x}{2}\right\rfloor $、左の子への移動は$2\times x$右の子への移動は$2 \times x+1$となる．
親への移動の際に、根が1であることに注意すればこたえは求まる．
サンプルコード
from collections import deque
n,x=map(int,input().split())
s=list(input())
move=deque()
move.append(s[0])
for i in range(1,n):
if s[i]=="U" and len(move)!=0 and move[-1]!="U":
move.pop()
else:
move.append(s[i])
for i in move:
if i=="U":
x=max(1,x//2)
elif i=="R":
x=x*2+1
else:
x*=2
print(x)