AtCoder Beginner Contest 186 (パナソニックプログラミングコンテスト) E-Throne

AtCoder Beginner Contest 186 (パナソニックプログラミングコンテスト) (ABC-186) E - Throne についての記事です．

問題へのリンク

atcoder.jp

ABC-186 E Throne

解法

全体で必要なステップ数は，

  • Kの倍数であって (つまり，mod K で 0 である)
  • mod N で -S である

だから，中国剰余定理で求められる．これを K で割れば答になる．

感想

コンテスト中は，拡張互除法の結果を一生懸命場合分けしていました． 中国剰余定理ってこういうふうに使うんですね．

コード

#include <bits/stdc++.h>
#include <cassert>
typedef long long int ll;
using namespace std;
#include <atcoder/math>
using namespace atcoder;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  auto solve = [&]() -> ll {
    ll N, S, K; cin >> N >> S >> K;
    auto [y, z] = crt(vector<ll>({0, -S}), vector<ll>({K, N}));
    if (y == 0 && z == 0) return -1;
    return y / K;
  };

  ll T; cin >> T;
  for (ll t = 0; t < T; t++) cout << solve() << "\n";

  return 0;
}

階段関数の std::map による表現 (ACL Beginner Contest E - Replace Digits)

AtCoder の ACL Beginner Contest E - Replace Digits についての記事です．

問題へのリンク

atcoder.jp

経緯・考えたこと

コンテストのときには，この問題を解き始める時点でまだ80分以上残っていたのに，結局ACできませんでした．想定解は遅延伝搬セグメント木を使うというもので，それもチラッと頭には浮かんだのですが，モノイド演算が出てくると思えずに捨ててしまいました．出てきますよねえ...．

ともかくセグメント木は捨てて別の方向で考え始め，次のようにすれば良いのではないか，と思い至りました． 以下の記号を使います．

  • 1をk個並べた数 ( $ 1 + 10 + \cdots + 10^{k - 1} $ の値) を $C_k$ とする．
  • Sの位置は，右端 (1の位) を0，左端 ($10^{N-1}$の位) をN-1 とする．
  • Sの位置iの数を $x_i$ と書く．($ 1 \leq x_i \leq 9 $)
  • Tを，数が変化する位置と値のペアの集合とする．つまり，$x_{i} \neq x_{i - 1} $ なる $i$ に対する $(i, x_i)$ の全体を T とする．

T を持っていれば，「位置p から位置qまでdにせよ」というクエリに対して，Sの値が前回からどれだけ増減するかがわかります．$(i, x_i)$ と $(j, x_j)$ が T の中で隣り合っていて，$p \leq i < j \leq q$ だとすれば， この部分で $(d - x_i) \cdot C_{j - i} \cdot 10^i $ だけ増えるわけです．こういうのを全部足し合わせれば良い． Sの値を求めたら，Tを更新します．pとqの位置をTに加え，pからqの間にあるものはTから削除します．

計算量ですが，クエリで端点 p が導入されると，Tの要素が1増えますが，その後のクエリで，両端点の間に入らない限り，その要素は値の計算に必要ありません．両端点の間に入った場合には，次の瞬間にTから削除されます．つまり，この寄与は全体として$O(Q)$です．各クエリで，pとqの間に入るTの要素の境を探したり，pやqを挿入したり間の点を削除するのはそれぞれ $O(\log N)$ ですから，全体として $O(Q\log N)$ となり，十分間に合うはず (実際，間に合います)，ということで実装を始めました．

ところが，いつまでたってもコードが完成しません．C++のsetやmap の lower_bound や upper_bound を使ってコードを書くのですが，end() が返ってきたり，集合の中に等しい要素があったりなかったり，「○以上の最小の要素」はとれても，「○以下の最大の要素」は (すぐには) とれない，など，間違う要因が多くて，苦手です．一言で言ってしまえば，練習が足りないのですけれど．

階段関数の std::map による表現

ということで，コンテスト終了後になんとか動くコードを書いて得た教訓をメモしておきます．

