2022-02-25

置換の問題で添え字をバグらせない

色々雑です

縦線 $N$ 本から成るあみだくじの上部に $0,1,\dots,N-1$ と番号を割り振って、それらを辿って下部に番号を書き込んだとします。このときの下部の左から $i$ 番目の番号を $q_i$ とします。

このあみだくじが表す置換は $\begin{pmatrix} 0 & 1 & \cdots & N-1 \\ q_0 & q_1 & \cdots & q_{N-1} \\ \end{pmatrix}$ ではありません。
$q_i$ が表しているのは $i$ 番目に来る数であって、 $i$ の行き先ではないからです。（これややこしくないですか？？？）

つまり、このあみだくじが表す置換を $\begin{pmatrix} 0 & 1 & \cdots & N-1 \\ p_0 & p_1 & \cdots & p_{N-1} \\ \end{pmatrix}$ とすると、

$p_i$ は「 $i$ が左から何番目に行くか」
$q_i$ は「左から $i$ 番目に来る数は何か」

を表しています。

これを踏まえると、 $i = 0,1,\dots,N-1$ に対して $p_{q_i} = q_{p_i} = i$ です。

ところで、これは逆元の定義そのものです。

（意味を考えれば明らかではありますが）

これを意識することで見通しが良くなる場合があります。

例えばあるあみだくじがあり、それが表す置換が $\sigma = \begin{pmatrix} 0 & 1 & \cdots & N-1 \\ p_0 & p_1 & \cdots & p_{N-1} \\ \end{pmatrix}$ であるとします。
このあみだくじ最下部の、左から $k$ 番目と $k+1$ 番目の間に横線を引いたあみだくじの置換 $\sigma ' = ( k\ \ k+1 ) \sigma$ を考えます。

先程述べたように逆元を取ると位置を表す置換に変換されるので、逆元に変換→swap→逆元に変換とします。

$\tau$ を「置換を表す配列の左から $k$ 番目と $k+1$ 番目を swap する」ことに対応する互換とすると、

$\sigma ' = \left( \tau \sigma ^{-1} \right) ^{-1} = \sigma \tau$

です。

なので結局、あみだくじに線を引く（左から互換 $( k\ \ k+1 )$ を掛ける）操作は、右から互換 $\tau$ を掛けることと等価であるとわかりました。

ABC013D - 阿弥陀

atcoder.jp

あみだくじが表す置換が求まれば後はダブリングするだけです。

通常であれば置換を表す配列 $p_i$ だけでなく $i$ が $p$ のどこにあるのかも保持しなければなりませんが、先程の事柄を踏まえることで不要となります。

上から $i$ 番目の横線が表す互換を $\sigma _i$ とします。

あみだくじの表す置換は $\sigma_M \sigma_{M-1} \cdots \sigma_1$ ですが、これは $p = (1,2,\dots,N)$ に対し $i = M,M-1,\dots,1$ の順に $p_{A_i+1},p_{A_i}$ を swap するだけで求まります。

#include <bits/stdc++.h>
using namespace std;

vector<int> inv(const vector<int> &p) {
  vector<int> q(p.size());
  for (int i = 0; i < p.size(); i++) q[p[i]] = i;
  return q;
}
vector<int> compose(const vector<int> &q, const vector<int> &p) {
  vector<int> r(p.size());
  for (int i = 0; i < p.size(); i++) r[i] = q[p[i]];
  return r;
}

int main() {
  int n, m, d;
  cin >> n >> m >> d;
  vector<int> p(n);
  iota(p.begin(), p.end(), 0);
  vector<int> a(m);
  for (int i = 0; i < m; i++) cin >> a[i], a[i]--;
  for (int i = m - 1; i >= 0; i--) swap(p[a[i] + 1], p[a[i]]);

  // ダブリング
  vector<int> ans(n);
  iota(ans.begin(), ans.end(), 0);
  for (int k = 0; k < 30; k++) {
    if ((1 << k) & d) ans = compose(p, ans);
    p = compose(p, p);
  }
  for (int i = 0; i < n; i++) cout << ans[i] + 1 << "\n";
}

Submission #29633662 - AtCoder Beginner Contest 013

yukicoder No.326 あみだますたー

yukicoder.me

はじめに $A$ を対称群の逆元 $A'$ に変換しておくと、あみだくじの下部の番号の列を $A'$ にできるか？という問題になり、扱いやすくなります。

