ARC196 B - Torus Loop

問題概要 問題へのリンク 1辺の長さが1の正方形である2種類のタイルがある. 種類A: 種類B: 高さ $H$,幅 $W$ のグリッドに,このタイルが敷き詰められている. (A, B からなる長さ $W$ の文字列が $H$ 個与えられる) 各タイルは回転可能. グリッドをトーラスとしてみたときに,線分が行き止まりにならずつながるように配置する方法の数を mod 998244353 で求めよ. 制約 $2 \leq H$,$2 \leq W$,$HW \leq 10^6$ 解 公式解説へのリンク 略解.click to open 正しく敷き詰められているとする. $p[i, j]$ を,セル $(i, j)$ の左側の縦の線分の中点を線が通るかどうか (true/false) $q[i, j]$ を,セル $(i, j)$ の上側の横の線分の中点を線が通るかどうか (true/false) とする. トーラスになるように同一視する. $i$を固定し,横一列に $p[i, j]$ ($j = 0, 1, \ldots, W)$ を考えると, セル $(i, j)$ が A なら,$p[i, j] = \neg p[i, j + 1]$ セル $(i, j)$ が B なら,$p[i, j] = p[i, j + 1]$ だから,A の横の個数は偶数でなければならない.縦も同様....

2025-04-24 · yamate11

ARC196 A - Adjacent Delete

問題概要 問題へのリンク 整数 $N$ と長さ $N$ の整数列 $A$ が与えられる.最初スコアは $0$ である. 次の操作を,$A$ の長さが $1$ 以下になるまで繰り返す: $A$の (その時点で) 隣接する2項を選び,どちらも削除する. 2項の差の絶対値がスコアに加算される. 得られるスコアの最大値を求めよ. 制約 $2 \leq N \leq 3\times 10^5$,$1 \leq A_i \leq 10^9$ 解 公式解説へのリンク 略解.click to open $N$ が偶数の時 大きい方の半分をプラスに,小さい方の半分をマイナスにした和がスコアの上界. この上界が達成できる. $N$ が奇数の時 最後に残る1個を決めると,その左右それぞれで,上記偶数の時と同じ議論になる. 最後に残る1個を,左から順に全部調べる.

2025-04-21 · yamate11

ABC397 F - Variety Split Hard

問題概要 問題へのリンク 整数 $N$ と,長さ $N$ の整数列 $A = (A_0, \ldots, A_{N - 1})$ が与えられる. $A$ を 2箇所で区切って,3個の空でない連続する部分列に分解するとき, おのおのの部分列に含まれる数の種類数の和の最大値を求めよ. 制約 $3 \leq N \leq 3\times10^5$,$1 \leq A_i \leq N$ 解 公式解説 略解.click to open $L_i := (A_0, \ldots, A_{i - 1})$ に含まれる種類数 $R_i := (A_i, \ldots, A_{N - 1})$ に含まれる種類数 $dp[i][j] := (A_0, \ldots, A_{j - 1})$ と $(A_j, \ldots, A_{i - 1})$ に含まれる種類数の和 ($j \in [0, i)$) とする.求める値は $\max_i (R_i + \max_j(dp[i][j]))$....

2025-04-20 · yamate11

Codeforces Round 1018 Div1+2 E. Wonderful Teddy Bears

問題概要 問題へのリンク 長さ$N$の文字列 $S$ が与えられる.$S$ に現れる文字は B と P だけ. 次の操作によって,B を左に P を右に寄せ $S$ を BB...BPP...P という形にする. 操作の最小回数を求めよ. $S$ の長さ3の部分列をとり,その部分の B を左に,P を右に寄せる. つまり,1回の操作は,以下のいずれか: (あ) PPB $\to$ BPP (い) PBP $\to$ BPP (う) PBB $\to$ BBP (え) BPB $\to$ BBP 制約 $3 \leq N \leq 2\times10^5$ 解 tutorialへのリンク 略解.click to open 奇数番のみ,偶数番のみの列を考えると, 操作は,次のいずれかになっている: (ア) 奇数列の隣接入替,偶数列の隣接入替 (あ, う) (イ) 奇数列と偶数列の B, P の入替 (い,え) 全体としてみたときの転倒数を $r$ とする.(ア)では転倒数が2減り, (イ) では転倒数が1減る. 最終形を考えると,奇数列,偶数列の B, P の個数は決まっている. だから,(イ) の最低必要な回数 $x$ が決まる. 「最初に (イ) を $x$ 回行って,あとの操作はすべて (ア)」が実現できれば, それ以上回数は減らせない....

2025-04-20 · yamate11

Codeforces Round1011 (Div.2) E. Serval and Modulo

問題概要 問題へのリンク 整数 $N \geq 1$ と,整数の multiset $ A, B$ が与えられる.$A$, $B$ の要素数は $N$ である. 整数 $K$ で,multiset $ \{ a \bmod K \mid a \in A \}$ が $B$ と等しくなるものがあるか判定し, あれば1つ与えよ. 制約 $1 \leq N \leq 10^4$,$0 \leq a_i, b_i \leq 10^6$ 解 tutorialへのリンク 略解.click to open そういう $K$ があれば $K$ は,$d := \sum_i a_i - \sum_i b_i$ の約数になる. ($10^{10}$ 以下の数の約数の個数の最大値は $2304$ 個である.)

2025-04-20 · yamate11

積の和典型