Tはペアの集合ですから，map<int, int> で表現することにします．

(1) 番兵を置く．今回だと，T[-1] = 0, T[N] = 0. これらと合わせて，初期状態では，T は {(-1, 0), (0, 1), (N, 0)}.

(2) Sの値の変化を計算するときに，pからqまでいきなり足していくのは，私の技量では無理．次のようにする．

  • まず，$x_p$ と，$x_{q + 1}$ を求める．たとえば $x_p$ を求めるときには次のようにする．
    • p が T の key に入っていれば簡単．
    • そうでないときには，「p以下の最大の要素」を求めることになる． これは，reverse_iterator を使って，次のように実現できる:
auto it = T.lower_bound(p);
auto rit = reverse_iterator(it);
// *rit が求めるもの
  • T に，$(p, x_p)$ と $(q + 1, x_{q + 1})$ を追加する．これらの点はあっても害にならない．
  • p から q までの和を求める．pとq+1が T のキーになっているとわかっているから，場合分けなど無しで計算できる．

(3) 最後に，p と q+1 の間の要素を T から削除する．これも，p と q+1 は T のキーになっているとわかっているので，単純なループで実現できる:

auto goal = T.find(q+1);
auto it = T.find(p); it++;
while (it != goal) it = T.erase(it);

ACコード

(ライブラリコードが長いです) atcoder.jp

2009 JOI 予選6 ビンゴ

2009 JOI 予選6 ビンゴ についての記事です．

問題へのリンク (AtCoder)

atcoder.jp

上のリンクで問題は見られますが，要は，$n$, $m $, $s$ が与えられた時， 以下を満たす数列 $\{a_i\}_i $ の個数を求めよ，というものです． 制約は，$1 \leq n \leq 7$, $1 \leq m \leq 2000$, $1 \leq s \leq 3000$．

  • 長さは $n*n$
  • 和は $s$
  • 各 $a_i$ は1以上 $m $ 以下の整数
  • 狭義単調増加

経緯

JOIの問題も解くと良いよ．というお勧めがあちこちで見られるので，ときどきは解いてみようと思い，この問題を考えました．

一応DPで解けまして，実行時間は 2500ms くらいでした．(制限時間は10秒と書いてあります．) ところが，「すべての提出」をみると，数ms で終了するコードがACしています．読んだらとても賢いコードだったので， メモしておきます．

自分の解法

$dp[i][v][w]$ = 長さが $i$ で，和にあと $v$ の余裕があって，最終項が $w$ である数列の個数．

和の「余裕」というのは，最終項を $w$ とすると，現在までの数列の和から後少なくとも $(w + 1) + (w + 2) + \cdots (w + (n^2 - i))$ は増えることが決まっているので，その分も加えた上で，$s$ との差を取ったものです．

$(i, v, w)$ の遷移先は だいたい $v / (n^2 - i)$ 個くらいなので， 計算量は $O( \sum_{i} sm (s / i) ) = O(s^2m\log n)$． 大きいけれど，10秒なのでなんとか間に合う，という感じです．(コード)

ちなみに，メモリ制限は256MBなので，dp を全部とっておくとMLEします．

blog で見た解法

検索をしていたらもっと賢い解法が紹介されていました． リンク先を見ていただければ良いのですが，ここにも書きますと，一番外側のループを数列の長さにするのではなく， 最大値の方にするというものです．

$dp[w][i][v]$ = $1$から$w$までの数を使ってできる長さ $i$ の数列で和が $v$ であるものの個数．

こちらは，各$(w, i, v)$ の遷移先は 2 個しかないので，計算量は $O( n^2 m s)$． 実装してみる と，実行時間は 1000ms ほどでした．

速い解法

提出されていた数msで終了するコードを読んでみたところ， 次のようにできていました．

$dp[i][v]$ = 長さが $i$ で，和が $v$ である数列の個数．

一見，最大値はいらないのか?? と思うのですが，いらないようです．テーブルの更新は次のようになっています:

  • $dp[i][j] = dp[i][j] + dp[i-1][j-i] + dp[i][j-i]$
  • $dp[i][j] = dp[i][j] + dp[i-1][j - (m+1)]$