#include <bits/stdc++.h>
using namespace std;

vector<int> inv(const vector<int> &p) {
  vector<int> q(p.size());
  for (int i = 0; i < p.size(); i++) q[p[i]] = i;
  return q;
}

int main() {
  int n, k;
  cin >> n >> k;
  vector<int> b(n);
  iota(b.begin(), b.end(), 0);
  for (int i = 0; i < k; i++) {
    int x, y;
    cin >> x >> y;
    x--, y--;
    swap(b[x], b[y]);
  }
  vector<int> a(n);
  for (int i = 0; i < n; i++) cin >> a[i], a[i]--;
  a = inv(a);

  vector<pair<int, int>> ans;
  for (int i = 0; i < n; i++) {
    if (b[i] == a[i]) continue;
    int j;
    for (j = i + 1; j < n; j++) {
      if (a[i] == b[j]) break;
    }
    for (int k = j - 1; k >= i; k--) {
      ans.push_back({k + 1, k + 2});
      swap(b[k], b[k + 1]);
    }
  }
  cout << ans.size() << "\n";
  for (auto p : ans) cout << p.first << " " << p.second << "\n";
}

#741660 (C++17) No.326 あみだますたー - yukicoder

2021-12-08

存在しない beatmania IIDX の当たり待ちについて

この記事は CCS †裏† Advent Calendar 2021 の9日目の記事として作成されました。

adventar.org

前日の記事はくうらんくんのCHUNITHM曲紹介記事です。

note.com

解釈一致。

はじめにこの記事について、タイトルに beatmania IIDX と書いてますが音ゲーあんまり関係ないです。

beatmania IIDX、通称「弐寺」は、音ゲーの祖ともいえる伝統ある音楽ゲームです。7個の鍵盤と1つのスクラッチ（皿）をタイミングよく操作します。

beatmania IIDX には RANDOM、通称「乱」と呼ばれるオプションがあります。これはスクラッチを除いた7つのレーンをランダムに入れ替えるもので、運が良ければ正規譜面より押しやすい配置を引き当てることができます。

f:id:null_mn:20211205195429p:plain — DENIM[A] 正規

f:id:null_mn:20211209142656p:plain — DENIM[A] 乱当たり

（追記：逆割れになってたので画像差し替えました）

さらに最新作の CAST HOUR ではランダム配置を事前に引けるガチャが実装され、よりランダムの価値が高まりました。

そこで今回は、 beatmania IIDX 、及び beatmania IIDX ではない何かのランダム事情を考察していきます。

なお弐寺のランダムオプションは同様に確からしくない可能性を示した調査もありますが、この記事では譜面の排出は同様に確からしい、つまり全てのパターンが等確率で排出されるものとします。

beatmania IIDX の鍵盤が増えた場合

現在の beatmania IIDX の鍵盤は7個ですが、昔の初代 beatmania では5個しかありませんでした。

よって今後もっと鍵盤の多い beatmania が稼働する可能性も0ではありません。~~そんなわけないだろ~~

そこで、 $n$ 個の鍵盤を持つ beatmania でのランダムの分布について考えてみましょう。

f:id:null_mn:20211208022832j:plain — n=21

なお本家に従って $n$ は奇数とします。

ガチ割れ

ガチ割れとは、冒頭の DENIM[A] のように左右に鍵盤が分かれる譜面を指します。

今回は、例えば 3517264 のようにレーンが奇数レーンと偶数レーンに完全に分かれているもののみをガチ割れと定義します。奇数レーンと偶数レーンの順番が逆でもよいです。

ガチ割れのパターン数は奇数レーン $\dfrac{n+1}{2}$ 個と偶数レーン $\dfrac{n-1}{2}$ 個を両端に並べる場合の数であるから、 $2 \left( \dfrac{n+1}{2} \right) ! \left( \dfrac{n-1}{2} \right) !$ 通りです。

よってガチ割れを引く確率は

$\dfrac{ 2 \left( \dfrac{n+1}{2} \right) ! \left( \dfrac{n-1}{2} \right) ! }{n!}$

です。

具体的な $n$ についてのガチ割れ確率は次のようになります。

$n$	ガチ割れ確率（概数）
5	0.2
7	0.05714
9	0.01587
11	0004329
13	0.001166
15	0.0003108

鍵盤の数が増えれば増えるほどガチ割れは引きにくくなることが読み取れます。ポップンでガチ割れを引くのは大変らしい。