ABC399-F Range Power Sum が, 積の和典型だとのことなので,関連記事へのリンクなど. リンク 積の和典型 - ei1333の日記 ABC399-F 問題概要 問題へのリンク $A = (A_1, \dots, A_N)$ が与えられる.次を mod 998244353 で求めよ: $$ \sum_{1 \leq l \leq r \leq N}\left( \sum_{l \leq i \leq r} A_i \right)^K $$ 制約: $N \leq 2\times 10^5$, $K \leq 10$. 解法 (累積和で2項展開しても解けるが,それは置いといて…) 以下, 公式解説 より. 次のように言い換えられる. ボールが $A_i$ 個入った箱が一列に並んでいる. 箱の間に,2個の仕切りを入れる. 2つの仕切りの間にあるボールに,$1, 2, \ldots, K$ と書かれたラベルを1枚ずつ貼る 仕切りの入れ方とラベルの貼り方をセットで考えて,この方法の数が,求める答になる. DP で求める. dp[i][j][k] = (箱 i まで見て,仕切りを j 個入れていて,ラベルを k 枚貼るような方法の数)

2025-03-30 · yamate11

畳み込み・ゼータ変換・メビウス変換

畳み込みやゼータ変換やメビウス変換に関するメモ

2025-03-10 · yamate11

WolframAlpha への入力

WolframAlpha への入力方法のメモです

2025-02-25 · yamate11

std::mapへの挿入と更新

std::map に「挿入か更新をする」ときの idiom をすぐに忘れてしまうのでメモしておく. std::map<S, T> mp; と宣言されているとする. 1. 無条件で,s の値を t にする 通常は次で良い: mp[s] = t; もともと s が有ったか無かったのかも知りたい場合や,s へのイタレータも欲しい場合には,次のようにする: auto [it, b] = mp.insert_or_assign(s, t); b には,挿入が行われたかどうかが設定されるので,b が false なら,もともとキー s が存在していたことがわかる.it は s へのイタレータ. 2. キー s が無ければ,値を t にする. 次のように書くと,s の探索が2回走ってしまう. if (mp.find(s) == mp.end()) mp[s] = t; 次のようにすれば 1回ですむ. mp.emplace(s, t); もともと s が有ったか無かったのかも知りたい場合や,s へのイタレータも欲しい場合には,次のようにする: auto [it, b] = mp.emplace(s, t); b には,挿入が行われたかどうかが設定されるので,b が false なら,もともとキー s が存在していたことがわかる.it は s へのイタレータ....

2025-02-14&nbsp;·&nbsp;yamate11

比較関数

set, multiset, priority_queue などの比較関数の指定方法

2024-11-04&nbsp;·&nbsp;yamate11

誤りの記録

デバッグに失敗した,ないし,長時間かかった間違いの記録 ABC212E Safety Journey 問題へのリンク 2023/07/05 あさかつ 無向グラフが,完全グラフからM本の辺を除いたものとして与えられている. 除く辺は $(u, v)$ の形で与えられている. dp[i][j] = (i 回の繰返し後,頂点 j に到達できる方法の数) という DP で, 全体から 除いた辺の分を引く. $(u, v)$ と $(v, u)$ の両方を引かなければならないところ, $(u, v)$ しか引かなかった. ABC279F BOX 2023/07/05 あさかつ タイプミス 正: if (rx == -1 and ry == -1) { 誤: if (rx == -1 and ry == 1) { ARC164B 2023/07/09 コンテスト 誤読. 正: 木の好きな頂点を選んで出発できる 誤: 木の根から出発する ABC222E Red and Blue Tree 2023/08/02 あさかつ...

2024-09-26&nbsp;·&nbsp;2023-07-05T09:03:15+09:00 (初版)&nbsp;·&nbsp;yamate11

intervalSet ライブラリ

階段関数を表現するライブラリ intervalSet の説明です.

2024-09-15&nbsp;·&nbsp;yamate11

ダブリングライブラリ

ダブリングを行うライブラリを書きました.ソースはこちら . できること その1 $f : [0, N) \to [0, N)$ が与えられた時, $r \in [0, R]$ と $i \in [0, N)$ に対して $f^{r}(i)$ を 計算する. 典型的には: $N$ は $10^5$ くらい,$R$ は $10^{18}$ くらい,または $N$ も $R$ も $10^5$ くらいだが,何回も (たとえば $10^5$回くらい) 計算する その2 上の $f$ の他に,モノイド $(M, \oplus)$ と $m: [0, N) \to M$ が与えられて, $r, i$ に対して $\bigoplus_{k = 0}^{r - 1} m(f^{k}(i))$ を計算する. 使用法 その1 DoublingFRel オブジェクト d を作る. 上記 $R$,$N$,$f$ を doubling_from_func に与える. ll R = 100000, N = 100000; auto f = [&](ll i) -> ll { return (i * i) % N; }; auto d = doubling_from_func(R, N, f); 関数 $f$ の代わりにベクトルなどのコンテナを与えたいときには,doubling_from_container を用いる. ll R = 100000, N = 100000; vector<ll> vec(N); REP(i, 0, N) vec[i] = ....

2024-09-08&nbsp;·&nbsp;2022-12-10 (初版)&nbsp;·&nbsp;yamate11

LIS - 最長増加部分列

復元方法も含めた最長増加部分列に関するまとめ

2024-09-01&nbsp;·&nbsp;yamate11

集合・多重集合のハッシュ

集合のハッシュに関する記事です

2024-08-26&nbsp;·&nbsp;2022-02-13T11:32:14+09:00 (初版)&nbsp;·&nbsp;yamate11