AGC 034 F RNG and XOR

解説と全然違うことをして通したので書く。各ステップは難しくないが相当の考察腕力を必要とする。実装はほぼ無。

 

問題概要

最初 0 にいて、 \{0,1,...,2^N-1\} 上の確率変数 X を xor していくランダムウォークを考える。各状態について、はじめてその状態に至るまでの遷移回数の期待値を求めよ。 N \leq 18, X からは全部の値が正の確率で出る

 

母関数による言い換え

遷移行列を A とする。 e _ j を j 番目の要素のみ 1 であって他は 0 であるようなベクトルとして、 q _ {j,k} = e _ jA^ke _ 0 とする。すなわち q _ {j,k} は時刻 k に状態 j にいる確率。この母関数を q _ j(x)=\sum _ {k=0}^{\infty} q _ {j,k}x^k とする。

 

これらを用いて、時刻 k に初めて状態 j にいる確率 p _ {j,k} を求めていく。ただし、 j=0 に対しては p _ {0,k} は時刻 0 を除いて初めて時刻 k に 0 にいる確率とし、便宜上 p _ {0,0}=-1 とする。より正確には、この母関数 p _ j(x)=\sum _ {k=0}^{\infty} p _ {j,k}x^k を求める。

 

j=0,k \geq 1 に関しては漸化式 \sum _ {i=0} ^ {k} p _ {0,i}q _ {0,k-i} = 0 が立ち、 p _ {0,0} = -1, q _ {0,0} = 1 から p _ 0(x)q _ 0(x)=-1 を得る。 j\neq 0 に対しては、 p _ {j,k}=-\sum _ {i=0} ^ {k} p _ {0,i}q _ {j,k-i} がやはり DP のようなことを考えると出てくるので、 p _ j(x)=-p _ 0(x)q _ j(x) を得る。まとめれば、 p _ j(x)=\frac{q _ j(x)}{q _ 0(x)} を得る。

 

 さて、求めたい期待値は \sum _ {k=0}^{\infty}kp _ {j,k} であった。これは、 p _ j(x) を x で一回微分したあと、 x=1 を代入すれば得られる。商の微分公式を用いれば、求めたい値は、 \frac{q _ j(x)'q _ 0(x)-q _ j(x)q _ 0(x)'}{q _ 0(x)^2} の x=1 での値である。

 

固有ベクトルへの分解

非負整数 t に対し、母関数  \frac{q _ j(x)'q _ 0(x)-q _ j(x)q _ 0(x)'}{q _ 0(x)^2} の分子と分母の x^t の係数を評価していく。このまま定義式を代入すると行列が入ってきて大変なので、 A の固有ベクトルに e _ 0 を分解して考えることにする。 A の固有ベクトルは 2^N 次 Hadamard 行列 (定数倍に関しては、係数はすべて 1,-1 とする) の各行に一致する。その i 行目 ( 0-origin) に対応する固有ベクトルを h _ i と書き、対応する固有値を \lambda _ i とする。これを用いれば、 q _ {j,k} = e _ jA^ke _ 0 = \frac{1}{2^N}e _ j\sum _ {i = 0}^{2^N-1}\lambda _ i ^k h _ i = \frac{1}{2^N}\sum _ {i = 0}^{2^N-1}\lambda _ i ^k h _ {i,j} と書ける。

 

極限値の評価

A の要素はすべて正なので、唯一の最大固有値は固有ベクトル h _ 0=(1,1,...,1) に対応する 1 である。よって、 k を大きく取れば、 \lambda _ i ^k (i\neq 0) は \lambda _ 0 ^k に比べて無視できるようになることが期待できる。これを用いて、大きい t に対する x^t の係数を評価していく。

 

まずは簡単な分母の方から評価する。先ほどの q _ {j,k} の表式を求めたい式に代入し、主要項にならない項を無視すると、分母の係数は (主要項とそれにつく係数以外を無視して) \frac{1}{2^{2N}}\times t となる。

 

分子に関しては、引き算によって \lambda _ 0^t に対応する項が消えるので、次の項も評価してやる必要がある。結局、計算すると展開式のうち主要項として残るのは \frac{1}{2^{2N}}\times \sum _ {i=0}^t \sum _ {s=1}^{2^N-1}i\lambda _ s^{t-i}(h _ {0,s}-h _ {j,s}) の項となることが分かる。 \sum_{i=0}^t i\lambda _ s^{t-i} を評価すると大きい t に対して \frac{t}{1-\lambda _ s} が主要項として残ることが分かる。よって、分子の係数は (主要項とそれにつく係数以外を無視して) \frac{1}{2^{2N}}\times t\times \sum _ {s=1}^{2^N-1}\frac{1}{1-\lambda _ s}(h _ {0,s}-h _ {j,s}) となる。分子と分母の評価を合わせて x=1 での評価を行えば、結局求めたい値は \sum _ {s=1}^{2^N-1}\frac{1}{1-\lambda _ s}(h _ {0,s}-h _ {j,s}) であることが分かる。

 

 答えの計算

 さて、この値を計算することを考える。各固有値 \lambda _ s の値は、与えられた確率の列を Hadamard 変換したものの第 s 要素そのものであり、高速 Hadamard 変換を用いて求められる。 v _ 0=0, v_s = \frac{1}{1-\lambda _ s}(s\neq 1) としてできるベクトル v を考える。 \sum _ {s=1}^{2^N-1}\frac{1}{1-\lambda _ s}h _ {j,s} は、 v を Hadamard 変換したものの第 j 要素に他ならないため、これも高速 Hadamard 変換で求められる。最後に、 \sum _ {s=1}^{2^N-1}\frac{1}{1-\lambda _ s}h _ {0,s} は、上述の Hadamard 変換の第 0 要素である。このことから、この問題は、