なお、上の表からもわかる通り $n \rightarrow \infty$ としたときのガチ割れ確率は0に収束します（スターリングの近似を用いると示せます）。

S 乱当たり

弐寺には、通常の RANDOM オプションの他に S-RANDOM と呼ばれるオプションがあります。

これはレーンを入れ替えるのではなく、1つ1つのノーツごとに独立にどのレーンに降ってくるかを決めるというものです。

勿論これを用いることで押しやすくなる譜面もありますが、一般には縦連が多くなり押しにくくなります。

……ですが、鍵盤の数がめちゃくちゃ多い場合にはどうなるでしょうか？

f:id:null_mn:20211208024122j:plain — デカい

簡単のため譜面に同時押しはないものとし（鍵盤の数がめちゃくちゃ多い場合、遠すぎると無理押しになるため）（？）、ノーツ数は $m$ とします。

縦連が生じる回数の期待値を求めてみましょう。

期待値の線形性から、 $i$ ノーツ目と $i+1$ ノーツ目が同じレーンにある確率を $p$ とすると、求める期待値は $(m-1)p$ です。

同時押しがないという仮定から $p = \dfrac{1}{n}$ であり、縦連の個数の期待値は $\dfrac{m-1}{n}$ であるとわかりました。

通常の弐寺では $n \ll m$ であるため縦連の回数の期待値はかなり大きくなります。

しかし鍵盤の個数がノーツ数より多い弐寺においては、縦連の個数の期待値は1未満になります。鍵盤の個数が増えるとS乱がお得ということですね。

ちなみに $n \sim m-1$ のとき、縦連が1個も存在しない確率は $\left( 1 - \dfrac{1}{n} \right) ^ {m-1} \sim \dfrac{1}{e}$ です。綺麗です。

皿の上に鍵盤が配置されている場合

KONAMIがトチ狂って皿の上に鍵盤がついた新作 beatmania を発表したとします。

この場合皿を回転させることで配置をある程度変更できるので、皿の回転によって一致する譜面は同一視してよいです。

よってあり得る譜面の数は $(n-1)!$ 通りです。（1鍵を固定して考えるとわかりやすい）

ランダム譜面の生成は $(n-1)!$ 通りの譜面の中から一様ランダムに選ぶものとします。

ガチ割れ

1鍵を時計の0時の位置に固定して考えます。

ガチ割れ（のような何か）になるのは左右に奇数レーン偶数レーンが分かれるときで、順番も考慮すると $2 \left( \left( \dfrac{n-1}{2} \right) ! \right) ^2$ 通りです。

よってガチ割れ確率は

$\dfrac{2 \left( \left( \dfrac{n-1}{2} \right) ! \right) ^2}{(n-1)!}$

です。

これは先程の鍵盤が増えた場合で $n$ を偶数とした結果と一致しますね。

これも $n \rightarrow \infty$ とすると確率は0に収束します。

beatmania ∞DX

3021年に登場した無寺(beatmania ∞DXのことです)では、なんと鍵盤の数が無限個になりました。

（STARTボタンは無限遠にあります。悲しいね）

このゲームにおける RANDOM の分布について考えていきましょう。

無限個のものからランダムに選ぶ場合、通常の意味での確率を定義することはできません。そこで確率を確率空間として再定義します。

確率空間は $(\Omega, \mathcal{F}, P)$ の3つ組で、以下を満たすものです。

$(\Omega, \mathcal{F})$ は可測空間*1。つまり、 $\mathcal{F}$ は $\Omega$ 上の完全加法族。
は確率関数で、以下を満たす。
- $P(\Omega) = 1,\ P(\emptyset) = 0$
- どの2つも共通部分を持たない集合列 $A_1, A_2, \dots \in \mathcal{F}$ に対し $P( \bigcup_{i=1}^{\infty} A_i) = \sum_{i=1}^{\infty} P(A_i)$ （可算加法性）

なお、 $\mathcal{F}$ が $\Omega$ 上の完全加法族であることの定義は以下です。

$\mathcal{F} \subseteq 2^{\Omega}$
$\mathcal{F} \neq \emptyset$
$\mathcal{F}$ は補集合及び可算合併について閉じている。

定義だけ見るとゴツいですが、これは事象が有限である通常の確率の自然な拡張です。

