セキュリティキャンプ フォーラムに行ってきた。強い人と話せてよかった。名刺を貰いまくったので次は名刺を作っていきたい。

登大遊さん初めて間近で見れてよかったー。

---

ABC293に参加した。

A: なんかよくわからないが愚直に実装した

B: すでに呼ばれた人をsetで管理した、bool値配列で良かったかもしれない

C: 「全ての移動について移動前後のマスの値が異なる場合」と誤読した。誤読に気づいた後でAiの値が10^9なことに絶望したが、全ての移動経路を全探索しても間に合うことにすぐに気づいてACした。危ない危ない。

D: UnionFindで閉路検出するだけ。同じ場所を2回結ぶようないじわるはしないので助かった。

E: 本日の大負け問題。すぐさまパターンマッチでA^X-1/A-1にしてしまったがこれは罠で、A-1とMが互いに素だとどうにもならない。1WAした後で「多分なんか工夫すれば行けるんだろ」とぼんやり考えていたが、そんな方法は本当に一切存在しない。正解は2分再帰で$f(A,X,M)=f(A,X/2,M)+A^{X/2}f(A,X/2,M)$の形にすること。割り算を諦めたら割とすぐに思いつけた。

べき級数への式変形が意味をなさないことを把握していればすぐにその方針を断てた。完全な勉強不足だ。非常に悔しい。

ちなみにmod M(A-1)で考えるとかいう方法もあるらしい。膝を打った。128ビットの多倍長整数演算が必要という問題はあるが。そして想定解は行列累乗らしい。ええ…

F: 残り6分では解けず。下一桁が0or1であることを考えるとbはNの約数かN-1の約数であることが分かる。gcd(N, N-1)=1なので被りはない。しかしNの約数全列挙は$O(\sqrt{N})$なので遅すぎる。何かもう一段速くする必要がある。

G: ある区間の中にある同じ数字の数が分かれば、その数字についての3つ組の数は$_xC_2$と分かるのだが、数字の種類数は大量にあるので各クエリについて全種類を計算していては話にならない。ちょっと考えると、ある区間について答えが分かっていれば、そこから伸び縮みした区間については伸び縮みした部分に含まれる数字による差だけ考えればすぐに求められる。これはMo’s algorithmの典型だ。

ある数字の個数がCからC+1になったとき、$+(C+1)(C)(C-1)-C(C-1)(C-2)=3C(C-1)$の差が発生する。これで区間の伸び縮みができる。あとはやるだけ。

すぐにMo’sに至れたのはよかったが、単なるオーバーフローとコーナーケースによる計算処理ミスで2WAしてしまった。もったいない。とりあえずあまり使い慣れていないMo’s algorithmを本番で思いついて通せたのは良かったと思う。しかし650人が解いてるのは恐ろしいな。