考え方 回答例 考え方$N$以下の整数を，平方数で割れるだけ割ったもので分類する．同じクラスに属する数どおしを掛け合わせたときにだけ，積が平方数になる．回答例 N = int(input()) cnt = [0] * (N + 1) for i in range(1, N + 1): j = 2 while j * j <= i…

考え方 回答例 参考 考え方 「dp[i][j] = $i$番目まで選んだときに和が$j$となる場合の数」としたくなる 不等式の両辺が動くと困るので，片方を固定したい．和については↑のようにdpで考えたいので，maxを固定したい． $\{(A_{i}, B_{i})\}_{i}$を$A_{i}$に…

考え方 回答例 考え方以下と同じ考えで解ける． ABC246F - typewriter - 競プロはじめました文字列を26bitで管理し，$N$個のうちどの文字列を選ぶかをbit全探索する．すべての場合について，26文字が何回出てくるかカウントする．最後に，$K$回出てくる個数…

考え方 回答例 考え方左から見ていくと，コの字の辺を追加していく形になっている（初期状態のみ特殊）．各ステップで3辺のうちどれを切るかをきめるとdpで解ける．dp[i][j][k]を， 左から$i$番目まで決まっていて， $j$本の辺を取り除かれていて， 上と下が…

考え方（包除原理） 回答例 考え方（包除原理）dpで解いたが，組み合わせ＋包除原理でも解けそうと思いつつ実装できなかったのでメモ． Editorial - UNIQUE VISION Programming Contest 2022（AtCoder Beginner Contest 248）$\sum_{i=1}^{N} A_{i} = x$の場…

考え方 回答例 考え方$K=1$ならInfinityなので，その他の場合を考える．2点を決めれば傾きが決まる．このとき，何点通るかをカウントする．「$x$個の点が一直線上に乗っているとき，この直線はxx回カウントされる」という考え方ができる． ※これに気付かずに…

考え方 回答例 考え方区間$[1, N]$を，区間$[i, j]$で $X \leq A_{k} \leq Y \:(\forall k \in [i, j])$ を満たすものに分割して考える．あとはこの区間ごとに個数を数えれば良い．区間の左端を$L = i$に固定して，$X, Y$の両方が出てくるまで右端を一つずつ…

考え方 回答例 考え方 包除原理 Editorial - AtCoder Beginner Contest 246$k$段目のキーにどの文字が含まれるかを26bitで表す．キーの組み合わせをbit全探索する（1 〜1 ）．各キーの組み合わせにおいて，選んだ全てのキーに共通して含まれる文字種の数を求…

考え方 回答例 考え方部分列の中含まれる「(1の数) - (0の数)」のパターンが何通りあるか，という問題．累積和のパターンが何通りあるかを考えれば良さそうだが，1の数が変化しても，0の数が変化しても累積和が変化してほしい．そこで，0を-1で置き換えて累…

考え方 回答例 (Python) 考え方条件を満たす文字列$X$が，初めから何文字目で$S$と異なるかで場合分けして数え上げる．$S$と$i$文字目で異なる回文$X (\leq S)$としてあり得るものの個数は，次の積で求められる． $i-1$文字目までは$S$と一致するので1通り $…

何度もバグらせてしまったので，どうやればバグりにくいかを考える． 考え方 回答例 考え方$N$以下で$k$桁のものの個数$\mathrm{cnt}[k]$がわかれば，\begin{aligned} \sum_{k} \frac{\mathrm{cnt}[k] (\mathrm{cnt}[k] + 1)}{2} \end{aligned}が答えになる…