通常の弐寺のランダムを例に挙げると、 $\Omega$ は7つのレーンの並べ替え、 $\mathcal{F}$ は並べ替えの集合を全て集めた集合（つまり $2^{\Omega}$ 。例えばガチ割れや2356は $\mathcal{F}$ の要素）、 $P$ は $P(A) = |A| / 7! \ (A \in \mathcal{F})$ で定義される関数です。これが確率空間の公理を満たすことは容易に確かめられます。

（これだけ見ると「 $\mathcal{F}$ 要らなくね？別に $2^{\Omega}$ で良いじゃん」と思うかもしれませんが、 $\Omega$ が非可算無限集合である場合におかしなことが起きます。詳しくは省略）

さて、これを（可算）無限個の鍵盤を持つ弐寺について適用しましょう。

無限個のものの置換全体の集合は $S_1,S_2,\dots$ の合併、つまり $S_{\infty} := \bigcup_{i=1}^{\infty} S_i$ で定義します（無限対称群と呼ばれます）。ここで $S_n$ は $n$ 次対称群（ $n$ 個のものの並べ替え全体のなす群）です。ただし群の構造は忘れて単なる集合とします。 $S_i$ は $S_j \ (i < j)$ の部分集合と見なせることに注意しましょう。

$S_{\infty}$ は可算無限個の有限集合の合併であるので可算集合です。可算集合の冪集合は完全加法族の公理を満たすため、 $(S_{\infty}, 2^{S_{\infty}})$ は可測空間です。

問題は確率関数 $P$ ですが、同様に確からしいという条件があるので、以下を満たすような $P$ を採用したいです。

任意の $\sigma, \sigma ' \in S_{\infty}$ に対し、 $P(\{ \sigma \}) = P(\{ \sigma ' \})$

……結論から言うと、このような $P$ は存在しません。

つまり、無限個の鍵盤を持つ弐寺にランダムを実装することはできません。

以下に理由を述べます。

$S_{\infty}$ は可算集合であるので、 $S_{\infty} = \{ \sigma_1, \sigma_2, \dots \}$ と添え字をつけて外延的に表すことができます。

$A_i := \{ \sigma _{i} \} \ (i = 1,2,\dots)$ としましょう。

確率関数の可算加法性より $P( \bigcup_{i=1}^{\infty} A_i) = \sum_{i=1}^{\infty} P(A_i)$ が成り立ちます。
さらに $\bigcup_{i=1}^{\infty} A_i = S_{\infty}$ であるので、 $P(S_{\infty}) = 1$ と合わせると $\sum_{i=1}^{\infty} P(A_i) = 1$ です。

ここで、無限級数の収束の必要条件から $\lim_{i \rightarrow \infty} P(A_i) = 0$ です。

同様に確からしいという条件から $P(A_1) = P(A_2) = \dots = 0$ となりますが、これは $\sum_{i=1}^{\infty} P(A_i) = 1$ に矛盾します。

よって条件を満たす確率関数 $P$ は存在しません。

（同様の議論を $\Omega = \mathbb{N}$ で行うことで、S乱やR乱が実装できないことも示せます。）

なお、同様に確からしいという条件を外せばランダムを実装することができます。例えば $P(\{ \sigma _i\}) = 2^{-i}$ とすればこれは確率関数の公理を満たします。

冒頭で弐寺のランダムは同様に確からしくないかもしれないという話をしましたが、あれは鍵盤の数を無限に増やすための伏線らしいです。知らんけど。

真・beatmania ∞DX

最後に、鍵盤が非可算無限個ある beatmania を考えます。

鍵盤（？）は $\mathbb{R}$ 上の閉区間 $[ 0,1 ]$ として表されるものとします。~~CHUNITHM か？~~

RANDOM についてはよくわからなかった（レーンの入れ替わりを $[ 0,1 ]$ の自己同型写像としてみれば定義できる？）ので S乱だけを扱います。

可算無限の場合にS乱が定義できなかったので非可算無限なら尚更無理では？と思うかもしれませんが、なんとできます。区間が有界なのがポイント。

先程同様譜面のパターンが有限ではないので確率空間を考えることになりますが、書くのがめんどくなってきたので詳しくは省略します。

（参考：連続一様分布 - Wikipedia）

なお、区間が有界でない場合は定義できません。

確率密度関数は知っている人も多いと思いますが、その背景に測度論があるというのは興味深いですね。