・与えられた確率の列を高速 Hadamard 変換して各固有値を求め、

・上述の v を計算し (ただの割り算)、

・ v を高速 Hadamard 変換してできる列の第 0 要素から第 j 要素を引いた値を各 j に対して出力する

というアルゴリズムを用いて解くことができる。

 

 

ソースコード

 https://atcoder.jp/contests/agc034/submissions/5775887

AGC とか埋めまとめ

今年のはじめ頃に AtCoder 埋めをしたので、感想を書き連ねます。問題を選ぶ基準は、すでに埋めた全員 rated のコンテストの 1300 以上とあと若干の気になったものたちです。

(ネタばれ防止用空白)


































(空白ここまで)

AGC 001 E:
当時は非典型だったけど一回出ちゃえば解法忘れないからもう典型なんじゃないかな、本番はなんか解けた

AGC 001 F:
N*N グリッド作って〇書いていろいろ線引いてたら解けた覚えがあるけど、けっこう時間かかったし難しい
最初やった時は平衡二分探索木が必要になって詰んでた

AGC 002 E:
普通に勝ち負け書いてたらできるけど細かい実装に若干ハマった覚え まあ簡単だと思う

AGC 002 F:
典型数え上げ 生成されるものを数えるときは生成されるものを認識する簡単なアルゴリズムを作ってその動作を数えるアレ

AGC 003 E:
writer 手持無沙汰になって excel のセルのコピー機能を無為にガシャガシャやってたらできた問題

AGC 003 F:
writer 最初全体が連結になるか判定だったけどお布団にいたら数えられることに気づいた

AGC 004 E:
言われればまあそうっていう感じだけど微妙に見えにくい あとグリッドをガシャガシャ動かす羽目になるので実装頭壊れる

AGC 004 F:
2200 だけど人間的に解ける
まず、こういうのは葉から操作回数を決めていくんだけど木の場合は greedy に順に操作回数が決まっていく
なもりの場合は、サイクルの各頂点にくっついてる木を見ると「何回この色で塗ってください」みたいなのが定まってることになって、サイクルに対する問題に帰着されて、これは解ける

AGC 005 E:
これ相当難しいと思うんだけどみんな簡単って言う……
人を片方消すのはまあよくて、到達した瞬間逃げ放題の頂点の条件もわかるんだけどその先がきついと思う
悩み続けたらなんかぬるっとできたけど再現不可能

AGC 005 F:
これは素直 FFT できるように項を分けるのに慣れてますかというだけ

AGC 006 E:
つくれるもの全体は部分群なので位数を実験で数えるのは典型 実験すると全体の 1/4 が作れるのでパリティ条件を 2 個探せばよく、ありがちなものを試すと出る

AGC 006 F:
AA->B, BB->A は mod 3 で見るのの初出かな、なんでこの特定の遷移が何度も出されてるのかわからないけど
当時はかなりすきだったけど今となっては典型

AGC 007 C:
1000 点とは 適切にやると非本質っぽい条件が消えていってシンプルな問題にはなるけどそれもまた難しかった覚えがある

AGC 007 E:
DP っぽいことする以外にやりようがなくてそうするとまあこれしかないよねという感じ log がたくさんついて若干不安になる

AGC 007 F:
思った通りにお絵描きするとできる

AGC 008 E:
やることはわかるんだけどやるのが大変すぎる……
AGC たまにこういう見た目が面白そうなだけなものが出てくる、たぶんりんごさんの問題評価の癖

AGC 008 F:
やることはわかるがたるのが大変その 2
求めたいものの式を無心で変形すると求められるものの足し引きで書けるがちゃんと求めるのが大変
Petr がこの回 tedious って言ってた

AGC 009 D:
writer なんか考えてたらできて面白いと思ったけど既出らしくかなしい
りんごさんはこれしかないでしょみたいなノリで解いてたので難易度評価バグった

AGC 009 E:
writer これお気に入り
あまり解けると思わずに適当に考えてたらなんか解けてテンション上げてた

AGC 010 E:
考えることが複雑で頭壊れてくる 実装も特殊な重さだし王道難問という感じ
まあ落ち着けばできるんだけど落ち着くのが大変

AGC 010 F:
雰囲気でだいたい戦略わかるのでやると通る 配点ミスだと思うけどこういうふわっとしたの過剰に難しく評価されがちな傾向はあると思う

