naoya_t@hatenablog

いわゆるチラシノウラであります

ABC A/B問題のWA原因リスト

水曜深夜の比屋定先輩タイムまですこし時間を持て余したので、ABCの不出場回のA/B問題*1を埋めていった。

  • 使用言語: Python2 (2.7.6)*2
  • エディタ: 問題ページのフォームに直接書き込み*3

これで現行のスコア体系になってからの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

続きを読む

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:動かすには何箇所か修正が必要

続きを読む

Kindle Oasis(第9世代)を買った話

我が家にKindle Oasis(第9世代)がやってきました。

TopCoder Algoのレーティングが黄色に復帰した後に届いたので黄色復帰祝っぽくなりましたが、ぽちった時点ではそういうイベントが来るのは予期していませんでした。
f:id:n4_t:20180603140544j:plain:w400
f:id:n4_t:20180603140827j:plain:w400
f:id:n4_t:20180603140932j:plain:w400

続きを読む

例題で学ぶ微分方程式: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以下の整数)が与えられてx^yy^xの大小を比べるだけの問題。

y\log xx\log y の比較に置き換えれば簡単なはずなんだけど、ローカルでは何の問題もないのにサーバ上ではあたかも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;
}
続きを読む