問題文 https://atcoder.jp/contests/abc336/tasks/abc336_d 問題概要 正整数 $k$ について，数列 $\langle 1, 2, \dots, k - 1, k, k -1, \dots, 2, 1 \rangle$ を「サイズ $k$ のピラミッド数列」と呼ぶことにする． 長さ $n$ の数列 $A = \langle A_1, A_…
問題文 https://atcoder.jp/contests/abc335/tasks/abc335_d 問題概要 奇数であるような正整数 $n$ が与えられる．以下の条件を満たす $n \times n$ グリッドを構成せよ． グリッドの各セルには文字列が書かれる． セル $\left( \frac { n + 1 } 2, \frac { …
問題文 https://atcoder.jp/contests/abc335/tasks/abc335_e 問題概要 $n$ 頂点 $m $ 辺からなる連結な単純無向グラフ $G = ( V, E )$ があり，$i$ 番目の辺は頂点 $V_i$ と $U_i$ を双方向に結んでいる．また，整数列 $A = \langle A_1, A_2, \dots, A_n \r…
問題文 https://atcoder.jp/contests/abc335/tasks/abc335_f 問題概要 左から右に一列に並んだ $n$ 個のマスがあり，$1, 2, \dots, n$ で番号付けられている．また，長さ $n$ の数列 $A = \langle A_1, A_2, \dots, A_n \rangle$ がある． 初期状態では，マ…
はじめに 本記事は競プロ Advent Calendar 2023，第 4 日目の記事として書かれました． 本記事では，わたしが普段競技プログラミングに取り組む際に使っているテンプレ (C++) の紹介をします．使用言語が Python や Rust や Haskell の方，すみません． 動機…
問題文 https://atcoder.jp/contests/abc324/tasks/abc324_f 問題概要 $N$ 頂点 $M $ 辺の有向グラフ $G = ( V, E )$ があり，$i$ 番目 ($0 \leq i *1は頂点 $u_i$ から $v_i$ を結び，その「美しさ」は $b_i$ で「コスト」は $c_i $である． 頂点 $0$ から…
問題文 https://atcoder.jp/contests/abc324/tasks/abc324_e 問題概要 英小文字からなる $N$ 個の文字列 $\{ S_i \}_{ 0 \leq i $0 \leq i, j 制約 $N \in \mathbb Z^+$ $1 \leq N \leq 5 \times 10^5$ $\sum |S_i| \leq 5 \times 10^5$
問題文 https://atcoder.jp/contests/abc299/tasks/abc299_d 問題概要 長さ $N$ の秘密の列 $S = S_1 S_2 \dots S_N$ があり，$S_1 = 0$ かつ $S_N = 1$ かつ $S_i \in \{ 0, 1 \}$ である． $S_i$ を尋ねる操作を 20 回まで行える．$S_i \neq S_{ i + 1 }$ …
導入 最近（どれぐらい？）の AtCoder の問題で，「有理数を $\bmod$ で扱え」といった問題がしばしば出題されます*1．わたしは数学が苦手なのでこの手の問題は最初から諦めていたのですが，そろそろそういうことも言っていられなくなってきた気がするので，…
問題文 https://atcoder.jp/contests/abc292/tasks/abc292_e 問題概要 単純有向グラフ $G = ( V, E )$ が与えられる． 以下の操作を考える． グラフ $\hat G = ( V, \hat E \leftarrow E )$ を用意する 以下の操作を可能な限り適用する 相異なる頂点 $u, v, …
問題文 https://atcoder.jp/contests/abc267/tasks/abc267_e 問題概要 $N$ 頂点 $M $ 辺の単純無向グラフ $G$ が与えられ，頂点 $i$ には整数 $A_i$ が書かれている． ここで，一つの頂点を削除する以下の操作を $N$ 回繰り返すことでグラフを空にすることを…
問題文 https://atcoder.jp/contests/abc266/tasks/abc266_e 問題概要 $1$ 以上 $6$ 以下の整数の目が等確率で出るダイスを使ったゲームを考える．ゲームは最大 $N$ ラウンドからなる．各ラウンドではサイコロを一回振り，その出目を $X$ とする．その後行え…
問題文 https://atcoder.jp/contests/abc260/tasks/abc260_d 問題概要 $1$ 以上 $N$ 以下の整数が重複なく書かれたカードが $N$ 枚あり，山札として積まれている．上から $i$ 番目のカードに書かれているのは $P_i$ である． ここで，次の操作を $N$ 回繰り…
問題文 https://atcoder.jp/contests/abc258/tasks/abc258_e 問題概要 $N$ 種類の荷物があり，種類 $i$ の重さは $W_i$ である． 今，荷物が無限に運ばれてきて，$i$ 番目 (0-indexed) の荷物の種類は $i \bmod N$ である．これらの荷物を次のように処理する…
問題文 https://atcoder.jp/contests/abc258/tasks/abc258_d 問題概要 $N$ ステージからなるゲームがある．$i$ 番目のステージは，初回クリアには $A_i + B_i$ 分の時間がかかり，2 回目以降のクリアには $B_i$ 分かかる．$i$ ( $0 ステージを合計 $X$ 回ク…
問題文 https://atcoder.jp/contests/abc255/tasks/abc255_d 問題概要 項数 $N$ の数列 $\{ A_i \}_{ i \in [ 0, N ) }$ が与えられる．この数列を以下のように変更することを「操作」と呼ぶ． $0 \leq i $A_i$ を $A_i + 1$ または $A_i - 1$ のいずれかで…
問題文 https://atcoder.jp/contests/abc245/tasks/abc245_f 問題概要 単純有向グラフ $G = ( V, E )$ が与えられる． 頂点 $v \in V$ であって，$v$ を始点として $G$ 上で無限に（辺に沿った）移動を繰り返すことができるものの個数を求めよ． 制約 $1 \le…
問題文 https://atcoder.jp/contests/abc187/tasks/abc187_f 問題概要 $N$ 頂点 $M $ 辺の単純無向グラフ $G = ( V, E )$ がある．このグラフをクリークで被覆するときの最小のクリーク数を求めよ*1． 制約 $1 \leq N \leq 18$ $0 \leq M \leq \frac{ N ( N …
問題文 https://atcoder.jp/contests/abc186/tasks/abc186_d 問題概要 $N$ 項からなる正整数列 $\{ A_i \}_{ i \in [ 0, N ) }$ が与えられる．$$\sum_{ i = 1 }^{ N - 1 } \sum_{ j = i + 1 }^N | A_i - A_j |$$ を求めよ． 制約 $2 \leq N \leq 2 \times 1…
問題文 https://atcoder.jp/contests/abc186/tasks/abc186_e 問題概要 正整数 $N, S, K$ が与えられる．$S + xK \equiv 0 \pmod N$ となる最小の $x$ を求めよ． $T$ ケース処理せよ． 制約 $1 \leq T \leq 100$ $2 \leq N \leq 10^9$ $1 \leq S \leq N$ $1 …
問題文 https://atcoder.jp/contests/abc185/tasks/abc185_e 問題概要 長さ $N$ の正整数の列 $\{ A_i \}_{ i \in [ 0, N ) }$ と長さ $M $ の正整数の列 $\{ B_i \}_{ i \in [ 0, M ) }$ が与えられる．これらからいくつかの要素を取り除き（，残った要素を…
問題文 https://atcoder.jp/contests/abc185/tasks/abc185_d 問題概要 $N$ 個のマスが一列に並んでいる．これらの $N$ 個のマスははじめ，白または青で塗られている．青色のマスは $M $ 個あり，それらの座標は数列 $A_i$ で与えられる（位置 $J$ について，…
問題文 https://atcoder.jp/contests/abc185/tasks/abc185_f 問題概要 長さ $N$ の正整数の列 $A$ について，以下の 2 種類のクエリが $Q$ 個飛んでくる．順に処理せよ． クエリ 1 : $A_{ X_i }$ を $A_{ X_i } \oplus Y_i$ で置き換える クエリ 2 : $\oplus…
問題文 https://atcoder.jp/contests/abc185/tasks/abc185_c 問題概要 長さ $L$ （$L$ は整数）の棒を $11$ 箇所で切断して $12$ 本の棒（各棒の長さは整数）を作ることを考える．切断の仕方は何通りあるか？ 制約 $12 \leq L \leq 200$
問題文 https://atcoder.jp/contests/abc185/tasks/abc185_b 問題概要 バッテリー容量が $N$ [mAh] のスマートフォンを携帯し散歩をすることを考える（単位の話は Wikipedia 先輩に 任せる．面倒なので以降無単位量として扱う）． 散歩の詳細は， バッテリー…
はじめに 競技プログラマ的な視点で「列挙問題」について解説してみる，という記事です．競技プログラミング要素はこれだけです（ごめん）．元々脈絡無く用意していた記事ですが，Competitive Programming (1) Advent Calendar 2020 の枠が変に空いていたの…
問題文 https://atcoder.jp/contests/abc184/tasks/abc184_f 問題概要 $N$ 項の正整数列 $\{ A_i \}$ が与えられる．$A$ の部分列であって総和が $T$ 以下となるものの内で，総和が最大のものの総和はいくらか？ 制約 $1 \leq N \leq 40$ $! \leq T, A_i \leq…
問題文 https://atcoder.jp/contests/abc184/tasks/abc184_e 問題概要 $H \times W$ のグリッド状の迷路がある．空きマスは，単なる空きマスと，英小文字が書き込まれたものがある． 移動は 上下左右の隣接するマスへ移動する 現在地に書かれている文字と同…
問題文 https://atcoder.jp/contests/abc184/tasks/abc184_d 問題概要 金貨が $A$ 枚，銀貨が $B$ 枚，銅貨が $C$ 枚ある．いずれかの種類のコインが $100$ 枚になるまで以下の試行を繰り返す． コインを一様ランダムに選ぶ 選ばれたコインと同種のコインを …
問題文 https://atcoder.jp/contests/abc184/tasks/abc184_c 問題概要 グリッド状の無限に広い盤面の位置 $( r_1, c_1 )$ に駒が置かれている．この駒が位置 $( a, b )$ にあるとき，次の条件のいずれかを満たす位置 $( c, d )$ へ一手で動かすことができる…