AGC 011 E:
これは見たことないタイプで難しい
9 倍するの見えてしまえばまあできるとは思うのでここだけ覚えておこうという感じ

AGC 011 F:
いろいろと複雑で頭壊れるけど特に特殊なところはないので落ち着けばできる
時間内に間に合うかというとそれは別問題

AGC 012 F:
条件エスパー系 妥当にやってもできない数え上げは難しい
それっぽい条件を思いついたら証明しにいくのが良い気がする

AGC 013 E:
解説は頭っぽいことしてるけど式書いて無心でいじればできる
式を組合せ的に解釈して思考する系で combination 系でないやつは大抵式のままいじってもできる

AGC 013 F:
正答派難問 最初 O(NQ) すら全然わからなくてビビるやつ
ステップが 3 つあって、区間系の条件言い換えの典型っぽさのある最初の 2 つをやると O(NQ) にはなる
最後は全クエリ並列に処理しようとすると、各クエリが欲しがる条件がまとまってくるのでオーダーが落ちる、これはそんなに見ないタイプ

AGC 014 E:
パスとか言ってるけどグラフ理論の教科書の定義の部分っぽい感じで要するに連結性の話をしている
やることはわかり、なぜかマージテクできないと思い込んでハマってたけど両方の木を一気に考えればよい

AGC 014 F:
増加列がどこに行くかみたいなのをお絵描きして三日悩んだらできたけどこの不変量はなに……
他の AGC の問題と比べても段違いに難しいと思う 何かにこのテク使えないかな

AGC 015 F:
writer 解説に書いた定理っぽいのを見つけたので出した
適切に実験すればできるんじゃないですかね

AGC 016 E:
いろいろ手で実験したりしてるとまあ条件は見えるのでできる 王道

AGC 016 F:
指数系苦手…… grundy 数そのものを持たなくていいのかなり新鮮だった

AGC 017 C:
1000 点とは 90 度回さないと大変な目にあいそうというのはそうなんだけどそこから先もきつい……

AGC 017 F:
こういうの見ると上からやりたくなってしまうのは宿命なんだろうか 横に見ないと無理ということを結論するのにけっこうハマった
あとは i->j のパスに中間状態を付け加えて遷移まとめてやるやつをどう適用するかというだけ ゼータ変換みたいな感じ

AGC 018 E:
累積和っぽい変形は combination 慣れでできて、16 個問題を解けばいいことはわかる
経路数の話だと思えば自然な境界足し引きでできる

AGC 018 F:
適当なものを作って補正することにするとけっこうきれいにフローになるけど非想定だったっぽい(10 万の重みなし dinic なのでオーダー的にも大丈夫)

AGC 019 E:
落ち着いていろいろ分類して DP の式を書くと状態がまとまることがわかる
解説変なことしてるけどまあ 2 乗しか書かないと思う

AGC 019 F:
適当に言い換えると combination 系の境界足し引きをするだけになるけどなんか添え字にハマった 簡単だとは思う

AGC 020 E:
どうせこれしかできないし状態数少ないやろみたいな DP を書いて送り付けるとなんか通る
tourist だとりんごさんの良問判定ガバガバになるので

AGC 020 F:
積分したくないという一心でできそうな方針を探すと第一感がこれ まあやけに許容誤差が小さいとかいろいろ怪しいポイントはあるよね
期待値とると消えるので特定条件下での平均を実現しそうなケースだけやれば OK というの思考過程での実験とかではよく使うのでそれが問題になっただけと思えばまあ

AGC 021 F:
writer DP 自体そんなに難しいとは思わないけどりんごさんがハマったのでここに置かれた

AGC 022 D:
落ち着いてやることをやればできるが、場合分け多いしコンテスト中にできるかといわれると微妙
場合分けだけど場合のそれぞれが結構きれいなのでやる気になる

AGC 022 E:
普通の数え上げ 判定問題のアルゴリズムの動作を数えるやつ 典型

AGC 022 F:
落ち着いて適切な方向から見ると判定問題のアルゴリズムが生える系 適当にやりすぎてオーダー増えたので埋め込んだ

APC 001 G:
場合分けが大変 コンテスト中はひたすらこれと格闘していた
やればできるとは思うけど合わせるのはかなり大変

APC 001 H:
列の場合を適切な方法で解けるとそれを拡張できる
HL 分解ってデータ構造乗せる以外にもたまにこういうきれいな使い方ができるし解析に使えることも多いので心の片隅に置いておくとよい
各ステップの最初の処理の部分の操作回数最初見積もってなくて一瞬ひやっとしたけど大丈夫だった

APC 001 I:
下手な方針を選ぶと実装が手に負えなくなる
座標圧縮は良くて、障害物に影響されてできる最短路は圧縮した座標の隣くらいしか通らないことがわかるので、座標圧縮後に重み 1 で最短路してから補正すれば十分なことがわかる
これでもとても軽いということはないが、見通しは良い