このときS乱をかける前とかけた後でノーツの位置が変わる確率は $1$ です。つまりS乱をかけることで（文字通り）無限のバリエーションを楽しむことができます。夢があるなぁ

ちなみに人間の指は有限本しかありませんが、適当に押した点とノーツが重なる確率は $0$ なので、どう頑張ってもノーツは拾えません。お疲れ様でした。

おわりに

何言ってんだこいつ

参考文献

初心者のための測度論的確率論 ~ Pythonコードを添えて ~ - Qiita

自然数全体から「同様に確からしく」自然数をランダムに選ぶことができないという話 - Sokratesさんの備忘録ないし雑記帳

*1:可測空間！？！？！？（「く」が……）

2021-11-03

std::map の範囲 for 文内で operator[] を使わない

バグったのでメモ

突然ですが次のようなコードがあります。

#include <bits/stdc++.h>
using namespace std;

int main() {
  map<int, int> mp;
  mp[0] = 1, mp[1] = 2;
  int sum = 0;
  for (auto [key, val] : mp) {
    cout << key << " " << val << "\n";
    sum += mp[key + 1];
  }
  cout << sum << "\n";
}

map の全ての key に対して mp[key+1] を求めるコードです。

mp[0+1] = 2, mp[1+1] = 0 なので sum の値は 3 になりそうですが、実際に実行すると次のようになります。

0 1
1 2
2 0
3 0
4 0
5 0
6 0
7 0
8 0
9 0
10 0
11 0
12 0
13 0
14 0
15 0
16 0
17 0
18 0
19 0
20 0
21 0
...（以下ずっと続く）

std::map の operator[] は「キーに対応する値を返し、対応する値がない場合は要素をデフォルトで構築する」という仕様になっています。そのため mp[key+1] と書いただけで {key+1,0} という要素が構築されてしまい、無限ループになります。
std::unordered_map の場合も同様です。（こちらは収納順序が不定である分バグに気付きにくいので注意）

解決策

find関数やcount関数を使いましょう。findの方が要素の探索が一回で済むので速いと思います。

#include <bits/stdc++.h>
using namespace std;

int main() {
  map<int, int> mp;
  mp[0] = 1, mp[1] = 2;
  int sum = 0;
  for (auto [key, val] : mp) {
    cout << key << " " << val << "\n";
    auto itr = mp.find(key + 1);
    if (itr != mp.end()) sum += itr->second;
  }
  cout << sum << "\n";
}

実行結果

0 1
1 2
2

範囲 for 文以外の場面でも無駄に要素が増えると定数倍が大きくなるので、実行時間が気になるときは operator[] を控えましょう。

2021-08-22

区間に等差数列を作用させる遅延セグメントツリー

たまに見る割にまとまった記事がない気がしたので

区間に等差数列を作用させる遅延セグメントツリーとは

長さ $N$ の数列 $A_0, \dots, A_{N-1}$ に対し次のような操作が全て $O(\log N)$ で行えます。

$A_l, A_{l+1}, \dots, A_{r-1}$ をそれぞれ $b,\ a+b,\ 2a+b,\ \dots, \ (r-l)a+b$ で更新する。

$A_l, A_{l+1}, \dots, A_{r-1}$ の最小値/最大値/総和を取得する。

後程述べますが、少し変えると区間等差数列加算・区間和も扱えます。

仕組み

次のような更新を目標にします。

$A_l, A_{l+1}, \dots, A_{r-1}$ をそれぞれ $la+b,\ (l+1)a+b,\ \dots, \ (r-1)a+b$ で更新する。

これはセグ木のノードに最小値、最大値、総和、左端/右端のindexを持たせることで実現できます。

ノードのマージはそれぞれのminやmaxをそのまま取ればよいです。

作用素の作用については、区間 $[l,r)$ を $i \times a+b$ で更新するとき、

$a \geq 0$ なら左端が新しい最小値となり、右端が新しい最大値となる

$a < 0$ なら左端が新しい最大値となり、右端が新しい最小値となる

ことに注意することで最小値/最大値を計算できます。

総和は等差数列の和なので更新後の総和を計算して上書きすればよいです。

ノードのマージと作用素の作用が入れ替え可能なので（略）、無事遅延セグ木に乗せることができました。

添え字がずれていますが、 $i \times a+b$ の代わりに $i \times a+(b-la)$ で更新することで冒頭で述べた変更と一致します。

コード

