競プロ解説
久々に ABC でやったらいけないミスした……。
問題リンク
https://atcoder.jp/contests/abc198/tasks/abc198_d
問題概要
覆面算 $S_1+S_2=S_3$ を解いてください。
制約
- $1\le |S_i|\le 10$
- $S_i$ は英小文字のみからなる。
解説記事を書くのはかなりお久しぶりになってしまいました。
問題リンク
https://atcoder.jp/contests/arc114/tasks/arc114_c
問題概要
$1$ 以上 $M$ 以下の整数からなる長さ $N$ の数列 $A$ に対して、$f(A)$ を以下のように定義します。
長さ $N$ の数列 $X$ があり、初め全ての要素は $0$ である。$f(A)$ を、次の操作を繰り返して $X$ を $A$ に等しくするために必要な最小の操作回数とする。
- $1\le l\le r\le N$ と $1\le v\le M$ を指定する。$1\le i\le r$ に対して $X_i$ を $\max(X_i,\ v)$ で置き換える。
全ての $A$ に対する $f(A)$ の和を $\bmod 998244353$ で求めてください。
制約
- $1\le N,\ M\le 5000$
ABC 反省文シリーズ。
問題リンク
https://atcoder.jp/contests/abc190/tasks/abc190_d
問題概要
整数からなる公差 $1$ の等差数列のうち、総和が $N$ であるものはいくつあるでしょうか？
制約
- $1\le N \le 10^{12}$
ABC 反省文シリーズです。
問題リンク
https://atcoder.jp/contests/abc189/tasks/abc189_f
問題概要
マス $0$ から始めてマス $N$ を目指す双六があります。高橋くんは $1$ から $M$ までの目が出るルーレットを回して進みます。また、この双六のマス $A_i\ (i=1,\ 2,\ ,\dots,\ K)$ は振り出しに戻るマスで、そこに止まるとマス $0$ に戻されます。
高橋くんがマス $N$ より先に着きゴールするまでにルーレットを回す回数の期待値を求めてください。到達不可能ならその旨を報告してください。
制約
- $1\le N,\ M\le 10^5$
- $0\le K\le 10$
- $0\lt A_1\lt \dots\lt A_K\lt N$
解きました。公式解説や有志の解説ブログを見ても自分と同じような考え方の人がいなかったので解説ブログを書きます。
問題リンク
https://atcoder.jp/contests/arc071/tasks/arc071_d
問題概要
$1,\ 2,\ 3,\ \dots,\ n$ からなる無限長の数列 $a_1,\ a_2,\ \dots$ のうち、次の条件を満たすものの個数を答えてください。
- $a_n=a_{n+1}=\dots$
- すべての $a_i$ について、$a_{i+1}=a_{i+2}=\dots=a_{i+a_i}$
制約
- $1\le n\le 10^6$
灘中入試コンテストday2-E でした。実装が重かったです。無限に実装をバグらせてしまい、自らの実装力の無さを嘆きました。
問題リンク
https://yukicoder.me/problems/no/1354
問題概要
$x,\ y$ 座標ともに $0,\ 1,\ \dots,\ N$ からなる竹藪があります。サンボ君はこの竹藪の $M$ 個のチェックポイントを全て通りつつ $(0,\ 0)$ から $(N,\ N)$ へと移動したいです。移動は右または下にのみ可能です。
ただし、竹藪には $L$ 体のトラが棲んでいます。トラのいるマスには最大でも $K$ 回までしか通れません。
条件を満たすような移動のしかたは何通りあるでしょうか。$998244353$ で割った余りを求めてください。
制約
- $1\le N\le 2\times 10^{5}$
- $0\le M\le \min(10^5,\ N-1)$
- $0\le L\le \min(100,\ (N+1)^2-2)$
- $0\le K\le 10^5$
- チェックポイントの座標について、$0\lt xc_i,\ yc_i\lt N$
- $xc_i\lt xc_{i+1},\ yc_i\lt yc_{i+1}$
- トラの座標について、$0\le xt_i,\ yt_i\le N,\ (xt_i,\ yt_i)\ne (0,\ 0),\ (N,\ N)$
- トラの座標は Distinct
過去にやった問題が役に立ったので嬉しかったです。
問題リンク
https://atcoder.jp/contests/arc111/tasks/arc111_b
問題概要
$N$ 枚のカードがあり、各カードの両面には $a_i,\ b_i$ の色がついています。どちらかを表にするとき、表側の色の種類数の最大値はいくつになるでしょうか。
制約
- $1\le N\le 2\times 10^5$
- $1\le a_i,\ b_i\le 4\times 10^5$
Educational Codeforces 初めての Unrated 参加でした。見事に出来ないといけない問題が解けずに Educate されました。
問題リンク
https://codeforces.com/contest/1473/problem/E
問題概要
$n$ 頂点 $m$ 辺の重み付き有向連結グラフが与えられます。ここで、二頂点間のパスの距離を、通る辺の重みの総和に、重みの最小値を足して、最大値を引いたものと定義します。頂点 $1$ から各頂点への距離の最小値を求めてください。
制約
- $2\le n\le 2\times 10^5$
- $1\le m\le 2\times 10^5$
- $1\le w_i\le 10^9$
最近の ABC は調子良かったんですが、今回はありとあらゆる失敗を詰め込んだ破滅回でした。もう反省だらけです。
【追記】嘘解法であることが発覚したので、その部分を訂正して正当な解法にしました。
問題リンク
https://atcoder.jp/contests/abc188/tasks/abc188_f
問題概要
整数 $X$ を整数 $Y$ にしたいです。以下の操作を何回でもできます。
- 整数を $1$ 増やす。
- 整数を $1$ 減らす。
- 整数を $2$ 倍する。
最小で何回操作する必要があるでしょうか。
制約
$1\le X,\ Y\le 10^{18}$
…C 問題は問題文が読みにくくて少しつらかったけど、D 問題も E 問題も面白くて楽しいセットでした。本番ギリギリ E が間に合わなくてつらかった……。
問題リンク
https://codeforces.com/contest/1469/problem/E
問題概要
ふたつの文字列 $a,\ b$ について、同じ位置に同じ文字が存在するような位置がひとつでもある場合、a bit similar といいます。
0 および 1 からなる文字列 $s$ について、その長さ $k$ の部分文字列全てと a bit similar である長さ $k$ の文字列のうち、辞書順最小のものを求めてください。そのような文字列が存在しない場合はその旨を報告してください。
制約
$1\le k\le n\le 10^6$
…