torus711 のアレ

主に競技プログラミングの問題について書きます.PC 以外だと数式が表示されないかもしれないです

AtCoder

AtCoder Beginner Contest 345, C : One Time Swap

問題文 https://atcoder.jp/contests/abc345/tasks/abc345_c 問題概要 文字列 $S$ が与えられる.$S$ に対し,$S$ の添字 $i, j$ ($1 \leq i 制約 $1 \leq |S| \leq 10^6$ $S_i \in \mathcal C$ ここで,$\mathcal C$ はすべての英小文字からなる集合とする.

AtCoder Beginner Contest 345, D : Tiling

問題文 https://atcoder.jp/contests/abc345/tasks/abc345_d 問題概要 $1 \times 1$ のセルからなる $h \times w$ のグリッド状の盤面と $n$ 枚のタイルがあり,タイル $i$ は $A_i \times B_i$ の長方形状である. 各タイルについて,グリッドに沿い,かつ…

AtCoder Beginner Contest 344, D : String Bags

問題文 https://atcoder.jp/contests/abc344/tasks/abc344_d 問題概要 文字列の列が $n$ 個与えられる.$i$ ($1 \leq i \leq n$) 番目の列は $S_i = \langle S_{ i, 1 }, S_{ i, 2 }, \dots, S_{ i, A_i } \rangle$ である. ここで,次の処理を行う. 変数 …

AtCoder Beginner Contest 344, E : Insert or Erase

問題文 https://atcoder.jp/contests/abc344/tasks/abc344_e 問題概要 相異なる $n$ 項からなる数列 $A = \langle A_1, A_2, \dots, A_n \rangle$ がある. 次の 2 種からなるクエリを $q$ 個,順に処理せよ. $( 1, x, y )$ : $A$ に含まれる $x$ の直後に …

AtCoder Beginner Contest 342, E : Last Train

問題文 https://atcoder.jp/contests/abc342/tasks/abc342_e 問題概要 $1$ から $n$ で番号付けられた $n$ 個の駅があり,$m $ 種類の路線が運行されている.各路線は 6 個の整数 $l, d, k, c, a, b$ *1で説明され,その意味は, 駅 $u$ から駅 $v$ へ向かう…

AtCoder Beginner Contest 342, D : Square Pair

問題文 https://atcoder.jp/contests/abc342/tasks/abc342_d 問題概要 $n$ 項からなる非負自然数の列 $\langle A_1, A_2, \dots, A_n \rangle$ が与えられる.以下の条件を満たす順序対 $( i, j )$ はいくつあるか? $1 \leq i $A_i A_j$ は平方数 制約 $2 \…

AtCoder Beginner Contest 341, D : Only one of two

問題文 https://atcoder.jp/contests/abc341/tasks/abc341_d 問題概要 正整数 $n, m, k$ ($n \neq m $) が与えられる.正整数であって,$n, m $ のどちらか一方でのみ割り切れる数の内,小さい方から $k$ 番目のものを求めよ. 制約 $1 \leq n, m \leq 10^8$…

AtCoder Beginner Contest 341, E : Alternating String

問題文 https://atcoder.jp/contests/abc341/tasks/abc341_e 問題概要 $0$ と $1$ からなる $n$ 要素の列 $S = S_1, S_2, \dots S_n$ ($S_i \in { 0, 1 }$) が与えられる.クエリが $q$ 個与えられるので,順に処理せよ.クエリは以下の 2 種類からなる: $(…

AtCoder Beginner Contest 341, F : Breakdown

問題文 https://atcoder.jp/contests/abc341/tasks/abc341_f 問題概要 $n$ 頂点 $m $ 辺からなるグラフ $G = ( V, E )$ がある.ここで,$\forall u, ( u, u ) \not \in E$ かつ $( u, v ) \in E \Leftrightarrow ( v, u ) \in E$ である(i.e., $G$ は単純…

AtCoder Beginner Contest 340, F : S = 1

問題文 https://atcoder.jp/contests/abc340/tasks/abc340_f 問題概要 整数 $x, y$ ($x \neq 0$ or $y \neq 0$) が与えられる. 以下の条件を満たす整数 $a, b$ を出力せよ. $-10^{ 18 } \leq a, b \leq 10^{ 18 }$ 二次元平面 $\mathbb R^2$ 上の点 $( 0, …

AtCoder Beginner Contest 340, E : Mancala 2

問題文 https://atcoder.jp/contests/abc340/tasks/abc340_e 問題概要 $0$ から $n - 1$ で番号付けられた $n$ 個の箱があり,最初,箱 $i$ には $A_i$ 個のボールが入っている. $i = 1, 2, \dots, m $ に対し順に以下の手続きを実行する. 変数 $c$ を用意…

AtCoder Beginner Contest 340, D : Super Takahashi Bros.

問題文 https://atcoder.jp/contests/abc340/tasks/abc340_d 問題概要 $1$ から $n$ の合計 $n$ ステージからなるゲームをプレイしている.最初,ステージ $1$ のみを遊ぶことができる. プレイ可能なステージ $i = 1, 2, \dots, n - 1$ では,以下の内 1 つ…

AtCoder Beginner Contest 339, C : Perfect Bus

問題文 https://atcoder.jp/contests/abc339/tasks/abc339_c 問題概要 あるバスがあり,ある時点で非負の人数が乗っていた.その時点からのバスの乗降記録が与えられる.乗降記録は数列 $A = \langle A_1, A_2, \dots, A_n \rangle$ の形で与えられ,$A_i$ …

AtCoder Beginner Contest 339, D : Synchronized Players

