方法1 回答例 方法2 方法1コンテスト中に考えた方法です． $B_{00} = (i-1)\times 7 + j$を満たす$(i, j)$が存在し， $1 \leq i \leq i + N - 1 \leq 10^{100}$，$1 \leq j \leq j + M - 1 \leq 7$を満たし， $B_{kl} = B_{00} + 7k + l$を満たす ならYesで…

「値」が何種類かというのがポイント．ここを「$n$の種類」と読み違えると泥沼にはまる（「$X=1$の場合，無限に存在するじゃん？？？」，となる）．上のせいで，難易度が水色なのだと予想．．．考え方例を見ればわかるように，$n$に関して単調増加なので，二…

考え方 回答例1：「Pinv[頂点]=コマ」を使う 回答例2：「P[コマ]=頂点」を使う 考え方コマを頂点に置く方法は$9! = 362,880$と少ないので，dictで「並び順：かかった手数」を管理しながら全探索（BFS）できます．コマのない頂点には，仮想的なコマ9を置くこ…

全探索して，3点が一直線上になければ+1すれば良い．一直線上にあることは，$x$が小さい順に点を$P_{1}, P_{2}, P_{3}$として，条件【「点$P_{1}$と点$P_{2}$の傾き」＝「点$P_{1}$と点$P_{3}$の傾き」】を満たすかどうかで判定できる．分数だと分母がゼロの…

「長方形が3つ」という点と「辺の長さが整数」という点がポイントです． 考え方条件を満たす長方形が3つ存在したとする．長方形が3つなので，ある一つの長方形は，辺を$x$軸 or $y$軸方向に目一杯延長しても他の2つの長方形と干渉しない．そのような長方形を…

【関連問題】 ABC216D - Pair of Balls - 競プロはじめました 考え方「数字を頂点」，「順序関係を辺」と考えればグラフの問題になる．求められているものは，トポロジカルソートしたもので，辞書順で最小のものであるとわかる． （トポロジカルソートについ…

考え方：二分探索バグ取りに苦労した．もっと見通しの良い方法がありそう． 求める位置が左からx以上となるならok，そうでないならngとして二分探索を考える．あとはcheck(x)関数をつくればよい．左からx進むのにかかる時間tlと，トータルの時間を計算するこ…

むずい．考えの流れを整理しておく． 【類題】 C - ABC conjecture 考え方$N\leq 10^{10}$だから，$N$になる数を調べることはできない．よって，$a^{b}$で表せる数を重複なくカウントして，$N$から引く方針． 一番単純な方法として，「$a,b$の全探索＋setの…

考え方入力例1の3番目をもとに考察するとよい（具体例大事！）．$R \leq B$とする（例は既にそうなっている）．以下の手順で全てGに変えることができる． R G B 1 2 4 3 1 3 2 3 2 1 5 1 0 7 0つまり，すべてGにしたければ，RとBを同じ個数に調整できればよ…

考え方：公式解説の方法公式解説の方法（Editorial - Exawizards Programming Contest 2021（AtCoder Beginner Contest 222））を考える． まず，各辺を何回通るか求める．頂点$A_{i}$と頂点$A_{i+1}$を結ぶ辺を通る回数を$C_{i}$とする．すると，\begin{ali…

考え方dp[i][j]=「$c_{i} = j$となる方法の数」がわかれば，\begin{aligned} &\mathrm{dp}[i+1][j] \\ & = \begin{cases} \, \displaystyle \sum_{k\leq j} \mathrm{dp}[i][k] & (A_{i + 1} \leq j \leq B_{i+1}) \\ \, 0 & (\text{otherwise}) \end{cases} …

B問題なのに手間取ったのでメモ． 全探索せずに，切り上げ・切り下げで考えて沼ってしまった．．．考え方1：全探索B問題としては，全探索するのが素直．個数$N$のパターンは高々$10^{6}$通りなので，$A \leq 1000W/N \leq B$となるもののうち，最小・最大を…

考え方根を「深さ$0$」とすると，深さ$d$にある頂点の個数は$2^{d}$個．深さ$0$から深さ$d$までの頂点の総数は\begin{aligned} \sum_{i = 0}^{d} 2^{i} = 2^{d + 1} - 1 \end{aligned}であるから，問題文の設定では深さは$N - 1$である．「①一番浅い頂点$v$…

各$A_{i}$について，$i 考え方 $i \begin{aligned} \mathrm{ans} &= \sum_{\{(i,j) \mid i &=\sum_{j} 2^{j} \textcolor{red}{\sum_{ \substack{i \end{aligned}を計算すればよい．以下，$j$でループさせることにして，赤字の部分をどう実現するか考える． …

1. bit 全探索考え方分割後の数字は，大きい位ほど大きい数字のほうがよい．よって，どの数字を選ぶかが決まれば，並び方は決まる．数字の選び方を全探索することを考えると，9桁しかないのでbit 全探索できる．回答例 N = list(map(int, list(input()))) N.…

考え方差分だけを処理していく問題．ログインとログアウトを後で区別できるようにして「ごちゃまぜソート」をするとラク（これもよくあるパターン）．日付を1日単位で見るとTLE．「現れる日付の差」を使って処理する．現れる日付を前から見ていき，今ログイ…