たとえば $i = 3$, $m = 5$ としてみましょう．dp[3,9] には，2つの数列 $2, 3, 4$ および $1, 3, 5$ が属します (面倒なので数と集合を混同しています)． これらの数列の各数から1ずつ引いた数列 (ただし 0 になったら削除する) を作ってみますと， $1, 2, 3$ および $2, 4$ となります．これらは，dp[3][6] および dp[2][6] に属します． つまり，$dp[i-1][j-i]$ と $dp[i][j-i]$ です．最初の式はこのように導出されます．

逆に，$dp[i-1][j-i]$ と $dp[i][j-i]$ に属する数列の各数 (前者は0が先行すると考える) に1を加えると $dp[i][j]$ に属する数列になるかというと，だいたいなるのですが，$m $ の制約が問題になります． たとえば，$1,5$ は dp[2][6] に属しますが，$1, 2, 6$ は，$m = 5$ なので，制約に反しています． 新たに制約に反する数列ができる場合，その数列は，最終項 (今の場合は6)が $m + 1$ で， それを除いた数列 (今の場合は $1,2$) は， $dp[i-1][j - (m + 1)]$ に属していることがわかります．これが2番目の式が必要な理由です．

これなら計算量は $O(n^2 s)$ ですから，一瞬で答が出るのももっともです． こんなのどうしたら考えられるんですかね?

Codeforces Global Round 10 G. Omkar and Pies

Codeforces Global Round 10 G. Omkar and Pies についての記事です．

問題へのリンク

codeforces.com

経緯

全然見当もつきませんでした．editorial を読んですごく勉強になったように思います．

解法

以下，ほぼ editorial のまま．

まず，「1をできるだけ多く重ねる」問題だと思って良い．なぜなら，そのときに0も一番多く重なるから．

最初の文字列を$s$, 目標文字列を$t$ と書くことにする．また，$l$ から $r$ までの変換を合成したものを， $T(l, r+1)$ と書くことにする．

さて，仮に「$l$, $r$ を適当に選んで，変換結果をtに一致させられるか?」という問題だったとする． 愚直だと $O(n^2)$ で間に合わない．次の事実に注目する．

$T(l, r)(s) = t$ であることと，$T(l, n)(s) = T(r, n)(t)$ であることとは同値

すると，変換結果はたかだか $2^k \leq 2^{20} \sim 10^6 $ しかないので，各 $i \leq n$ について， $T(i, n)(s)$ と $T(i, n)(t)$ を全部求めて，一致するものがあるかどうか見れば解ける．なるほど....

ちなみに，$T(i, n)(s)$ を全部求めようとするとき，$T(n,n)(s)$ から $T(0,n)(s)$ まで逆に求めていくのだが， $i$ 番目の互換を $c(i)$ と書いたとき，$T(i,n)(s) = T(i+1,n)(c(i)s)$ というふうに，望む方と反対側に来てしまう． $T(\cdot,\cdot)$ の逆変換 $S(\cdot,\cdot)$ を考えれば，$S(i,n)(x) = c(i)S(i+1,n)(x)$ と，うまい方向に来る． $S$ だの $T$ だのは $k$ の置換なので，長さ $k$ のベクトルで表せて，逆変換は $O(k)$ で作れるから，これでOK．

もとの問題に戻る．さっきの解はちょっと見方を変えると，$\{1,\ldots,k\}$ の各部分集合 $w$ に対して，

  • $is[w] =$ 「$T(i,n)(s) = w$ となる $i$ があればそのどれか．なければ -1」
  • $it[w] =$ 「$T(i,n)(t) = w$ となる $i$ があればそのどれか．なければ -1」