問題文 https://atcoder.jp/contests/abc339/tasks/abc339_d 問題概要 $n \times n$ のグリッド状の盤面があり,各セルは空きマスまたは障害物である.また,2 つの駒が盤面の(相異なる)セルに置かれている. 駒たちに対し,以下の操作を適用することがで…

AtCoder Beginner Contest 339, E : Smooth Subsequence

問題文 https://atcoder.jp/contests/abc339/tasks/abc339_e 問題概要 $n$ 項の数列 $A = \langle A_1, A_2, \dots, A_n \rangle$ が与えられる. $A$ の(連続するとは限らない)部分列であって,隣接する 2 項の差の絶対値が $d$ 以下なものの長さの最大値…

AtCoder Beginner Contest 338, F : Negative Traveling Salesman

問題文 https://atcoder.jp/contests/abc338/tasks/abc338_f 問題概要 $n$ 頂点 $m $ 辺からなる重み付き単純有向グラフ $G = ( V = \{ 1, 2, \dots, n \}, E )$ がある.$i$ 番目の辺は $( U_i, V_i ) \in E$ であり,その重みは $w( ( U_i, V_i ) )$ であ…

AtCoder Beginner Contest 338, E : Chords

問題文 https://atcoder.jp/contests/abc338/tasks/abc338_e 問題概要 円周上に $2n$ 個の点が並んでいて,(適当な位置から)時計回りに $1, 2, \dots, 2 n$ で番号付けられている.円周上には $n$ 本の「弦」*1があり,$i$ 番目の弦は点 $A_i$ と $B_i$ を…

AtCoder Beginner Contest 338, D : Island Tour

問題文 https://atcoder.jp/contests/abc338/tasks/abc338_d 問題概要 $0$ から $n - 1$ で番号付けられた $n$ 個の島と $n$ 本の橋があり,$i$ 番の橋は島 $i$ と島 $i + 1 \bmod n$ を双方向に結んでいる. 島 $X_1$ から開始して島 $X_2, X_3, \dots, X_m…

AtCoder Beginner Contest 338, C : Leftover Recipes

問題文 https://atcoder.jp/contests/abc338/tasks/abc338_c 問題概要 料理の材料が $n$ 種類あり,$i$ 番目の材料は $Q_i$ グラムある. これから $2$ 種類の料理を作ることができる.料理 A は,$1$ 人前を作るのに材料 $i$ ($1 \leq i \leq n$) を $A_i$ …

AtCoder Beginner Contest 337, E : Bad Juice

問題文 https://atcoder.jp/contests/abc337/tasks/abc337_e 問題概要 本問はインタラクティブ問題である. $1$ から $n$ で番号付けられた $n$ 本のジュースがあるが,その内ちょうど $1$ 本は腐っており,それを飲むと◯ぬ.腐ったジュースを特定するために…

AtCoder Beginner Contest 337, D : Cheating Gomoku Narabe

問題文 https://atcoder.jp/contests/abc337/tasks/abc337_d 問題概要 文字からなる $h \times w$ のグリッドがあり,セル $( i, j )$ に書かれた文字は $S_{ i, j }$ で与えられ,$S_{ i, j } \in \{\text{$`$o', $`$x', $`$.'} \}$ である. このグリッド…

AtCoder Beginner Contest 337, B : Extended ABC

問題文 https://atcoder.jp/contests/abc337/tasks/abc337_b 問題概要 文字列 $S$ が与えられる.$S$ は以下で説明する $A, B, C$ で $A + B + C$ の形で表せるか?*1 $0$ 個以上の文字 $`\text{A'}$ からなる文字列を $A$ ,$0$ 個以上の文字 $`\text{B'}$ …

AtCoder Beginner Contest 336, F : Rotation Puzzle

問題文 https://atcoder.jp/contests/abc336/tasks/abc336_f 問題概要 $h \times w$ のグリッドがあり,グリッドの各セルには $1$ 以上 $h w$ 以下の整数がそれぞれひとつずつ書き込まれている. このグリッドに対し,以下の操作を $0$ 回以上適用することを…

AtCoder Beginner Contest 336, E : Digit Sum Divisible

問題文 https://atcoder.jp/contests/abc336/tasks/abc336_e 問題概要 正整数 $n$ が与えられる.$n$ 以下の正整数で,その桁和が自身を割り切るものはいくつあるか? 制約 $1 \leq n \leq 10^{ 14 }$

AtCoder Beginner Contest 336, D : Pyramid

問題文 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_…

AtCoder Beginner Contest 335, D : Loong and Takahashi

問題文 https://atcoder.jp/contests/abc335/tasks/abc335_d 問題概要 奇数であるような正整数 $n$ が与えられる.以下の条件を満たす $n \times n$ グリッドを構成せよ. グリッドの各セルには文字列が書かれる. セル $\left( \frac { n + 1 } 2, \frac { …

AtCoder Beginner Contest 335, E : Non-Decreasing Colorful Path

問題文 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…

AtCoder Beginner Contest 335, F : Hop Sugoroku

問題文 https://atcoder.jp/contests/abc335/tasks/abc335_f 問題概要 左から右に一列に並んだ $n$ 個のマスがあり,$1, 2, \dots, n$ で番号付けられている.また,長さ $n$ の数列 $A = \langle A_1, A_2, \dots, A_n \rangle$ がある. 初期状態では,マ…

AtCoder Beginner Contest 324 F : Beautiful Path

問題文 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$ から…

AtCoder Beginner Contest 324, E : Joint Two Strings

問題文 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$