APC 001 J:
非自明なケースを作りに行くと作れて絶望的になるが、実は素直に積んだ後に三方向から長方形領域をずらしたような形を作ると残り全部決まることがわかるので、これを数える
いろいろな値が出てくるが、結局全部適切に計算すると 4 乗で済むことがわかるので、落ち着いてそれぞれ数えてやる

CODE FESTIVAL FINAL 2017 H:
本番バグらせて賞金がだいぶ減った
問題文の条件を言い換えるとそれっぽくなるのでそれを使って DP する

CODE FESTIVAL FINAL 2017 I:
条件エスパー系 実験すると必要条件が十分条件なことがわかる
あとはゼータ変換っぽくやるとできる

CODE FESTIVAL FINAL 2017 J:
実家重心分解で通るので……

CODE FESTIVAL 2017 Qual A E:
writer 場合分けして combination 頑張るとできると思う
手数と気を付けることは多めなのでそんなに解かれなかった

CODE FESTIVAL 2017 Qual A F:
お気持ちをそのまま DP の式に落とすと通る

CODE FESTIVAL 2017 Qual B E:
素直に判定条件を書いて素直に式をいじるとできる

CODE FESTIVAL 2017 Qual B F:
結局証明できてないね…… 綺麗だとは思うのだけど
文字列系のこういう証明闇になりがち

CODE FESTIVAL 2017 Qual C E:
発想も結構難しいし気を遣う、実装はもっと気を遣う
見た目に反して面白いけど、コンテスト中に通せるものではないね

CODE FESTIVAL 2017 Qual C F:
これも判定条件を書くと多項式にはなるが、3 乗まで落とすパートの累積和を変なものを取らないといけなくなって大変な目にあった
結局更新順序を異常にして通したけど最初の方針が悪かったのかな

MUJIN 2017 B:
素直にできる操作をするとそれ以外にやりようがないことも同時にわかるので適当に場合分けしてちょっとやる こういうお気持ち系はりんごさんの難易度評価が上にぶれがち

MUJIN 2017 C:
かなり悩んだ 正しい方針以外はすべてがダメダメなので手が動かないタイプ
正しい方針も見たことないタイプで、難しいと思う

MUJIN 2017 D:
条件エスパー系 比較的簡単に証明できる
メモ化で書くと楽 奇数の場合も実はきれいに処理できて良い

CODE FESTIVAL GRAND FINAL E:
この考察パートはどこをとっても見たことがない 1000 点とは……
確かに見るべきものを絞る段階でサイクル消せるけど有向でそんなことしようと思うのかなぁ

CODE FESTIVAL GRAND FINAL H:
rank しか関係ないことは対称性からわかる 残りもひたすら対称性って言い続けながら線形空間の様子をイメージし続けるとできる
やることは多いので時間はかかる

CODE FESTIVAL GRAND FINAL I:
こういう緩い構成は適当に作って座標圧縮が筋なのかな こういうのも典型化したいね

CODE FESTIVAL GRAND FINAL J:
構造を適切に見ると普通に数えられる やればできる系

CODE FESTIVAL FINAL 2016 H:
DP は簡単で、その様子を適切に眺めるとまあできるんだけど難しい……
怪しい制約を生かそうという思考をしてもそんなに簡単になるかというと……

CODE FESTIVAL FINAL 2016 I:
部分群系は実験して状態数をカウント いろいろ実験すると見えるのでそれを書く

CODE FESTIVAL FINAL 2016 J:
割り当てた後にサイクルに沿って回す操作をすれば割当先までの距離の和みたいなものが減少することがわかるので、必ずできることはわかる
上から突っ込むものの割当先までの距離の集合だけ考えても、各距離はサイクルに沿って回す操作で増加しないので上からの距離の列が辞書順最小になるように埋めていけばよい
辞書順最小なので順次決めていけて、毎回フローを流すとできるが遅い
グラフは単純な形をしているので maxflow-mincut で言い換えてやると高速に判定ができる形になり、できる



埋めてないのがたまってきてるのでまた埋めないと……

ICPC におけるチーム Cxiv-Dxiv の基本戦略

  • この記事は何か

2015 年から 2018 年にかけて活動した、チーム Cxiv-Dxiv(Hujiwara, hogloid, DEGwer) のコンテスト中の立ちふるまいについてです。

  • メンバー紹介

Hujiwara: 幾何とか非典型実装をやる
hogloid: データ構造とか文字列とかをやる
DEGwer: 数え上げとかロシアゲーをやる

実力が似通っている && 各々の得意分野が異なるチームです。全員の得意分野を合わせるとほぼ全分野が網羅されます。
解くスピードは遅いので序盤はダメですが、逆に終盤まで速度が落ちないのが強みです。多分難しいセットほど強いと思います。

  • 実績

WF 2017 12位(銅)
WF 2018 4位(金)

アジア地区予選 2015 つくば 5位
アジア地区予選 2016 つくば 2位
アジア地区予選 2016 バンコク 2位
アジア地区予選 2017 ホーチミン 2位
アジア地区予選 2017 つくば 1位

