この記事は問題の復讐のため、短時間で問題を解くときの自分の思考をざーっと書いた日記ぽいなものですのでわかりにくかったら申し訳ございません！
Atcoder 412 (perf 1001, rating 631 -> 676)
Cまでしか解けなかったのに1001perf...初心者に厳しい問題セットだったかなーと思います
A
![[Pasted image 20250628230439.png]]
n行の入力で a_i < b_iの数を数える問題
コード
#input
n = int(input())
ans = 0
for i in range(n):
a, b = map(int, input().split())
if a < b:
ans += 1
print(ans)
行別に入力をもらい、a, bを比較してbが大きいとansを+=1しました！
B
S の先頭でない英大文字の直前の文字はすべて T に含まれるかを確認する問題。
AtCoder
Total
#ここではtが'Total'に含まれるので'Yes'を出力
Pythonなら.isupper()を用いると簡単に英大文字の判別ができます！
コード
#input
n = str(input().rstrip())
m = set(str(input().rstrip()))
for i in range(len(n) - 1):
now = n[i + 1]
if now.isupper():
if n[i] not in m:
print('No')
sys.exit()
print('Yes')
C
問題文の条件が複雑ですので、この記事では解法の説明だけ載せます！
まず、各々のテストケースでもらう数字列中、最初のドミノと最後のドミノは決まっているため、分割しました。
また、答えは条件を満たすドミノの並べ方は存在しますか？また、存在する場合は最小で何個のドミノを並べる必要がありますか？このように、存在する場合は最小で何個を求める問題であるため、貪欲法を検討しました。
まず、lstの変数に数字列をリスト形式で入力します。
また、上述したよう最初のドミノと最後のドミノ、それ以外のドミノ数列リストで分割します。
n = int(input())
lst = list(map(int, input().split()))
now = lst[0]
end = lst[-1]
llst = lst[1:-1]
llst.sort()
まず、条件を満たすドミノの並べ方は存在するのかを確認するため、最後のドミノを倒すために必要な中間のドミノを選ぶ戦略を考えます。
最後のドミノ（end）を右に倒すためには、その直前のドミノをxとするとx * 2 ≥ end を満たす必要があります。
この条件を満たすxをllstの中からなるべく小さいものを貪欲に選んで、倒れる連鎖を作ります。
また、この段階はbisectを用いて、indexをもらうことでより計算しやすくしました！
これを繰り返し、最初のドミノ(now)にたどり着けるかを判定します。
具体的には、ソートしたllstを二分探索で使い、endを倒せる最小のxを探します
そのxを使ってendを更新します（end = x）
もしllst内にx * 2 ≥ endを満たすxがなければ失敗です。
whileループでこの更新を繰り返し、最終的にend ≤ 2 * nowになれば、全てのドミノが倒せます。
したがって、正解コードは
コード
#input
tc = int(input())
for _ in range(tc):
n = int(input())
lst = list(map(int, input().split()))
ans = 2
now = lst[0]
end = lst[-1]
llst = lst[1:-1]
llst.sort()
flag = True
while end > now * 2:
newlst = [i * 2 for i in llst]
lft = bisect.bisect_left(newlst, end)
llft = bisect.bisect_left(newlst, end * 2)
if lft == llft:
print('-1')
flag = False
break
ans += 1
end = newlst[lft] // 2
#-1をプリントしてまたansをプリントすることを防ぐためflagをcheck
if flag:
print(ans)