近況報告

最近競プロを再開した。
とりあえずAtCoderの過去問をひたすら解いているのだけど、以前よりも沢山の問題が解けるようになっている気がする。
ここ数年間はあまり脳を働かせていなかったので衰えているかと思ったけど、そうでもないみたいだ。

といっても、1日かけても解けない問題もちらほらあり、昨日は双対セグ木の考え方を用いた方法が想定解である問題を解こうとして、解けなかった。
この問題から学んだことをどうしても書き残したいと思い、今回の記事を書いている。

というのも、双対セグ木、もう少し抽象化した完全二分木は、頂点数が O(N) である。
そして、そのうち半分の頂点は区間の情報を持つ。
範囲に対する更新操作を行ったとき、その操作の大半は各要素ではなく区間に対して行われるため、これにより保有している情報が変更される頂点の数は高々 logN 個程度である。

これは、たとえば各頂点がmultisetを持ち、範囲 [0, N) に対して A←max{A, x} という操作を Q 回行ったとしても、空間計算量が O(QlogN) 程度に収まるということである。
一度の更新操作ですべての頂点のmultisetが更新されることはない。

よって、multisetなどの「操作回数に応じてメモリ使用量が増えるようなデータ構造」を各頂点に持たせても問題はない。

問題を解いているときはこの事実に気付かなかった（「頂点にmultisetやpriority_queueを持たせるのは良くない」と思い込んでいた）。
この気付きは自分にとって大きいものだったので今回は書き残した。

広告を消すための記事

90日以上記事を投稿していないと広告が表示されるため、とりあえず記事を投稿する。

11月末に今の会社を辞める。その後の予定は未定。
フリーランスになりたい気もするし、別の会社に正社員として就職するかもしれないし、農業をするかもしれない。
就職するなら Rust を触れるところがいいな。

とりあえず、少なくとも半年はニートでいたいので、その間は仕事のことは全く考えず、貯金を切り崩す生活をする。

この貴重な空白期間に、今までする余裕のなかったゲーム作りなどをしたい。
ゲームじゃなくて、有用なソフトウェアとかでもいい。
息抜きにボランティアをしてもいいかも。

近くに市民プールがあるので、運動不足を感じたらそこに行こうと思う。
今月だけで4回ほど行っているのだけど、僕の泳ぐスピードが遅く、気軽に利用できるのは何でもOKのレーンのみ。
平泳ぎが一番泳ぎやすいんだけど、顔を水に沈めたときに吐きそうになる。いつか治って欲しい。
ずっと顔を出した状態で泳いでいれば吐きそうにはならないけれど、常に背筋を伸ばした状態なので疲れやすく、顔を沈めるのに比べて泳ぎが遅くなる。

顔を水に沈めても吐きそうにならない、何かいい方法はないだろうか…。
というのが最近の悩み。

今は Unreal Engine のインストールが終わり、Unreal Editor を起動している最中。シェーダのコンパイルに時間がかかっているようだ。
起動が完了した後は、とりあえず以下のチュートリアルを進めていこうと思っている。

docs.unrealengine.com

2021年10月26日 日記

今日は733円、体重は84.6kg、問題数は11だった。
典型90の問題を解き進めている。

計算量が O(N²) かかると思い込んでいたら、エラトステネスと似た理屈で O(NlogN) （×コンビネーションの計算量）に抑えられることに3時間くらい気付けなかった。

2021年10月13日 日記

今日は1,071円、体重は84.8kg、問題数は2問だった。
2問のうちの1問は Make Pair だった。
Make Pair の想定解の計算量は O(N³) だけれど、僕は O(N⁴) で解いてしまった。
O(N³) の解法もしっかりと理解しておきたいところ。

2021年10月12日 日記

今日は1,100円、体重は84.8kg、問題数は1問だった。

ABC222 の G を解いた。まさか x^y≡1(mod K) の形にするなんて思いもしなかった。T <= 200 という制約を利用して前計算量 O(K) クエリ計算量 O(1) で求めるとか、ダブリングを利用すれば良さそうとか、グラフの遷移に言い換えればできるかもとか色々考えたけれど、そのどれもが間違いだった。

この問題を解くためには、x^y≡1(mod K) の他にも、基本的な mod 上の式変形の方法、オイラーの定理やオイラー関数、位数はオイラー関数の結果の約数であることなど、様々な知識が求められる。結構大変。

以下は二項係数を求めるコード。すぐに使える場所に残しておきたい。

binom[0][0] = 1;
for (int i = 1; i <= N; i++) {
  binom[i][0] = 1;
  binom[i][i] = 1;
  for (int j = 0; j < i - 1; j++) {
    binom[i][j + 1] = binom[i - 1][j] + binom[i - 1][j + 1];
  }
}

2021年10月11日 日記

今日は1,000円、体重は85.5kg、問題数は0問だった。
ABC222 の G を解くためには mod 上で正しく除算を行う必要がありそうなので、mod の勉強をしている。
もし想定解が mod 上の除算でなくても、周辺知識を得たことになるので良しとする。

2021年10月10日 日記

今日の食費は181円、体重は84.8kg、解いた問題数は6問だった。
ABC222 の A〜F を解いた。

C を解いているときはあまり頭が働いておらず、勝ち数の降順でソートしないといけないのに昇順でソートしてしまった。
そのバグに気付くのに2分ほど費やしたと思う。
気付いた後もソートの仕方に少し悩んでしまった。sort 関数の第三引数に関数を渡すだけでいいのに。

D は比較的すんなりと解けた。
遷移が多いので累積和を使って計算量を落とす。

E は考察を進めると部分和問題になるのだけど、その前に木のパスを100回ほど通る必要があり、普通に DFS すればいいものの LCA を使ってしまった。
普通の DFS で済む場合はそうしたいところ。
あと、メモリ使用量が800MBだったので危なかった。
もし ACL の modint が内部で long long でデータを保持していれば MLE になっていた。

F は全方位木 DP を知っていると比較的簡単に解けた。
E は29分かかったのに対して F は24分で解けた。
持ち上げの際に頂点番号が必要だったので、既存のライブラリを少し修正する必要があり、そこに時間がかかってしまった。

G はまだ解けていないけれど、もしかすると普通に解けば間に合うのかも…と思い始めた。どうなんだろう。