Wed Jun 19 2019

      6月 2019         
日 月 火 水 木 金 土  
                   1  
 2  3  4  5  6  7  8  
 9 10 11 12 13 14 15  
16 17 18 19 20 21 22  
23 24 25 26 27 28 29  
30

06/08-06/09

会社の同好会で合宿に行った. わざわざ遠出して一泊してやる意味があるか? などと、つい考えてしまう. けど、そういえば、使いみちの無い会社から支給される会費の使いみちが無くてのイベントだったから、しょうがないのだった. 交通費とかは負担したけどな.

06/15 - diverta 2019 Programming Contest 2

企業コンテストはARC相当であるらしく、私の腕前だと D 問題がギリギリという感じ. でもこれでレーティングが 1571 -> 1636 で水色から青色になれた.

06/16 - ABC130

さすがに昨日の企業コンテストよりは簡単であったが、本当にマグレで全て (A-F) 解けた. 最後の F 問題は本当にマグレで、誤った解法ではあったのに偶然通ってしまった.

F 問題は結局、時刻 \(t \geq 0\) に関する2つの凸関数 \(f(t), g(t)\) があって、これの積の最小値を求めよという問題だと言える. 私は凸同士の積だから凸になると考えた. いや結構怪しいが、この問題に限ってはなるのかも？と考えた. 競技プログラミングに関しては普通のプログラミングとは違って、メタ的な推論も方法の一つだと思っていて、わたしは「言うてABCなんだし、実は凸でした」というオチを期待したわけである. 凸関数の最小値を求めるには三分探索をすればよい.

実際には全然凸ではなくて, \(f(x) = |x|, g(x) = |x-1|\) なんかを考えると次のような関数が現れる.

Gnuplot Produced by GNUPLOT 5.2 patchlevel 6 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 -0.5 0 0.5 1 1.5 abs(x) * abs(x-1) abs(x) * abs(x-1)

ところで最近 modint が流行っている.

競技プログラミングにおいて、よくある典型的な形式がある: あまりにも回答する整数が巨大な場合に、ある数 \(M\) （これは大抵素数であることが多い）で割った数を求めさせることがよくある. そのような場合、あるコンテクストの計算を全て \(\mathbb Z / M \mathbb Z\) という体の上で計算すれば良いことになる（\(M\) が素数じゃないと割り算が自由じゃないので体ではなくなるけど）.

というのが背景で、要するに、普通の整数のように四則演算があって、その度に勝手に \(\bmod\) を適切に取ってくれるような構造体があると便利. それがないと、いちいち手で

a + b + c - d

を

((((a + b) % M) + c) % M + M - d) % M

などと書かないといけない. どこでオーバーフローするか分からないので毎回 % M をする必要があって、括弧がいくらあっても足りないだろう. 特に減算のときは + M をするのがポイントだ. 言語に依る話だけど -1 % 3 が -1 なものもある. そういう場合は (-1 + 3) % 3 で 2 にするのが大抵の場合、期待する値だから.

私は競技プログラミングで Rust を使う人間なので, Rust で実装した:

しかしながらまだ ABC130 の E 問題でしか試してない. この回答では +=, +, - くらいしか動かしてないので、もしかしたらバグがあるかもしれない. っていうか実際 - にバグがあったのを慌てて修正したし.

あと Rust は型安全に忠実すぎて、四則演算の定義だけでこんなに長くなってしまった. 例えば和については

ModInt + ModInt
ModInt + int
int + ModInt
ModInt += ModInt
ModInt += int

といったものを全て実装しないといけない. せめて += は + から自動的に derive する機能が欲しい（無いですよね？）

06/15

Facebook Hacker Cup の予選があった. 予選は一問でも解けさえすれば良いので、やる気があるかどうかのテストである.

その中の3つ目の問題

\(x\) に関する論理式が与えられるので一部を書き換えて, 式全体の値が \(x\) の値に依らないようにせよ、という問題. AND, OR, XOR を含む場合、実はそのトップレベルの演算を適切に別の演算に書き換えれば必ず全体の値は不変に出来る、ということに気づく.

例えば a AND b を考える. x=true,false に対して a b それぞれが a=true,false, b=true,true と取る時 a AND b=true,false と取るので値が x に依存していていけない. しかしこのとき AND を OR に置き換えれば a OR b=true,true と出来て不変. このように a b のバリエーションを全通り書き出して、どれかの演算なら不変に出来ることが分かる.

問題は、書き換えなくても不変かどうかである. Facebook の後からの解説によると、部分を見ればそれは分かるらしい. 例えば

問題の解説を書こうと思ったけど、公式の解説なりもっと強い人のを読めばいいのでやめた.