ABC345 D - Tiling
問題
- $H \times W$のマス目と、$N$枚のタイルが与えられるよ
- $i$枚目のタイルは、$ A_i \times B_i $の長方形だよ
- タイルを使って、マス目をピッタリ埋める事ができる？
- 重なったり、空白があったりしちゃだめだよ
- タイルは回転させてもいいよ
成約
- $1 \leq N \leq 7$
- $1 \leq H,W \leq 10$
- $1 \leq A_i, B_i \leq 10$
思考
- 制約が超絶小さい…ので、ゴリ押し力技の全探索
- 一旦計算量を考えてみる
- どのタイルを使う？→bit全探索で$O(2^{N})$
- 使う予定のタイルの、回転どうする？→bit全探索で$O(2^{N})$
- 使う予定のタイルの、順番どうする？→並べ替えで$O(N!)$
- 決めたタイルの使い方、手順を、左上から順に機械的に埋めていく
- もし全タイル丁度埋めきれたら、OK！→判定に$O(H*W)$
- 一旦計算量を考えてみる
- いくら$N,H,W$が小さいとはいえ…これは…
- $2^{N} \times 2^{N} \times N! \times H \times W$
- $=8,257,536,000$…これは、流石に、無理…
- ところがどっこい通るんですねぇ…
- タイルを何枚使うかを、小分けにして考えてみる
- 1枚使うパターン：7通り
- $7\times2^{1}\times 1! \times H \times W = 14HW$
- 2枚使うパターン：7C2=21通り
- $21 \times 2^{2} \times 2! \times H \times W = 168HW$$
- 3枚使うパターン：7C3=35通り
- $35 \times 2^{3}\times 3! \times H \times W = 1,680HW$$
- 4枚使うパターン：7C4=35通り
- $35 \times 2^{4} \times 4! \times H \times W = 13,440HW$
- 5枚使うパターン：7C5=21通り
- $21 \times 2^{5} \times 5! \times H \times W = 80,640HW$
- 6枚使うパターン：7C6=7通り
- $7 \times 2^{6} \times 6! \times H \times W = 322,560HW$
- 7枚使うパターン：7C6=1通り
- $1 \times 2^{7} \times 7! \times H \times W = 645,120HW$
- 1枚使うパターン：7通り
- $H,W$は固定なので、上記パターンに分類される
- 一番重い、7枚使うパターンを、7回回すっていう感覚で、
- $7 \times 645,120 \times10\times 10 = 451,584,000$
- $8,257,536,000$から比べると一気に小さくなった
- 一番重い、7枚使うパターンを、7回回すっていう感覚で、
- 計算量の見積もり、とても、難しい…
コード
import itertools N, H, W = map(int, input().split()) tiles = [] for i in range(N): A, B = map(int, input().split()) tiles.append([A, B]) master = [[1] * W for _ in range(H)] def calc(tiles): base = [[0] * W for _ in range(H)] cur = 0 for i in range(H): for j in range(W): if len(tiles) == cur: break if base[i][j] != 0: continue tile_x, tile_y = tiles[cur] if i + tile_x > H or j + tile_y > W: return False for x in range(i, i + tile_x): for y in range(j, j + tile_y): if base[x][y] != 0: return False base[x][y] = 1 cur += 1 if base == master: return True return False for saiyou in range(1, 1 << N): saiyou_tiles = [] area_sum = 0 for i in range(N): if saiyou >> i & 1: saiyou_tiles.append(tiles[i]) area_sum += tiles[i][0] * tiles[i][1] tile_cnt = len(saiyou_tiles) for omoteura in range(1 << tile_cnt): omoteura_tiles = [] for i in range(tile_cnt): if omoteura >> i & 1: omoteura_tiles.append(saiyou_tiles[i]) else: omoteura_tiles.append([saiyou_tiles[i][1], saiyou_tiles[i][0]]) for junban in itertools.permutations(omoteura_tiles): if calc(junban): print('Yes') exit() print('No')
ABC345 C - One Time Swap
問題
- 文字列$S$が与えられるよ
- 次の操作を1回行った後の文字列として、有り得るものはいくつある？
- Sのうち2つの文字を選んで、入れ替える
成約
- $2 \leq |S| \leq 10^{6}$
思考
- $O(N^{2})$は通らない…
- 片方を全探索して、もう片方がサクサクッと求められたら嬉しいね
- 全探索の典型
- 手順：
- 事前準備として、全アルファベットがいくつある？を記録(Counter)
- 先頭から順に一文字ずつ確認(全探索)
- Counterから、その1文字分の集計を消す
- Counterに記録されているのは、「今見ている文字」から右にある文字ごとの数！
- a~zまでの26文字、順番に数を数えていく
- 「今見ている文字」と同じ文字の個数に関して取り扱い注意！
- Counterから、その1文字分の集計を消す
- そもそも英小文字＝26種類しかないため、文字を2つどう選んでも、$26\times26$しかない
- aとbを入れ替えるパターンはいくつ？
- aとcを入れ替えるパターンはいくつ？
- …
- bとcを入れ替えるパターンはいくつ？
- こっちで集計したほうが明らかに速いですね！
コード(解1)
from string import ascii_lowercase from collections import Counter S = input() c = Counter(S) ans = 0 same = 0 for from_c in S: c[from_c] -= 1 for to_c in ascii_lowercase: if from_c != to_c: ans += c[to_c] elif c[to_c] > 0: same += 1 if same: ans += 1 print(ans)
コード(解2)
from string import ascii_lowercase from collections import Counter S = input() c = Counter(S) ans = 0 same = 0 for a in ascii_lowercase: for b in ascii_lowercase: if a == b: if c[a] > 1: same += 1 else: ans += c[a] * c[b] ans //= 2 if same: ans += 1 print(ans)
ABC345 B - Integer Division Returns
問題
- 整数$X$が与えられるよ
- $ \lceil \frac{x}{10} \rceil $を出力してね
成約
- $-10^{18} \leq X \leq 10^{18}$
思考
math.ceilで行けるでしょｗｗｗ- 誤差で通らず無事致命傷
- ちゃんと切り上げ除算、関数で準備しておきませう、というTips
コード
X = int(input()) def div_ceil(a, b): return (a + b - 1) // b print(div_ceil(X, 10))
ABC345 A - Leftrightarrow
問題
- "<"、"="、">"で作られた文字列$S$が与えられるよ
- $S$が、双方向矢印型かどうか判定してね
成約
- $3 \leq |S| \leq 100$
思考
- 最初が"<"、最後が">"、それ以外が"="かどうかを判定すれば良いね
コード
S = input() if S[0] == "<" and S[-1] == ">" and S.count("=") == len(S)-2: print('Yes') else: print('No')
ABC344 E - Insert or Erase
問題
- 長さ$N$の数列$A$が与えられるよ
- Q個のクエリを順番に処理してね
- クエリ1：$A$の中の要素$x$の直後に$y$を挿入してね
- クエリ2：$A$の中にある要素$x$を削除してね
- 全部のクエリを捌いた後の$A$はどうなってる？
成約
- $1 \leq N \leq 2 \times 10^{5}$
- $1 \leq Q \leq 2 \times 10^{5}$
- $A$の中の要素は常にユニーク
- クエリが与えられた時、$A$の中に$x$は絶対存在するよ
思考
- 電車の類題(ABC225D)を思い出す
- 特定の要素の、「前の数字は何？」と、「後ろの数字は何？」を管理・更新していくと良さそう
- クエリ1の捌き方：
- 「$x$の後ろの数字」をメモ(tmp)
- 「$y$の前の数字」を$x$に更新(新規作成)
- 「$y$の後ろの数字」を「$x$の後ろだった数字(tmp)」に更新（新規作成）
- 「$x$の後ろの数字」を$y$に更新
- 「$x$の後ろだった数字(tmp)の、前の数字」を、$y$に更新
- クエリ2の捌き方：
- 「$x$の後ろの数字」を、「$x$の後ろの後ろの数字」に更新
- 「$x$の前の前の数字」を、$x$に更新
- クエリ1の捌き方：
- 本番は$N=1$のケースでめっちゃしばかれました(5ペナ)
- tips: 番兵として、先頭と末尾の車両を固定で置いておくと幸せになれました
コード
N = int(input()) A_L = [0] + list(map(int, input().split())) + [-1] link_d = dict() for i in range(1, N + 1): link_d[A_L[i]] = [A_L[i - 1], A_L[i + 1]] link_d[0] = [None, A_L[1]] link_d[-1] = [A_L[N], None] Q = int(input()) for _ in range(Q): query = list(map(int, input().split())) if query[0] == 1: prev_num, add_num = query[1:] next_num = link_d[prev_num][1] link_d[prev_num][1] = add_num link_d[add_num] = [prev_num, next_num] link_d[next_num][0] = add_num else: del_num = query[1] prev_num, next_num = link_d[del_num] link_d[prev_num][1] = next_num link_d[next_num][0] = prev_num ans_L = [] now_num = 0 while True: ans_L.append(now_num) if link_d[now_num][1] == -1: break now_num = link_d[now_num][1] print(*ans_L[1:])
ABC344 D - String Bags
問題
- 最初に文字列$T$と、空文字列$S$を持ってるよ
- 文字列がいくつか入った袋が$N$個あるよ
- 袋$i$には、$A_i$個の文字列が入ってるよ
- 以下の手順を$i=1,2,...,N$について繰り返すよ
- 1円を払って、袋$i$から好きな文字列を1つ選んで、文字列$S$の末尾に連結する
- 何もしない
- 最終的に文字列$S$と文字列$T$が一致する？
- 一致するなら、必要な最小の金額を教えてね！
成約
- $1 \leq |T| \leq 100$
- $1 \leq N \leq 100$
- $1 \leq A_{i} \leq 100$
- $1 \leq S_{i,j} \leq 10$
思考
- 雰囲気から、DP！
- 問題文に「DはDPのD」って書いてる
- 初期値：「空文字列」を作るための最小コスト＝0
- 遷移：
- 「今作れてる文字列」に、新しい袋から文字列を1つ取り出して、引っ付けてみる
- もしTの先頭と一致しているなら、とりあえず採用！
- コストの最小値を見ていく
- 丁寧にindex（何文字目まで作成できた！）で見ていったほうが良いんだろうなぁ、と思ってはいる…
- が、
T.startswith()で接頭語だけに絞れば、割と余裕で通ったので良かった - 文字列の長さがどれも短かったから…？
- 正直、Tが$10^{6}$みたいな長さしてたらTLE頂いてた可能性は十分有り
- そのうちindexでちゃんと書き換える :TODO
- が、
コード
T = input() N = int(input()) words = [] for i in range(N): tmp = input().split() words.append(tmp[1:]) now_s = set() now_s.add("") cost_d = dict() cost_d[""] = 0 for i in range(N): next_s = set() for now_word in now_s: next_s.add(now_word) for add_word in words[i]: tmp = now_word + add_word if T.startswith(tmp): next_s.add(tmp) if tmp in cost_d.keys(): cost_d[tmp] = min(cost_d[tmp], cost_d[now_word] + 1) else: cost_d[tmp] = cost_d[now_word] + 1 now_s = next_s print(cost_d[T] if T in cost_d.keys() else -1)
ABC344 C - A+B+C
問題
- 3個の数列$A,B,C$が与えられるよ
- 長さ$Q$の数列$X$も与えられるよ
- 各$i=1,...,Q$について、以下の問題に答えてね
- $A,B,C$から要素を1つずつ選んで、和を$X_{i}$にすることができる？
成約
- $1 \leq |A|,|B|,|C| \leq 100$
- $0 \leq A_i, B_i ,C_i \leq 10^{8}$
- $1 \leq Q \leq 2 \times 10^{5}$
- $0 \leq X_{i} \leq 3\times 10^{8}$
思考
- $A,B,C$はそんなに長くないですね
- (Aの要素1つ)+(Bの要素1つ)+(Cの要素1つ)のパターンは、$100^{3}$個しか無いね！
- 前準備として、先に要素を1つずつ選んだ和として作れるものを全部列挙しておくと、$X$の質問にすぐ答えられるね！
コード
N = int(input()) A_L = list(map(int, input().split())) M = int(input()) B_L = list(map(int, input().split())) L = int(input()) C_L = list(map(int, input().split())) Q = int(input()) X_L = list(map(int, input().split())) sum_s = set() for a in A_L: for b in B_L: for c in C_L: sum_s.add(a + b + c) for x in X_L: if x in sum_s: print("Yes") else: print("No")