ACLのlazy_segtreeを継承しています。初項の変更を自動的に行います。

using ll = long long;

// 区間min & 区間max & 区間sum & 区間等差更新
namespace arithmetic {

const ll LINF = ll(4e18);
const int INF = int(1e9) + 10;

struct S {
  ll min, max, sum;
  int l, r;
};
struct F {
  ll a, b;
};
S op(S s, S t) {
  return {min(s.min, t.min), max(s.max, t.max), s.sum + t.sum, min(s.l, t.l),
          max(s.r, t.r)};
}
S e() { return {LINF, -LINF, 0, INF, -INF}; }
S mapping(F f, S s) {
  if (f.a == LINF) return s;
  if (f.a >= 0)
    return {f.a * s.l + f.b, f.a * (s.r - 1) + f.b,
            (f.a * (s.l + s.r - 1) + f.b * 2) * (s.r - s.l) / 2, s.l, s.r};
  else
    return {f.a * (s.r - 1) + f.b, f.a * s.l + f.b,
            (f.a * (s.l + s.r - 1) + f.b * 2) * (s.r - s.l) / 2, s.l, s.r};
}
F composition(F f, F g) { return f.a == LINF ? g : f; }
F id() { return {LINF, LINF}; }

using lazy_segtype =
    atcoder::lazy_segtree<S, op, e, F, mapping, composition, id>;

struct lazy_segtree_arithmetic : lazy_segtype {
  using lazy_segtype::lazy_segtype;
  lazy_segtree_arithmetic(int n) {
    vector<S> sv(n);
    for (int i = 0; i < n; i++) sv[i] = {0, 0, 0, i, i + 1};
    (*this) = lazy_segtree_arithmetic(sv);
  }
  lazy_segtree_arithmetic(vector<ll> v) {
    vector<S> sv(v.size());
    for (int i = 0; i < v.size(); i++) sv[i] = {v[i], v[i], v[i], i, i + 1};
    (*this) = lazy_segtree_arithmetic(sv);
  }
  // f = (a, b)
  // [l, r) を b, a+b, 2a+b, ... で更新
  void apply(int l, int r, F f) {
    lazy_segtype::apply(l, r, {f.a, f.b - f.a * get(l).l});
  }
  void apply(int p, F f) { apply(p, {f.a, f.b - f.a * get(p).l}); }
};
}  // namespace arithmetic

using namespace arithmetic;

Verify

ちょうどいい問題がなかったので作りました。

Range Arithmetic Query (easy) | MojaCoder

Range Arithmetic Query (hard) | MojaCoder

愚直解と照らし合わせているので変なバグはないと思われますが、おかしい点があればご一報ください。

'Range Arithmetic Query (hard)'のstoqさんの提出 | MojaCoder

使用例

ABC177-F I hate Shortest Path Problem

F - I hate Shortest Path Problem

これが解けなかったのがきっかけで作りました。貼るだけで解けます。

int main() {
  int h, w;
  cin >> h >> w;
  lazy_segtree_arithmetic seg(w);
  for (int i = 0; i < h; i++) {
    int l, r;
    cin >> l >> r;
    l--;
    ll x = (l > 0 ? seg.get(l - 1).min : LINF);
    seg.apply(l, r, {1, x + 1});
    ll ans = seg.all_prod().min;
    cout << (ans >= LINF ? -1 : ans + i + 1) << "\n";
  }
}

Submission #25254062 - AtCoder Beginner Contest 177

他に使える問題を知っている方がいれば教えてください。

区間等差数列加算の遅延セグ木

関連して、区間に等差数列を足す遅延セグ木も考えられます。Min, Max の取得は難しいですが、総和は同様の考え方で実装できます。

using ll = long long;

