以下の転置行列を求める問題を考える． zipを使う 素直に書く 例 zipを使うzipを使うとすごくきれいに書ける． H, W = map(int, input().split()) A = [list(map(int, input().split())) for _ in range(H)] B = list(zip(*A)) for b in B: print(*b) 【参考…

解法1 考え方 回答例 解法2 解法3 考え方 回答例 解法1考え方逆から考えれば，両端にしか文字を追加せずに済むので，dequeをつかえば良い． Editorial - AtCoder Beginner Contest 237回答例collections --- コンテナデータ型 — Python 3.10.0b2 ドキュメン…

考え方 平均値 中央値 二分探索＋DP 回答例 考え方公式解説がわかりやすい．二分探索＋DP． Editorial - AtCoder Beginner Contest 236平均値\begin{aligned} & \frac{1}{n} \sum_{i=1}^{n} x_{i} \geq K \\ & \Leftrightarrow \sum_{i=1}^{n} (x_{i} -K) \g…

考え方 回答例 考え方最大で$2N = 16$人．ペアの組み方は\begin{aligned} 15!! &= 15\times 13 \times \cdots \times 3 \times 1 \\ &=2,027,025 \end{aligned}となる（例えば以下のコード）．よって，全探索できる． ans = 1 x = 15 while x > 0: ans *= x …

最小全域木（MST）については以下： 最小全域木（MST - Minimum Spanning Tree） - 競プロはじめましたUnionFindについては以下： UnionFind木 - 競プロはじめました 考え方 回答例 考え方クラスカル法を使う．以下のようにすれば良い．一度のクラスカル法で…

用語 アルゴリズム 例題 用語用語を整理しておきます（蟻本p. 99-）： 全域木：無向グラフの部分グラフで，任意の2頂点が連結である木． 最小全域木：辺のコストの和が最小の全域木． アルゴリズム プリム法：木$T$に，木$T$の頂点と木$T$に含まれない頂点を…

考え方 回答例 考え方 「重みなし」グラフの最短経路を求める問題になる→BFS 桁が減る操作はないので，10 ** 6を超えたら打ち切ることができる 回答例 from collections import deque a, N = map(int, input().split()) q = deque() q.append(1) dist = [-1]…

考え方 回答例 考え方こうやって遷移できるんですね．なるほどぉ〜．長さ$j$の文字列を作るとき，新しい文字を$k$個使うとすると， 新しい文字（$i+1$番目の文字）を入れる場所を，$j$個の候補から$k$個選べば， あとは，$i$種類の文字で長さ$j-k$の文字列を…

優先度付きキュー 考え方 回答例 参考 BIT 考え方 回答例 優先度付きキュー考え方$K$要素のリストを管理し， 「(リストの中で一番小さい値) そうでないなら，リストを変更しない とすれば，このリストの最小値が各ステップで求めたい値となる．これは，最初…

考え方 回答例 考え方$K$を2進数表記して，1を2に置き換えたものが答え．回答例 K = int(input()) tmp = [] while K > 0: if K % 2: tmp.append('2') else: tmp.append('0') K //= 2 print(''.join(reversed(tmp))) bin(x)を使うと，整数を先頭に "0b" が付…

考え方 回答例 参考 考え方連結成分ごとの答えをかけ合わせれば良い．「どの頂点についても、その頂点から他の頂点に向かう辺がちょうど 1 本ずつ存在する」とき，頂点と辺は1セットと考えることができ (頂点数) = (辺数) という条件を満たす．また，「(頂点…

考え方 回答例 考え方$K$回の操作はシミュレーションしなくてはならない．現在地を$(x,y)$で表し，$(x_{2}, y_{2})$を「ゴール」と呼ぶ．各ステップに対して，状態としては $x$座標も$y$座標も「ゴール」と関係ない：$x\neq x_{2}, y\neq y_{2}$ $x$座標のみ…