今日解いた競プロの問題。
競プロ典型90問
057 Flip Flap: F2上のN元1次連立方程式の解がいくつあるかという話なので、線形代数やるだけなのだが、線形代数全部忘れてたので学びなおす羽目になった。
$N\times M$行列$A$,未知の$N$次元ベクトルx、既知の$M$次元ベクトルbがあって、方程式Ax=bがあったとき、rankA=rank(A,b)ならば解あり。rankA<rank(A,b)ならば解なし。また解がある場合の解空間の次元はN-rankAになる。体が$\mathbb{R}$とかだった場合は解が無限個あるという話になるが今回は有限体$\mathbb{F}^2$なので、解は$2^{N-rank A}$個になる。
一応線形代数ライブラリ自体は持っていたのだが、なんかもう動作が分からないので自作しなおした。
081 Friendly Group: 一瞬にぶたんかと思ったのだが、どうもいい感じに出来そうにない。図で考えてみると、どうも二次元平面上の正方形領域の中の点の数を数えたい気がする。制約見たらAi,Bi≦5000なので2乗が通る雑魚だということが分かった。平面全走査して終わり。
082 Counting Numbers: やるだけなのだが、端の処理でちょっとだけバグらせた。文字数ごとに見て行きたいので、打ち切る条件として$10^n \leq k < 10^{n+1}$なら～という条件を書きたいところだが、kが$10^{18}$である場合は$10^{19}$を取り扱うことになってしまう。これは厳しいので場合分けした。Pythonなら楽なのかもしれないが。
mod逆元を学ばせる問題でもあったようだ。modintを使い倒しているので忘れていた。
clangのコンパイルを延々やっている。
昨日の朝から30時間くらいかかってようやく100%に達したが、crtbeginS.oが見つからんみたいなエラーで落ちた。CMakeの設定をやり直したら案の定一からビルドし直しになった。こう、ビルドキャッシュとか多少なり使われんものか。
異常に時間がかかるわけは、どうやらあらゆるアーキテクチャ向けのコンパイル機能を有効にしているからだということに今更気づいた。しかしなんかもう意地で全部コンパイル通してやるぞという気になっている。
ビルドさせている最中はメモリ不足なのかWordPressが動かない。次ビルドに失敗したらさすがにサーバーを別に建てようと思う。
サイト落ちるのに無頓着すぎるのさすがにダメな気がしている。
久方ぶりに腕立てをやった。ちょっと衰えてる気がする。
このところ色々意欲が湧かない。うーん。
なんか社会とか所属サークルに対してこれをやろうみたいなのを自分に課しているのが精神的にはあまり良くない方向に作用している気がする。
好き勝手な二次創作絵とか再開したい。
Categories: 未分類