// 区間sum & 区間等差加算
namespace arithmetic_add {

const ll LINF = ll(4e18);
const int INF = int(1e9) + 10;

struct S {
  ll sum;
  int l, r;
};
struct F {
  ll a, b;
};
S op(S s, S t) { return {s.sum + t.sum, min(s.l, t.l), max(s.r, t.r)}; }
S e() { return {0, INF, -INF}; }
S mapping(F f, S s) {
  return {s.sum + (f.a * (s.l + s.r - 1) + f.b * 2) * (s.r - s.l) / 2, s.l,
          s.r};
}
F composition(F f, F g) { return {f.a + g.a, f.b + g.b}; }
F id() { return {0, 0}; }

using lazy_segtype =
    atcoder::lazy_segtree<S, op, e, F, mapping, composition, id>;

struct lazy_segtree_arithmetic : lazy_segtype {
  using lazy_segtype::lazy_segtype;
  lazy_segtree_arithmetic(int n) {
    vector<S> sv(n);
    for (int i = 0; i < n; i++) sv[i] = {0, i, i + 1};
    (*this) = lazy_segtree_arithmetic(sv);
  }
  lazy_segtree_arithmetic(vector<ll> v) {
    vector<S> sv(v.size());
    for (int i = 0; i < v.size(); i++) sv[i] = {v[i], i, i + 1};
    (*this) = lazy_segtree_arithmetic(sv);
  }
  // f = (a, b)
  // [l, r) に b, a+b, 2a+b, ... を加算
  void apply(int l, int r, F f) {
    lazy_segtype::apply(l, r, {f.a, f.b - f.a * get(l).l});
  }
  void apply(int p, F f) { apply(p, {f.a, f.b - f.a * get(p).l}); }
};
}  // namespace arithmetic_add

using namespace arithmetic_add;

verify

HCPC2020 Day1 B - 三角形足し算

問題リンク：Aizu Online Judge Arena

提出：Aizu Online Judge Arena

参考文献

opt-cp.com

2021-08-04

千葉大生向けGPA計算ツール

追記：成績閲覧画面でpdf化ボタンを押すとGPAが表示されるようになったようです。そのためこのブックマークレットは非推奨です。

使い方

適当なページをブックマークした後、URLを次のコードで書き換えてください。ページ名は適当に変更して大丈夫です。

javascript:(function(a){s=document.createElement("script");s.src=a;document.body.appendChild(s)})("https://sto9.github.io/GPACalculator/GPACalculator.js");

学生ポータルの成績閲覧画面で先程のブックマークレットを起動するとGPAが表示されます。

2021-04-21

音ゲーのサポートツールを作った話

SOUND VOLTEXとCHUNITHMの各譜面の許容ニア/アタを計算して表示するツール『Score Tolerance』を作りました。
導入方法を書いておきます。

PC向け

①Tampermonkeyをインストールします。
Chrome: Tampermonkey - Chrome ウェブストア
Edge: https://www.microsoft.com/ja-jp/p/tampermonkey/9nblggh5162s#activetab=pivot:overviewtab
FireFox: Tampermonkey – 🦊 Firefox (ja) 向け拡張機能を入手

②拡張機能をインストールします。
greasyfork.org

するとSDVX譜面保管所やCHUNITHM譜面保管所で許容ニア/アタが表示されます。
不要になった場合はウィンドウ上部のTampermonkeyのロゴをクリックして停止または削除を行ってください。

Chrome及びEdgeで動作を確認しています。おそらくTampermonkeyに対応さえしていれば大丈夫です。

スマートフォン向け

①適当なページをブックマーク登録します。

②先程登録したブックマークのタイトルを適当に変更し、URLを次のJavaScriptで上書きします。
（2021/05/31追記：GitHub Pages上のjsファイルを呼び出すよう変更しました）

javascript:(function(a){s=document.createElement("script");s.src=a;document.body.appendChild(s)})("https://sto9.github.io/Score-Tolerance/ForBookmarklet.js");

譜面保管所で上のブックマークレットを実行すると許容ニア/アタが表示されます。
（chunirecの導入方法と同様です。）
Safariで動作を確認しています。
この方法はPCでも使えます。

おわりに

初めてJavaScriptを書いたのでかなり疲れましたが、それなりに使いやすいツールになったと思います。是非使ってみてください！

2021-03-27

作った問題

作問した競プロの問題です。

★はお気に入り。

ABC013D - 阿弥陀

yukicoder No.326 あみだますたー

beatmania IIDX の鍵盤が増えた場合

ガチ割れ

S 乱当たり

皿の上に鍵盤が配置されている場合

ガチ割れ

beatmania ∞DX

真・beatmania ∞DX

おわりに

参考文献

解決策

実行結果

区間に等差数列を作用させる遅延セグメントツリーとは

仕組み

コード

Verify

使用例

ABC177-F I hate Shortest Path Problem

区間等差数列加算の遅延セグ木

verify

参考文献

使い方

PC向け

スマートフォン向け

おわりに

yukicoder contest 247

yukicoder contest 271

Advent Calendar Contest 2020

MojaCoder