ABC A/B問題のWA原因リスト
水曜深夜の比屋定先輩タイムまですこし時間を持て余したので、ABCの不出場回のA/B問題*1を埋めていった。
これで現行のスコア体系になってからのABCはD問題1つ*4を残して全部埋まったので、明日からARCのE問題以降に取り組める(取り組まざるを得ない)。
解いた問題の解法の詳細はここには書かないが、代わりにWAやREを出した問題で何故WAを出したのかを列挙してみる。
AtCoder ProblemsのSubmissions一覧からWAを出した物のdetailsを見て、提出コードだけから(問題は見ずに)WAの原因を思い出していった。結構覚えているものだ。
*1:AtCoder Scoresに載っているもののみ、現行のスコア体系になる以前の回は対象外。で97問残ってた
*2:いまだにpython3より2の方が書き慣れている
*3:サンプルケースでのテストはほとんどしていない
*4:ABC050 D - Xor Sum
MathMash Round 19
6/11 2:25-4:25am JST
https://www.mathmash.org/contest.php?id=19
ABCの後に寝落ちして、ちょうど目が覚めたところでTLで目に飛び込んできたので(急遽アカウントを作って)出てみた
7完 (ABCDEF-H) 9816点で8位
↑EとHはズルしてる
1248(+248)
DFT(離散フーリエ変換)とNTT(数論変換:整数(剰余環)を用いたDFT)
先日ARC埋めの一環でATC001のC問題(高速フーリエ変換)を解いたのだけれど、こういう畳み込み問題はDFT(discrete Fourier transform;離散フーリエ変換)の代わりに NTT(number-theoretical transform;数論変換)という "整数(剰余環)を用いたDFT" でも解けるらしい。
そこで、math314氏の「 任意modでの畳み込み演算をO(n log(n))で - math314のブログ」の解説と実装例*1を追いながら自分で実装して試してみた。こないだcomplex<double>
で自分で書いてみたやつ(→ATC001)とほぼ同じことをしているように見える。これは面白い。
(ここでは解説はしないので、詳しくはmath314氏の元記事を参照して頂ければと思います)
*1:動かすには何箇所か修正が必要
例題で学ぶ微分方程式:1.1 常微分方程式と相図
なんとなく「時代は微分方程式だよなあ」と思って先日オライリーの「例題で学ぶ微分方程式」を買いました。
www.oreilly.co.jp
本書ではMathematicaでプログラムが書かれているので、これをPythonでというかJupyter notebook (scipy+matplotlib) で置き換えながら読み進めようと思います。
というか、jupyter notebookをgist経由でブログに埋め込むテストです。
続きを読む6log6≠6log6
先日のこどふぉ#484のB問題(agwたんから聞いた)
B. High School: Become Human
xとy(それぞれ1以上10^9以下の整数)が与えられてとの大小を比べるだけの問題。
と の比較に置き換えれば簡単なはずなんだけど、ローカルでは何の問題もないのにサーバ上ではあたかも6log6≠6log6であるかのような振舞いをする。
これは(数学の問題と見せかけて)コンパイラの最適化の地雷をどう避けるかという問題。
// サーバ上だとx=y=6でなぜか落ちる #include <bits/stdc++.h> using namespace std; int main() { int x,y; cin>>x>>y; double lx=log(x)*y, ly=log(y)*x; if (lx == ly) cout << "=" << endl; else if (lx < ly) cout << "<" << endl; else if (lx > ly) cout << ">" << endl; return 0; }続きを読む