国内予選はひどい

  • 戦略

初期は戦略が固まっていなかったですが、チームで何回か 5 時間をやっているうちに固まってきました。
固まる前のものを書いても仕方ないので、最終形態だけ記述しておきます。

コンテストが始まったら問題を機械的に配分します。WF やロシア合宿のセットなど問題の並び順が完全ランダムな場合は何も考えずに等分します。
そうでない場合(国内予選や日本のアジア地区予選など)は、前の方を Huji, hog の 2 人が分担して読み、ぼくはまったり後ろの方を読んで解法を考えておきました。
これは、ぼくの実装が遅い && ぼくは考察系担当なので、前の方をぼくがやる利点がないし、そんな暇があったら後ろの方を考えて詰めるなり適切に前を解いた人に投げるなどしておいた方がいいためです。あと英字キーボードには早く慣れておいた方がいいです。どこで使うのも英字配列なので。

ただ、他の 2 人とて特段速いわけではないので、毎回スタートはかなり悪いです。ということで、全完速度勝負とかになると弱くて、よって国内予選は勝てない。
ペナルティのシステムを考えると序盤の速度はペナルティにかなり大きな影響を与えるわけですが、結局何しても無理だし運もかなり絡むので諦めました。
WF 二年連続で 8 完内最下位だしね…… 特に序盤の問題の実装が重めだとどうしようもないです。逆に序盤の実装が無だと(ロシアセットとかでたまにある)上手くいくことがあります。
ロシアとかだとたまに変なものの FA を取ったりします。

本題に戻ります。問題を配分した後適当に見た目がよさそうなものから順に読んで考えていきます。できる && ある程度実装が軽い とわかったら他のを読む前にそれを書き始めます(どうせ実装しているうちに他の人が読んでくれるため)。ここで注意すべきは、できるからと言って実装が重めなものに手を付けるのはやめておいた方がいいということです。まあパソコンが空いている && 実装方針を間違いようがない なら手を付けてもいいんですが、たいていの場合そういうのは終盤まで残って一人戦線離脱という感じになります。
ある問題ができる状態になったら、何分くらいかかりそうかを聞いて実装をかわるかどうかとかを判断します。30 分以上かかるのを序盤に始めるのはあまりよくなくて、そういうのは解法が分かっても放置しておくべきです(パソコンが空いていない場合)。

問題を見て明らかに他の人に向いているようならその人に投げつけます。
サンプルが明らかに文字列だった時点でぼくは hogloid に投げるし、10^9+7 と書いてある問題が無条件でぼくに飛んできます。たまに本質が数え上げじゃなかったりするので投げ返します。
データ構造だったら考察しきってから hogloid に投げつけたりします。幾何は図を見た瞬間に Hujiwara に投げていました。
どの問題がどの状態になったかの表みたいなのを管理した覚えはありません。各々がやっている問題や解いた問題は聞けばすぐわかるので、暇になった人が適宜やることをあぶり出していけるためです。

ということで、序盤は各人のところに得意分野が集まっている状態になります。よほどのことがない限り、開始 1 時間ちょっとで各人がメインでやる問題が 1 個か 2 個に絞られている状態になります(簡単枠は既に解いた or 実装中 or パソコン待ち になっていて、やることはわかるが明らかに実装が重すぎることが分かりきっているものとかは見なかったことにするため)。
とはいえ大抵実装キューが詰まっているので、軽そうなものから順にやっていきます。もちろんバグったら印刷して交代しますが、パソコンをちょっと使えばデバッグ効率が数倍良くなる場合はパソコン上でデバッグするのも選択肢には入ります。簡単セットだともうしばらくするとパソコンに触れていない人のやることがなくなります。

順位表ですが、最序盤は適当に選んだものを通せるかどうかなので気にしません。実装が重めなもの以外にできることがなくなったタイミングで確認して、コンテストの全体像を把握します。簡単そうな問題を把握するのは早いタイミングでできているので、やる問題を選ぶ目的というよりはコンテストの性質を見極める目的に使います。
もし実装が重いと判断したものがガンガン通されているようであればそのセットは重いセットです。そうでない場合は軽いものはその時点でたいてい通せているので、AC が 1 つ以上出ているものに重点的に取り組むことにします(ライブラリゲーとか既出とかだと判断した場合は放っておきます)。
十分軽いのに解かれていないことは国内はおろかロシアでも普通にあるので、順位表よりも自分の判断を信頼して軽い順にやっていきましょう。FA がおまけでついてきます。
たまにとても難しいセットだと序盤からパソコン空きまくりということがあります。そういう時は通されている実装枠があるならそれに手を付けるのが最適だと思います。
大抵そういう時は序盤に通されるものがバラバラになりがちですが、0 と 1 は大きく違うので 1 回以上通されているものを重点的に考察します。
大量の WA が出ているものは地雷なので敬遠しますが、解法に自信がある場合はやります。もちろんライブラリゲーとかなら適切に諦めます。

