はじめに
競技プログラミングを初心者なりに頑張っているのですが、「どう解いたかを記録して、将来的に見返せるようにするといいよ」なんてことを小耳に挟んだので、備忘録として書いてみます。
A - Shampoo
問題文要約：
父(A ml使用)・母(B ml使用)・高橋君(C ml使用)が、V ml残っているシャンプーを順番に減らしていきます。
足りなくなっちゃうのは誰？
考えたこと：
modを使うことも一瞬考えたけど、max(V) = 10^5なので、素直にVから減らしていくループを回し、負になった時点で終了すれば良さそう。
V, A, B, C = map(int, input().split())
while True:
if V-A < 0:
print("F")
break
else:
V -= A
if V-B < 0:
print("M")
break
else:
V -= B
if V-C < 0:
print("T")
break
else:
V -= C
3:22も掛かってるので、ちょっと遅かった。A問題は素直にシミュレートする思考だけに制限してもよさそう。
B - Hit and Blow
Wordle的なやつ。
問題文要約：
同じ長さ(N)の整数列A, Bが与えられます。
・同じ位置で同じ数字(Wordleの緑)の個数
・違う位置だけどどちらにも含まれている数字(Wordleの黄色)の個数
をそれぞれ求めてください。
考えたこと
「どちらにも含まれている数字」の集合からそれぞれの条件で分類する話だったので、とりあえず積集合でどちらにも含まれているものを取り出し、「積集合に含まれているかどうか → 位置が一致しているかどうか」で判定すれば良さそう。
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
AB = set(A)&set(B)
cnt1 = set()
cnt2 = set()
for i in range(N):
if A[i] in AB:
if A[i] == AB[i]:
cnt1.add(A[i])
else:
cnt2.add(A[i]
print(len(cnt1))
print(len(cnt2))
pythonのset型、めちゃめちゃ便利で多用しがち。→スーパー初心者の頃にset型に出会ったときの記事
C - Collision 2
問題文要約：
$xy$ 座標平面に $N$ 人います。
それぞれの人 $i$ は右左どちらか一方に動けますが、それは文字列Sの $S_i$ によって定まっています。
全ての人を動かし続けたとき、お互いにぶつかる人はいるでしょうか？
考えたこと
とりあえずyが同じ人同士でないと絶対にぶつからないので、yが同じ人同士をまとめ、その中でxを降順に並べ、「右に動く人」の右側に「左に動く人」が存在すればぶつかるので、それを判定した。
N = int(input())
array = []
for i in range(N):
x,y = map(int, input().split())
array.append([y,x])
S = list(input())
for i in range(N):
array[i].append(S[i])
array.sort()
flag = 0
for i in range(N-1):
if flag == 0:
if array[i][0] == array[i+1][0]:
if array[i][2] == "R":
flag = 1
if flag == 1:
if array[i][0] == array[i+1][0]:
if array[i+1][2] == "L":
print("Yes")
exit()
else:
flag = 0
print("No")
何を実装すれば良いのかは早めに思いついたのですが、Sのインデックスの管理とか、「yが同じ人同士をまとめ、その中でxを降順に並べる」をどうすればいいか手間取ってしまい、43分時点で提出。
結局 $[y,x,S_i]$ の順番でリストを作ってソートをかければ、ソートの優先順位的にうまくいくことに気づいた。
ぶつかるかどうかの判定についても、「yが同じ人たちの中で『右に動く人』がいる時点でフラグを立て、その後に『左に動く人』がいれば良い」というやり方で実装したが、解説ではもっとスマートに判定していたので、参考にしたい。
D - Moves on Binary Tree
問題文要約：
完全二分木があります。
文字列Sのi番目がUなら木の親に移り、Lなら左の子に移り、Rなら右の子に移るのをシミュレートしてください。
考えたこと
「なるほど、N = 10^6で乗除を愚直にやっていたらデカい数字のときに間に合わないからなんとかしてね」ってことか......まではすぐ考えた。ただ、一歩手前で撃沈。
この問題を解く数日前にビット演算についてちょっと触れていたので、「//2じゃなくて<< 1なら演算早いのでは？」と思ったんですが、そんなことはなかったらしい。
直接二進数の文字列として操作すれば良かったのか......。考え方は合ってたので悔しい。
まとめ
結局Dまでは解けなかったけれども、二進数でどうにかするという考え方自体は合っていたので満足してます。次は解き切れるように。