解き方を忘れないためにまとめてるだけなのでコードはめちゃくちゃ不細工です、ここもっと良くできるよって場所あったら教えていただけるとありがたいです！！
231 Counting 2
import bisect
n,q = map(int, input().split())
alist = sorted(list(map(int, input().split())))
for _ in range(q):
x = int(input())
print(n - bisect.bisect_left(alist,x))
この問題はbisectを使うだけで簡単にとけてしまいます。まずbisect_leftを使って、alistの中でxの数字を挿入できる位置のindex番号を取得します(xより小さい数字の数)。次に、xより大きい数字の数を調べ上げるために、全体数nからさっき取得した値を引き出力すればACです
232 Graph Isomorphism
from itertools import permutations
def judge(perm):
for i in range(n):
for j in range(n):
if AB[perm[i]][perm[j]] != CD[i][j]:
return False
return True
n,m = map(int, input().split())
AB = [[False]*n for _ in range(n)]
CD = [[False]*n for _ in range(n)]
for _ in range(m):
a,b = map(int, input().split())
AB[a-1][b-1] = True
AB[b-1][a-1] = True
for _ in range(m):
c,d = map(int, input().split())
CD[c-1][d-1] = True
CD[d-1][c-1] = True
for perm in permutations(range(n)):
if judge(perm):
print("Yes")
exit()
print("No")
この問題は、制約の1≤N≤8から、bit全探索か順列全探索のどちらかを使うんだろーなとなんとなくイメージできます。そして問題文のおもちゃが同じと証明する条件の一つ"P は (1,…,N) を並べ替えて得られる。"から、順列全探索使うんやろなーとなります。なのであらかじめ、itertoolsからpermutationsをインポートしておきましょう。そして、この問題を解く上で一番重要な情報のどのボールと、どのボールがつながっているのかを保有しておくためのABリストとCDをつくっときましょう。(booleanは偉大やね)次に情報を受けとっていき、さっき作ったリストの情報を更新していきましょう(index番号は0から始まるから、操作しやすいように-1をしている)。そして楽しい楽しい全探索マンの時間です。permutationsを使って配列のパターンを洗い出していきましょう(remember!インデックス番号は0から始まるからここでも、それに従っていくゾ、大切なことなので2回言いました)。判定の部分ではCDをベースにして判定していきました(ABにただのiとjを使っても結果は変わらないので好みの問題です、私はCDの方がエロかったのでそっちを選びました)。条件の2つ目に従って、言われた通りの処理をして、判定していきます。そして成立するなら、yesを出力して処理を終わらせ、全て調べても成立するものがなかった場合にはnoを出力していきます。
233 Product
from sys import setrecursionlimit
setrecursionlimit(10**7)
def dfs(num, total):
if num == n:
if total == x:
return 1
else:
return 0
cnt = 0
for choice in choices[num]:
cnt += dfs(num+1,total*choice)
return cnt
n,x = map(int, input().split())
choices = []
for _ in range(n):
l,*alist = map(int, input().split())
choices.append(alist)
print(dfs(0,1))
この問題にはいろんな解き方があるみたいですが、私はDFSを使って解きました。イメージとしては最後の袋の深さまで行ったら、最初に戻ってやり直すを繰り返す的なイメージです(伝わってなさそう...)。まず再起関数を含めたDFSを回す場合にはsysからsetrecursioinlimitを設定して、再起関数を回す回数のリミットを設けてあげる必要があります。正直テンプレなんで暗記しちゃいましょう。まずはそれぞれの袋に入っているボールの情報を取得し、choicesに格納していきましょう。一番最初のやつはいらないので捨てちゃえ!情報の格納が終わったらいよいよ、DFSの時間です。このDFSの処理もテンプレに則って書いていきました。DFSに渡した情報としては最初の数字の1と最初の袋の数字0です(インデックス番号で処理をしているから0)。再起関数の中では、もし袋の番号が最後の袋の番号と一緒なら、積がxと同じかどうかの判定をして、違うのならば、再起関数を回しまくっています。(引数には袋を1つ後のにするのでnumの数字を1つ足して、for文を回した時点での選ばれたボールの積を渡しています。)再起関数1回ごとにたくさんのchoices[num]の要素分の分岐が起こっています。最後にcntの値を戻り値として返してあげて出力してあげればACできます。 文章力もっとあげな、意味わからんわ...
使ったテンプレート
234 Happy New Year!
k = int(input())
k = int(format(k,'b'))
print(2*k)
この問題は一見複雑そうに見えますが、穴を見つけられ場一瞬です。フツーの2進数は0
235 The Kth Time Query
from collections import defaultdict
n,q = map(int, input().split())
alist = list(map(int, input().split()))
helper = defaultdict(list)
for idx, a in enumerate(alist):
helper[a].append(idx+1)
for i in range(q):
x,k = map(int, input().split())
if len(helper[x]) < k:
print(-1)
else:
print(helper[x][k-1])
この問題はdefaultdictを使うと簡単に解くことができます。defaultdictとは連想配列のキーをその場で作れる的なやつです、最後にそれ用のリンク載せときます。まずはdifaultdictの力を持ったhelperを作成して、enumerateを使ってそれぞれの値とindex番号を同時に取得し、キーがaの連想配列に、aの値が出てくる場所を追加していきます(1を追加すのはidxはインデックス番号だから) そして、実際に答えを出力していく処理に移っていきます。まず、k番目の要素が存在するのかをif文でチェックします。もし存在しなかったら、-1を出力します。存在するならば位置を出力します(kに-1をしているのは要素を探すためにkの値をインデックス番号に変換しないといけないから、ややこしいね♪誰だよ考えたやつ)
236 Route Map
n,m = map(int, input().split())
S = input().split()
T = set(input().split())
for s in S:
if s in T:
print("Yes")
else:
print("No")
正直この問題は知識問題的な感じですね（もし知らなくても、今学べばなんの問題もありません）下に参照した方の記事によると〜in〜で特定の要素がset型に入っているかどうかを調べるときの速度はリスト型に比べて約100倍ほど早いらしいので、小技として覚えておきましょう！多分君を助けてくれるぞ
For detail)
237 kasaka
s = input()
la = len(s) - len(s.lstrip('a'))
ra = len(s) - len(s.rstrip('a'))
if la > ra:
print("No")
exit()
else:
s = "a"*(ra-la)+s
if s == s[::-1]:
print("Yes")
else:
print("No")
まずこの問題で重要なのは、先端と末端のaの数です。問題のルール上、aは前にしかつけることができないので、先頭のaの数が末端のaの数より大きい時点で、回文が成立することはあり得ません。先頭と末端についているaの数はlstripとrstripを使うことで簡単に調べあげられます。lstripではsの先頭からaを全て抜いた後のsを作ってくれて、rstripは逆に末端からaを全て抜いた後のsを作ってくれます。なので、全体の文字数から、それぞれの位置からaを抜いた後の文字数を引くだけで求めることができます。あとはaを足りないだけ先頭に足してあげて、回文になっているかどうかを判定してあげるだけでACできます。
238 digitnum
mod = 998244353
n = int(input())
leng = len(str(n))
ans = 0
for i in range(1,leng+1):
tmp = min(n,10**i-1)-(10**(i-1)-1)
ans += (tmp*(tmp+1)//2)
ans %= mod
print(ans)
しばらく考えても分からなかったので、unidayoさんの力を貸していただきました。自分用に解説すると、まずこの問題は桁数メインで管理をしていきます。for文の中では、nの数がiの桁数の最大値より大きいかどうかをで処理が別れます。もし大きい場合には、i桁の最大値からi-1桁最大値の間の全ての数字が総和計算マシンに送られ、小さい場合にはnからi-1桁の最大値の間の全ての値が総和まるに送られます。下では総和の公式(x*(x+1)//2)を使って計算し、ansに追加して、for文の最後に数字を小さくして、処理を早めるためにmodの値で余りを出して動かしてます。(これは余りの性質みたいなのがあるからうまく動くらしい)
unidayoさんの解説記事
239 Knight Fork
import math
x1,y1,x2,y2 = map(int, input().split())
if abs(x2-x1) > 10 or abs(y2-y1) > 10:
print("No")
exit()
for i in range(min(x1,x2)-3,max(x1,x2)+4):
for j in range(min(y1,y2)-3,max(y1,y2)+4):
if (math.sqrt(((x1-i)**2)+((y1-j)**2)) == math.sqrt(5)) and (math.sqrt(((x2-i)**2)+((y2-j)**2)) == math.sqrt(5)):
print("Yes")
exit()
print("No")
この問題はどちらの点からもユークリッド距離が√5になるというのがポイントです、距離が√5なのでxとyそれぞれの絶対値の差が離れすぎてるポイントたちが入力与えられたら、スグにnoを出力して処理を終わらせてオッケーです(10にしているのは、ギリギリの値がよく分からないから安パイな数字をぶち込んだだけ) 実際のfor文の処理では√5なので、それぞれのxとyから離れすぎている点が答えになることはないので、大体こんぐらいかなって範囲のxとyの範囲から±3の範囲でfor文を回しています。そして、実際にユークリッド距離を求めるための公式を当てはめて、√5になるのならyesを出力して処理を終わらせます。
240 Jumping Takahashi
n,x = map(int, input().split())
dp = [[False]*(x+1) for _ in range(n+1)]
dp[0][0] = True
for i in range(n):
a,b = map(int, input().split())
for j in range(x+1):
if dp[i][j]:
if j + a <= x:
dp[i+1][j+a] = True
if j + b <= x:
dp[i+1][j+b] = True
if dp[n][x]:
print("Yes")
else:
print("No")
この問題はめちゃくちゃ良いDPの練習問題です。普通に全探索を回すとO(2**n)上かかってしまいます(多分...) しかしDPを使うことによって高速で解き切ることができます。まず、DPとは一言で表すと、それまでの最適解から現在の最適解を導き出すみたいなイメージです。この問題では、iまでの間に辿り着ける、場所を全てbooleanを使って、記録しておき、次のループに生かしていくみたいな感じです。 それではコードの解説に移っていきましょう。 まず、dpのそれまでの情報を格納するためのDPリストを作っていきます。そして初期値として、dp[0][0]をTrueにしてあげます(Trueの値が入っていないとDP自体が始められないから。) 正直この書き方はDPのテンプレ的な感じです。そして、for文を回し始めます。for文の中では最初に選択肢の入力を受けとり、その後に前回のループまでで辿り着ける場所のデータが欲しいので、x+1でもう一度for文を回し始めます。そして、もし前回までのループで辿り着ける場所が見つかったのなら、その情報を現在の辿り着ける場所リストに追加していきます(indexエラーを防ぐために、xの場所を超えちゃわないかを判定してから情報を加える。) ここでi+1にしているのはベースが何も入っていない状態から始まるので、index番号の1番目が一番最初の選択肢でたどりつける場所リストになっているから(多分伝わってないよな...) そして、同じ処理を繰り返していき、最後のリストには最終的にたどりつける場所が格納されています。なので、最後のリストのxの位置がTrueになっているのなら辿り着けるということです!