そんな感じでできるものを消化していくと 4 時間経過して順位表が固まります。と言っても、この時間帯の順位表から読み取れる情報はあまりないので特に困らないのですが。解法が分かっているものが残っていても、重い場合はこの時間帯から手を付け始めて通ることは少ないです。特に、残り 20 分で何かはじめて通せる、と言ったことはまずない(そういうのは序盤に通っている)ので、デバッグに集中します。どうしようもないもの以外残っていない状態になった場合も同様です。
人数分印刷して全員でデバッグをするのが良いでしょう。これで結構バグが取れます。運よく通ったり運悪く通らなかったりしてコンテストが終わります。
もし通ったらおやつを食べに行きます。

一人が詰まっても他がカバーできるので、問題の配分を間違えなければ大崩れすることは少ないです。逆に、配分を間違えると大変なことになりうるので積極的に人に投げつけていきましょう。

  • どうやって練習するべきか

WF でメダルを目指すとなると日本国内ではどうしてもレベルが足りないため、現状海外に出るしかありません。
twitter を見ると RedCoder たちがたまに集団で旅行していることがあると思います。これはりんごさん主催の合宿で、ロシア合宿などからとってきた 5 時間セットをやりがてら旅行をします。
ロシア合宿の問題は基本的に非公開なので、現地に行くかこういうのに参加するしかなさそうです(ただしかなりレベルが高いので、最低でも AtCoder 橙、できれば赤はないと厳しい)。
あと、Open Cup というのがあって、これもりんごさんが日本 admin をしているのでアカウントをもらって参加することができます。
これは日曜日に開催される ICPC 形式のコンテストで、何人かのチームから毎回 3 人までを選んで出ることができます。ただ、集まって出ると帰宅がかなり遅くなる(コンテストは 17:00-22:00)のと、そもそもロシア合宿で使って非公開にしておいたセットを使ったりするので、あまり出ませんでした。

というわけで、ロシア合宿の紹介をします。年に何度か各地で合宿をしていて、だいたい 1 週間強の期間で毎日 1 セット(休憩日はある)をやります(年中こんなのに参加してるんだからロシア人はそりゃ強いに決まっている)。

Petrozavodsk Camp: 夏と冬の二回がある。夏に 1 回参加した。9 セット行う。一番シンプルで、コンテストと解説以外ほぼ何もない。北緯 62 度なので夏でもそこそこ寒いし、冬はお察し。
MIPT Camp: World Final の前にモスクワで行われる。おそらくもっともレベルが高い。メダルを取る 12 チームの内 8 チームがいたりする。
Hello Barcelona Bootcamp: スペインのバルセロナで行われる。強いチームが少なくてレベルが低めではあるが、問題のレベルはちゃんとしている。
インドで行われたこともある。講義とかがちゃんとあるタイプの合宿。東大にいると謎の伝手で参加費が無料になることがある。ありがとうございます。
中国: どうやら中国人が集まる合宿もあるらしいが、詳しいことはよくわからない。
その他: あまり詳しくないがベラルーシでやったりもしているらしい。多分年ごとに変わってくる。この 7 月にウラジオストクで開催されるらしく、近いので参加してみては。

「数え上げテクニック集」を公開しました

この記事は、「『競プロ!!』 競技プログラミング Advent Calendar 2017」の 20 日目の記事として書かれました。

「数え上げテクニック集」を pdf として公開しました。最近の数え上げの問題を解くテクニックを体系的にまとめた資料です。想定している対象読者層は青〜赤下位程度のレーティングの方です。

AGC 012F Prefix Median

解説に少し頼りました。

  • 問題概要

http://agc012.contest.atcoder.jp/tasks/agc012_f

  • 思考の道筋

ある操作で作りうる列を数えるときは、同じ列ができる操作列の同値類から代表元を一個取ってきてそれを数える(できた列に対して、何らかのgreedyで操作列を一個対応付けることにするとうまくいくことが多い)のが常套手段。今回も、prefix medianでできる列を一個固定して、それを生成する操作列を考えることにする。まずは与えられた集合の要素がすべて異なる場合を考える。

できた列を前から見ていって、新しいものが出てきたら、それはそのステップで追加されたことにしてよいことが分かる。また、それ以外のものについて、課される条件は「端から距離x以内にある」とかだけなので、実は端から埋めていけばいいことが分かる。

次にこれを数えることを考える。前から見ると区間の情報とかをいちいち持っておかないといけなくて無理そうなので、後ろから見る。後ろから見ると、ソート列の要素を消していく問題になる。列の要素は、「前から見て初出かどうか」で分類できる。

後ろから見ていき、中央値を移動させたとする。移動前のやつが「前から見て初出」だったら、これはそれ以降(本来の時系列では、それ以前)には存在しない。ということで単に消してOK。結局、「まだ残っている、既に中央値として使われたもの」の列を持っておけば、この列を一気に2つ以上中央値が移動することはない。さらに、この列の内部にいるなら、この列の要素以外のものに中央値が移動することもない。中央値を移動させるときに右または左の要素を一緒に消すが、これは消した個数だけ持っておけばOK。