というのを作って，$is[w] \geq 0$, $it[w] \geq 0$ となる $w$ があるかどうか調べた，ということになる． そうすると，「$T(i, n)(\cdot) = w$」の部分を，「$w \subseteq T(i, n)(\cdot)$ 」というふうに変えてやり， しかも，$is[w]$ については，できるだけ小さなインデックスを，$it[w]$ についてはできるだけ大きなインデックスをとるように してやると，$it[w] \geq 0$, $\,is[w] \geq 0$, $\,it[w] - is[w] \geq m $ となる $w$ で，1を最もたくさん含むもの，を求めれば良いことになる． うーん．これもなかなか....

これを実装するには，次のようにすれば良い (ここは editorial には漠然としか書いてなかったので，コードを読んだ)．

  • 最初に，上の簡易問題に対する is, ts を作る．is は大きく，ts は小さくとる．
  • $\{1, \ldots, k\}$ の部分集合 $w$ を大きい方から見ていって， $w$ の各要素 $j$ に対して，$is[w - \{j\}]$ を $\min(is[w - \{j\}], is[w])$ で更新する． $it$ も同様．

コード

codeforces.com

AtCoder Beginner Contest 175 D-Moving Piece

AtCoder Beginner Contest 175 (ABC 175) D - Moving Piece についての記事です．

問題へのリンク

atcoder.jp

解法

$i \to P[i]$ にリンクがある有向グラフだと思って，連結成分 (といってもサイクルだが) ごとに考える．

ループを回ってプラスのときに，端の部分をどこにとるか... とか考えていくと，ループをまわる回数が 長さ / K だけとれるとかとれないとか-1するとか複雑なコードになってバグる．(いや，それでもバグらないように書けないといけないという話はあるけれども．) Niuezさんのツイート で教えられたのだが，iとjを固定して， iからjまでのパスのスコアの最大値を考えることにすれば簡明になる．

  • 直接行く
  • 直接行った後に，ループを回れるだけまわる．

の2つのうちの大きい方を取れば良い．直接行くコストは，あらかじめ累積和を2周分作っておいて，引けば良い．

コード

atcoder.jp

AtCoder Grand Contest 045-A Xor Battle

問題へのリンク

atcoder.jp

状況

2020/08/15 のあさかつで出題されました． 他の問題で時間がかかって，この問題まで手が回りませんでした．

この問題自体は，コンテスト時に解けていましたが，実行時間がだいぶかかりました (1.3秒)． 解説 を斜め読みした感じでは，想定解と同じ方針だと思うのに， なぜこんなに時間がかかるのか不思議に思いましたが，それ以上追求していませんでした．

今回，他の人のソースを読んでみて，なるほどこれは良くなかった，とわかりました．

解法

$F_2$ を，集合 $\{0, 1\}$，和は XOR，積は AND の体とする． $V$を，$F_2$の長さ60のベクトルがつくる，係数体が $F_2$のベクトル空間とする． $A_i \leq 10^{18} < 2^{60}$ なので，各 $A_i$ は$V$の要素とみなせる． $\{ A_j \mid i < j \leq N \}$ の張る部分空間を $V_i$ と書くと，第 $i$ ラウンドにおける値が $x$ のとき， 人0 が勝つ必要十分条件が $ x \in V_i $ であることが，後ろからの帰納法でわかる．

実装

上の解法を，持っていた行列のライブラリを使って，そのまま実装したのがよろしくありませんでした． $i$ を後ろから見ていって，$A_i$ から $A_N$ までの (本当の) ベクトルをならべた行列を作って， 掃き出し法で rank を計算していく．人1 の手番のときに，rank が増えることがあれば人1の勝ち． そういうことがなければ，人0の勝ち，というように実装していました． もう少しは工夫したのですが，まあ本質的にはこういうコードでした．

改良

別に「上三角」などにする必要はないわけで，要は， 初めて出てくる非0成分のインデックスが重複しないようにしていれば，良かったのです．つまり:

0でないベクトル$v = (v_i)_i $ に対して，$\text{msb}(v) = \min\{ i \mid v_i \neq 0\}$ と書きます． ベクトルの集合 $X$ が，$v, w \in X$ ならば $\text{msb}(v) \neq \text{msb}(w)$ を満たすときに，$X$ を良い基底とか いうことにしますか．このとき， ベクトル $v$ が 良い基底$X$ の張る空間に属するかどうかを判断するには， $v$ の非0 成分を順に見て，そこが msb になっている $X$ の要素 $x$ があったら， $x$ の適当な定数倍を $v$ から引いて ($F_2$ なら単に $v$ に $x$を足して) いくことを繰り返して0になるか見れば良く， $v \not\in X$ だったときには，この計算の結果のベクトルを $X$ に加えれば，$X \cup \{v\}$の張る空間の良い基底になる， というわけです．

こう考えれば，今回の問題では，実装上，ベクトルにする必要はなく整数のままで扱え，上の msb は，実際に最上位ビットです．

コード

atcoder.jp

ということで，そういうふうにコードを書きました．実行時間は11msでした．

AtCoder Beginner Contest 011 D - 大ジャンプ

AtCoder Beginner Contest 011 D - 大ジャンプ に関する記事です．

問題へのリンク

atcoder.jp

状況

2020/08/07 のあさかつで出題されました． 解けたつもりでしたが，時間内にはコードが書ききれませんでした． その後も考えたところ，結局，解けてはいなかったことがわかりました． 誤差が累積したのか，と思ったのですが，そうではなくて，double で表現できる範囲を超えていたのが問題でした．

解法

適当に回転することを考えれば，$X \geq 0$, $Y \geq 0$ としてよい． $X$ や $Y$ が $D$ の倍数でなければ，到達できない． $D$の倍数になっているときは，これらを $D$ で割っておくことで，$D = 1$ と考えることができる． $x_P$, $x_N$, $y_P$, $y_N$ を各々x/y方向への正/負の移動回数とすると， $x_P - x_N =X$, $y_P - y_N = Y$ となる．$p = x_P + y_P$, $n = x_N + y_N$ と書くと， $p + n = N$, $p - n = X + Y$ より $p = (N + X + Y) / 2$, $n = (N - (X + Y)) / 2$ なので，以下が必要．

  • $X + Y \leq N$
  • $N + X + Y$ は偶数

逆に，この2つが成り立っていれば，$x_N = 0, 1, \ldots, n$ に対して，$x_P$, $y_N$, $y_P$ が定まる． これらの各々の組に対して，そのようになる確率は $$\frac1{4^N} \binom{N}{x_N}\binom{x_P + y_P + y_N}{x_P}\binom{y_N + y_P}{y_N}\binom{y_P}{y_P}$$ であるから，これらの和を求めれば良い．

計算上の問題点と解決

上の解法までは到達したのですが，その後の計算ができませんでした． 2項係数$\binom{n}{r}$ は，$(n(n-1)\cdots(n-r+1)) / (r(r-1)\cdots1)$ を計算すれば良いので，全体として $O(N^2)$ で計算でき，$N \leq 1000$ ですから，計算量的には問題ありません． 問題は値が大きくなることで，DBL_MAX の値は $1.8\times10^{308}$くらいなので， $4^{1000} = 2^{2000} \approx 10^{600}$ は，表現できません． またたとえば，$\binom{1000}{500}$ は，大雑把に $2^{1000} \approx 10^{300}$ くらいあり，このまま正直に計算すると溢れます．

そこで，$x_N + x_P + y_N + y_P = N$ であることに注目し，$f(n, r) = \binom{n}{r}/4^r$ と書くと， 上の式は，$f(N, x_N) \cdot f(x_P + y_P + n_Y, x_P) \cdot f(y_N + y_P, y_N) \cdot f(y_P, y_P)$ となります． $f(n, r)$ は，次のようにすることで，溢れさせずに計算できます:

$$ f(n, r) = (n / (4r)) \cdot ( (n-1) / (4(r-1))) \cdot \cdots \cdot ( (n-r+1) / (4\cdot 1))$$

まあ，LDBL_MAX は $1.2\times 10^{4932}$ なので，long double を使えばそれで終わり，という話もありますが．

実装

atcoder.jp