- AtCoder Beginner Contest 081 C - Not so Diverse
- AtCoder Beginner Contest 150 C - Count Order
- AtCoder Beginner Contest 293 C - Make Takahashi Happy
AtCoder ProblemsのRecommendation(Moderate)を解く
AtCoder Beginner Contest 081 C - Not so Diverse
diff = 430
リンク：C - Not so Diverse (atcoder.jp)
概要：個のボールに何種類かの数字が書かれています。
種類以内にするために数字の書き換えが必要なボールの最小数を出力してね
度数分布作って少ない順に処理すれば良さそう。
Pythonでは度数分布を作る便利な関数があるので使いましょう。
Counterによって（1が3個）というように数字をキーとして配列が作られます。
今回は何の数字かは関係ないので数だけを取り出して適当に配列としています。
また少ない順に並べ替えて配列として、余分な数字の種類
のぶんを数え上げて答えとして出力しました。
from collections import Counter
N, K = map(int, input().split())
A = list(map(int, input().split()))
num = Counter(A)
B = []
for key in num:
B.append(num[key])
C = sorted(B)
D = len(B) - K
if D > 0:
ans = sum(C[:D])
else:
ans = 0
print(ans) 提出リンク：提出 #50296999 - AtCoder Beginner Contest 081
AtCoder Beginner Contest 150 C - Count Order
diff = 422
リンク：C - Count Order (atcoder.jp)
概要：～
の数字を重複なく並べ替えた数列が2つあります。考えられる数列すべてを辞書順に並べた時の順位の差を出力してね
問題文にもある通り～
の順列は
通りありますが制約が
なので全探索しても間に合いそうです。
でも探索するたって元の順列どうやって全部つくろう・・・なんとか計算で辞書順ひねくりだせんかな・・・
いやわからん（解説）
ということで"permitations"という関数を使うといいそうです。
配列に入っているものを重複なく並べ替えて作った順列を辞書順にリストアップしてくれます。
permutationsはタプル形式で順列を保有しているので検索したい順列もタプルに型を合わせる必要があります。
順列を作るのに(たぶん)、順列
と
の位置を探すのにすれぞれ
なので計算量としては
だと思います。
#ABC150 C - Count Order
from itertools import permutations
N = int(input())
P = tuple(map(int, input().split()))
Q = tuple(map(int, input().split()))
num = [i for i in range(1, N+1)]
a = list(permutations(num))
ans = abs(a.index(P) - a.index(Q))
print(ans)
提出リンク：提出 #50300842 - AtCoder Beginner Contest 150
AtCoder Beginner Contest 293 C - Make Takahashi Happy
diff = 432
リンク：C - Make Takahashi Happy (atcoder.jp)
概要：二次元盤面で互いに異なる数字のみを踏んでゴールにたどり着く組み合わせ数を出力してね
左上スタートで右か下のみに進んで右下を目指すということでとり得る経路は最短距離のみになります。
ゴールの可否や条件満たす経路のうち1つだけ出力する問題ならBFSで一瞬なんですが組み合わせの数ということは何とかして全ての組み合わせを試行してゴールできたものの数を数え上げる必要があります。
（1時間後）
DFSで経路記録したり上書きしたりすれば何とかなりそうだな！
ということでキューに座標を追加していき、取り出すタイミングで現在地の数字を経路配列に記録していきます。
現在地がスタートから何マス目かは
で計算しています。
今回は必ず最短経路でゴールにたどり着くため、スタートゴール含めて踏むマスの数のサイズは
になります。
現在地がゴールの座標の場合は経路に同じ数字が無いか判定を入れています。
#ABC293 C - Make Takahashi Happy
from collections import deque
H, W = map(int, input().split())
A = []
for x in range(H):
a = list(map(int, input().split()))
A.append(a)
#print(A)
q = deque([[0, 0]])
pre = [-1]*(H+W-1)
count = 0
while q:
cnt = q.popleft()
x, y = cnt
pre[x+y] = A[x][y]
if x == H-1 and y == W-1:
if len(pre) == len(set(pre)):
count += 1
# print(pre)
else:
nx = [x+1, y]
ny = [x, y+1]
if x+1 < H:
q.appendleft(nx)
if y+1 < W:
q.appendleft(ny)
# print(q)
# print(pre)
print(count) 提出リンク：提出 #50300193 - AtCoder Beginner Contest 293
今回は1勝2敗ということで同じような難易度帯でも解ける解けないがまだ激しいですね・・・