以上に気を付けると、以下のDPが書ける。

DP[n][l][c][r][d][s][t]: n回操作して、中央値として出てきたまだ消されていないものがc個あり、それより左の要素がl個、右の要素がr個残っており、まだ消えていない中央値たちの中で今いる場所が左からd番目であり、中央値として使った一番左がs、一番右がtであるときの、中央値の列としてありうるものの個数

ここで与えられた集合に重複がある場合を考えるのだが、作った列で同じものが連続する場合、新たに加えたものを適切に今見ているところの前または後ろに置くことにすれば、結局中央値が移動しない場合に含められることが分かる。よって、この枠組みで問題なく扱える。

これでO(N^7)となる。遷移を書き下してぐっと睨むと、l+c+rが一回の遷移で2ずつ、l+dが1ずつ小さくなっていくことが分かる。この依存関係で状態が削れて、O(N^5)となる。(l+c+rについては遷移の考え方を見るとそれはそう、l+dについては解説見るまで気付かなかったが、これが見えないと本解みたいなエスパーをしないと厳しくなると思う)

さて、中央値として(後ろから見て)新しいものが出てくるときはd=1もしくはd=cだが、この関係を上の式に突っ込んでみるとl=r=N-n(これ重要)という式が出てくる。ということは、後ろから見て新しいものが出てくるとき、その新しいものとして置けるものは真ん中から距離N-n以下のもの、ということになる。

さて、かなり強めの性質が分かったところで、このDPは(これ以上状態を削れないが)かなり冗長なことをしているように見えてくるので、この方針を捨てる。落ち着いて言い換えなおすと、解説に書いてある条件が出てくる。これをうまいことDPすればよいのだが、「前から見て初出かどうかで消すかどうか決める」みたいなことをしているとどうしても[n][c][d][s][t]あたりを全部持っておかないといけなくなってダメそうなので、中央値を消すタイミングを「その順番を飛ばしたとき」にすることにする。そうすると遷移は重くなるのだが、これまで[c][d][s][t]と持っていたものが、「[N-n,N+n]の中でまだ消えていないものに対する、今の場所の相対位置」みたいなものだけ持っておけばいいことになるので状態数が削れて、O(N^4)となる。

  • なにか

以上のような思考をすれば、エスパー力がなくても一応常人に思いつきうる解法になる(まあ出来なかったんだけど)。でも一本道にこの思考を辿ってもかなり大変だからコンテスト中にこういう愚直な考察を1ステップずつ積み重ねて通すのは無理だろうなぁ。

今回の場合、結局列が作れる必要十分条件が一番自然な十分条件と一緒になるので、それっぽい十分条件が見えたら地道な考察を始めるより前にそれが必要条件であることを示しに行く方がいいんだと思う。証明自体は別に難しくないので。

  • コード
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
ll mod = 1000000007;
ll dp[52][101][101];
int main()
{
	int num;
	scanf("%d", &num);
	vector<int>v;
	for (int i = 0; i < num + num - 1; i++)
	{
		int z;
		scanf("%d", &z);
		v.push_back(z);
	}
	sort(v.begin(), v.end());
	dp[1][1][0] = 1;
	for (int i = 1; i < num; i++)
	{
		int a1 = int(v[num - 1 - i] != v[num - i]), a2 = int(v[num - 1 + i] != v[num - 2 + i]);
		for (int j = 1; j <= i + i - 1; j++)
		{
			for (int k = 0; k < j; k++)
			{
				for (int l = 0; l < k + a1; l++)
				{
					dp[i + 1][j + a1 + a2 - (k + a1 - l - 1)][l] += dp[i][j][k];
					dp[i + 1][j + a1 + a2 - (k + a1 - l - 1)][l] %= mod;
				}
				dp[i + 1][j + a1 + a2][k + a1] += dp[i][j][k];
				dp[i + 1][j + a1 + a2][k + a1] %= mod;
				for (int l = k + a1 + 1; l < j + a1 + a2; l++)
				{
					dp[i + 1][j + a1 + a2 - (l - 1 - k - a1)][k + a1 + 1] += dp[i][j][k];
					dp[i + 1][j + a1 + a2 - (l - 1 - k - a1)][k + a1 + 1] %= mod;
				}
			}
		}
	}
	ll ans = 0;
	for (int i = 0; i <= num + num - 1; i++)
	{
		for (int j = 0; j < i; j++)
		{
			ans = (ans + dp[num][i][j]) % mod;
		}
	}
	printf("%lld\n", ans);
}

「心ある正論」について

twitterで「たとえ頭が良くても、相手の気持ちを汲み取らず、正論を振りかざして相手を傷つけるのは許されない」という主張を見たので思ったことを述べる。


まず、主張自体はよくあるものであり、我々がよくやるように「ただの僻み根性」として一笑に付してしまっても一向に構わないわけであるが、やはり思うところがあったのでここに書き記そうと思う。


ます、我々が正論で相手を傷つけるとき、果たして我々は相手の気持ちを汲み取っていないのだろうか。むしろ、相手の気持ちが手に取るようによくわかるからこそ、相手の弱点に的確に突き刺さる一言を発せるのではないか。我々は相手の気持ちを正確に汲み取った上で、あえてそこに一番適した武器を持って、相手を征するはずだ。勿論、いわゆる「心ないハラスメント」の類は完全な独りよがりであるし、その行動のファクターとして相手の気持ちなど存在しないのだが、それはそもそも正論ではないわけで、僕はそういう話をしているのではないのである。


そして、我々は知的好奇心からか、または曖昧なものを嫌う心からか、常に自分の心に残るわだかまりに対して目を向けようとしている。自分の心の弱点を把握し、自らそこに銛を打ち込んでいくことは、我々自身が最も望むことだ。我々は本質的な苦痛をたえず求め続け、そして苦痛の正体が曖昧な状態こそが最も苦しい状態である。我々はかりそめの苦しみから脱するために苦しみに目を向け、新たな、より根源的な苦痛を手に入れようと努力する。苦痛の発展の終着点など信じないし、苦痛の先にあるのは新たな苦痛だけであることも知っている。最早苦しみは自らを再生し、高め、自らの在り方の最高峰を求める手段などではなく、苦しみこそが目標であり、苦しみこそが幸福である。そして、その苦痛を手にするために手段を選ぶ理由はない。苦痛を自らの手で得たという事実には、何の価値もない。


「苦しいかどうか」と「その状態を求めるかどうか」は、分けて考えられなければならない。相手の気持ちが汲めるからこそ、相手の苦痛への鍵のありかが分かる。苦痛の発展を求めるものとしての考え抜かれた良心と、同じ苦痛に共に潜る者を求める孤独があれば、その苦痛を共有することへの躊躇はなくなるだろう。我々は相手の気持ちを汲むからこそ、的確な正論で相手の心に銛を打ち込み、そして銛を打たれることは本望だ。傷つけられた相手は、「苦しみをありがとう」と、こう叫ばなければならない。


錯綜しているのはわかっている。理性的でないのも分かっている。苦しみを避けたくないのなら、それは最早苦しみではないのだろう。しかし僕は、これを喜びと表現しようとは思わない。そして、苦しみが連鎖するその状況こそが、自らを顧みるということができる存在の本来の姿である、とすら思っている。


さて、僕に対する反論としての正論はおそらく、以下のようになるだろう。すなわち、苦しみを求めるのはお前だけで、苦しみを求めることのない多くの人にまで、苦しみを強要することはないだろう、と。これに対する答えを、僕はまだ出せずにいる。苦しみを求めない人間は、果たしてどれほどの割合で存在するのだろうか？　相手の気持ちを汲む、ということには、単に相手の立場に自分を置いてみること以上のことが求められているのだろうか？　だとすれば、相手への無関心の極み、いわゆるパターンマッチこそが、人間関係において最も求められていることなのだろうか？


なにはともあれ、この文章は単に現在の僕を書き記したに過ぎない。価値観は常に変遷するものであり、自己はどこまでも相対化できるものである。しかしそんなことを言ってしまってはキリがないので、主張がある程度の具体性を保っている今のうちに、筆をおいておくことにする。

分割数のDPをO(Nsqrt(N))でやる

Petrozavodsk campの北朝鮮セットであった問題で知見を得たので書き記しておきます。

  • 問題

分割数の N 番目を求めよ。

  • 解法

まず、DP[N][K]: K個の和でNを作る場合の数 とする。
1を使う場合と使わない場合に分けると、DP[N][K]=DP[N-1][K-1]+DP[N-K][K] がわかる。このままやると O(N^2) となる。

B=floor(sqrt(N))として、K < B に対して、この DP を愚直に計算する。

K>=B に対しては、x[s][t]: B<=xに対する DP[s-tx][x] たちの和 とする。下の図の青線や緑線一本一本の和を、始点と傾きを変えながら全部求めると思えばよい。x[N][0] がわかれば OK 。

このとき、t (すなわち傾き) は、sqrt(N) までしか考えなくてよい。これは、傾きがそれ以上大きいとき、直線は前計算した赤い領域以外の DP 値が 0 でない点を通らないためである。

さて、x[s][t] に対して先ほどの DP の漸化式を項ごとに適用すれば、x[s][t]=(x[s-1-t][t]+DP[s-1][B-1])+x[s-B][t+1] となる。括弧内の項は、DP[N-1][K-1] から DP[N][K] への遷移に対応し、今和を取っている直線を左斜め上 45 度にそのまま移動したものからの遷移を表す。K < B なる領域に踏み込んでいるので、その分は前計算された DP[s-1][B-1] を足しておく。第二項は、DP[N-K][K] から DP[N][K] への遷移に対応し、直線の傾きが 1 だけ増える。

DP[N][K] を K < B に対して前計算しておけば、x[s][t] も全部合わせて O(Nsqrt(N)) で更新できるので、全部合わせて O(Nsqrt(N)) で分割数が計算できたことになる。