StripeObject について

最近お仕事で決済サービスの Stripe を使っているので色々メモする。
溜まったらまとめて Qiita に記事にするかな。

Ruby で Stripe の API を叩くと StripeObject が返ってくる。StripeObject のドキュメントは
http://www.rubydoc.info/github/stripe/stripe-ruby/Stripe/StripeObject ここにあって、内部に Set を持っていて key value を管理している様子。
この StripeObject は Hash っぽいけど Hash じゃないので稀にハマる。
以下の点が気になる

続きを読む

trigraph

2014 TCO Algorithm Round 2B で トライグラフ (trigraph) に軽くハマった。以前にもハマったことがあるので、早めに気づいて致命傷にはならずにすんだけど、スコアをいくらか落としてしまったので対応策をまとめた。

trigraph とは

一部の記号が無いキーボードでも C のプログラムが書けるように、ISO 646 で規定されたより一般的な 3 文字を使って表記する方法。プリプロセッサによって変換される。
トライグラフ - Wikipedia
英語版 wikipedia には 2 文字表記の digraph についても説明がある
Digraphs and trigraphs - Wikipedia

このため、次のようなソースコードは大部分の人の意図と異なる出力となる

#include <iostream>
using namespace std;
 
int main() {
	std::cout << "??-" << std::endl;
	return 0;
}

出力は

~

の一文字になってしまっている。 C++11での実行結果
外部ファイルを読み込んだ場合は変換されないので、プログラミングコンテスト系ではソースコードに直接テストケースを記述する topcoder ぐらいでしか発生しない問題かも。

コンパイルオプション

ここで、先ほどのコードのコンパイラを変えてみる。先ほどは C++11 でコンパイルしたが、今度は C++4.8.1 でコンパイル、実行してみる。
C++4.8.1での実行結果

今度は変換されずに出力されている。まだ調べきれていないけど、C++11 ではデフォルトで trigraph を変換するようだ。なので、今回 Topcoder でハマった人はだいたい g++ でコンパイルして、オプションに次の指定をしていたと思われる

g++ -std=c++11 ...

この場合は次のような警告が出ていたはずだ。以下の警告は (GCC) 4.9.0 で試した結果。

SwitchingGame.cpp:111:4: warning: trigraph ??- converted to ~ [-Wtrigraphs]
  "-??-?+"}

trigraph ??- が変換されたことがわかる。ソースコードC++11 の機能を使っていないのであれば、 -std=c++11 を外すと、次のような警告になる。

SwitchingGame.cpp:111:4: warning: trigraph ??- ignored, use -trigraphs to enable [-Wtrigraphs]
  "-??-?+"}

trigraph は無視されたので、変換したいなら -trigraphs をつけてと言われる。こっちのほうが望ましい挙動なんだけど…

トライグラフを有効にするオプションがあるなら、無効にするオプションがあるのではないかとも思うけど、どうも見つからない(´・ω・`)。ちなみに、-Wno-trigraphs とすると警告を無効にできる。でも -no-trigraphs オプションは存在しない。何故。

解決策

2 番目がおすすめ?

1. トライグラフを書かないようにする

"??-" となっていたら、"\?\?-" と、? にバックスラッシュを追加すればトライグラフにならない。"??""-" と分割して書いてもよい。ソースコードを適当に置換すればよい。 https://ideone.com/yqQfbq

2. コンパイルオプションを -std=gnu++11 にする

twitter 見てたらわかった方法

コンパイルオプションを gnu++11 にすることで、gnu の独自拡張が適用されてトライグラフがデフォルトで無効になる。独自拡張に関しては、stackoverflow とか C++ Extensions - Using the GNU Compiler Collection (GCC) ここを参考に。

まとめ

これから -std=gnu++11 にしよう… 他の言語でも似たような問題を作れるんでしょうか。Java だとユニコードを利用してできるのかな?

Code Jam Tasting 作った。あと、Qiita 使ってみた。

しばらくプロコンから離れていたけど、最近またぼちぼちやっている。楽しい。で、Google Code Jam の過去問を練習するときに、人のソースコードを見るのがたるいので、楽にする Extension を作った。

Code Jam Tasting - Chrome ウェブストア

作ったあとで気がついたけど、Google Code Jam の解法をページ内に表示する bookmarklet - miauの避難所 これとほとんど同じ。ただ、セキュリティの問題で今は Chrome で動かないらしいので、これの Chrome 版かも。さすがにブックマークレットではない分、少し機能は多い。

主な機能

スクショは Chrome Store のページを見てください。私も当然使っていますが、コンテスト中に悪影響が出たことはないです。

説明とか

コードは GitHub - ororog/CodeJamTasting: Chrome extenstion for adding preview link to scoreboard of Google Code Jam. にあります。実装上のすこし面白い点は、JS ので zip のダウンロード、解凍と、chrome extension でのクリップボードのコントロールです。

JS での zip の扱いは、候補はいくつか有るのだけどどれも上手く動かせなくて苦労した… 最終的には jszip を使った。

クリップボードに関しては Qiita で初記事書いてみた Chrome Extension で content_scripts から clipboard を使う - Qiita

既知の問題

  • zip 内に複数のファイルが入っていたり、ソース以外が入っていると正しく表示されない

対応がめんどい…

  • レイアウトが少し崩れる

Qiita 使った感想

技術的なことを Qiita でまとめて書いておくのはいいかもって思うけど、ブログとの住み分けどうしよう。個人の感想とかはこっちにするか。久しぶりにはてなでブログ書いてはてな記法なんで完全に忘れてたけど、Qiita も記法があって、誰か統一してくれと思わないでもない。
Qiita で書いたほうが読者は多いと思うので、技術的なことは積極的に向こうに書いたほうがよさそう。あまりまとまっていない内容をこっちに書く感じ。

ICPC2010 Jakarta Site 海外派遣のはなし

2010年のICPC東京大会も終わりまして,タイミング的には東京大会の報告なんでしょうけど,その前に海外派遣のお話を.
優秀な次の世代の皆さんは,これからどんどん海外の大会に出られると思います.そこで,今回ジャカルタに行くにあたって経験したことを残しておこうと思います.海外に出られる方は参考にしていただけると幸いです.

続きを読む

アジア地区予選過去問

最近海外のアジア地区予選過去問をチーム練習しています.
ここで練習しています.
http://acm.uva.es/archive/nuevoportal/
MLEが32MBだったり,TLEが書いてなかったり(問題によっては10秒だったり60秒以上あったり),コンパイラはしょぼかったり,恐らく実行環境は貧弱だったり,
いろいろ難しいところもあるのですが,ここにしかない過去問も多いです.

Jakarta 2008

http://acm.uva.es/archive/nuevoportal/region.php?r=as7&year=2008
6問まで超絶簡単.6問終わった時点で半分以上残ってた.それから全く解けないwww
2問TLEとMLEで死んだ.本番環境なら通ればいいけど,たぶんそんな甘くない.

解いた問題: A B E G I J
TLE: F
MLE: C
予想順位: 5 - 14 (多分上の方)

Danang 2007

http://acm.uva.es/archive/nuevoportal/region.php?r=as12&year=2007
条件足らずな問題文が多い…Clarはどこですか?問題文も読みにくいし.
仕方ないのである条件だとTLEしたりするコードを投げて擬似Clar
またMLEに悩まされたりした.あと,簡単目なもんだいを最後まで放置していたみたい.
他のチームの解答状況がわからない大会もあるので,問題は全て目を通さないと.

解いた問題: A B C
MLE: D
予想順位: 9 - 18

Jakarta 2009

http://acm.uva.es/archive/nuevoportal/region.php?r=as7&year=2009
もともと2009年のジャカルタの過去問はlive archiveになかったんだけど,ジャカルタの大会委員会にメール
ジャッジデータないですか?って問い合わせたら追加してくれた!凄い!
こういうふうにメールだしてみたりするのもすごい大事ですね.
化学表記で少数何桁出力せよって問題があって(2.3E-8みたいな),多めに桁出して切っていて最後までWAだった.
小数点をちゃんと四捨五入しなきゃいけなかったらしい."化学表記"って言われて気づけなかった.
あと,printfは結構便利機能が多い.化学表記もできる.
しかし,文字列を検索したりする問題多いなぁ.suffix arrayよくわかってない…

解いた問題: A C D E G J
WAで終わってしまった問題: F
予想順位: 6 - 7
化学表記は正解したかった…残りは分からん.

Phuket 2009

http://acm.uva.es/archive/nuevoportal/region.php?r=as12&year=2009
Watchの参加した大会.Watchには勝つぞーと始めたが,結局Watchと同じ数といて終了.
六角形を,やるだけだと思ったがバグがとりきれなかった.無念.六角形になれないと.
他のチームが解いている問題は,とけそうと思いつつ解けなかった.無念.

解いた問題: B C E J
TLE: D
WA: G
予想順位: Watchと同じくらい?
Dは手元で1分ほどで終わったらしい.本番はどのくらい時間あったんだろう.

まとめ

簡単目の問題はとけてますが,あと一問足りないです.傾向は別につかめませんが,幾何はあまり見ないです.
文字列が意外とでるので,備えあればいいかなぁ…

なんだか自信がなくなってきましたが,頑張って練習します.

ポラード・ロー素因数分解法(Pollard's rho algorithm) PKU 2447とか.

以下は嘘吐いてる可能性が結構あるので気をつけて!!

ρ法は篩などでは見つけられない大きさの素因数を見つけるアルゴリズム

理論的なことは完全に理解していないので僕が説明するよりwikipedia:ポラード・ロー素因数分解法とかhttp://matsumoto-lab.hp.infoseek.co.jp/chapter02/algo02.htmlとかhttp://idm.s9.xrea.com/factorization/rho.htmlをよんだほうがいいです(´・ω・`)むずい.

ρ法のオーダーは,見つける素因数をpとするとsqrt(p)で50%程度らしい.

また実装の注意点として

  • long longの掛け算はオーバーフローする.
    • 掛け算を足し算で実装する.
  • 確率的なものなので,見つからないこともある.
    • Miller-Rabin Testなどで素数でないことを確認した上でρ法を行う.
    • f(x) = x^2 + cのcの値を変えて繰り返し試行.
  • 帰ってきた結果は素数とは限らない.
    • 予め試し割り(篩など)で小さな素数を取り除いておくとよい.

実装は次の通り

typdef long long Int;
// a * b % mを返す.
Int multMod(Int a,Int b,Int m){
  Int res = 0;
  a %= m;
  while (b){
    if (b & 1){
      res = (res + a) % m;
    }
    a = (a * 2) % m;
    b = b / 2;
  }
  return res;
}

// cははじめ1を入れる.
// numが素数の場合無限ループしてしまう.判定もするなら適度なcで打ち切る.*/
Int PollardRho(Int num,Int c){
  Int x,y,p;
  x = y = p = 1LL;
  while (p == 1){
    x = (multMod(x,x,num) + c) % num;
    Int ty = (multMod(y,y,num) + c) % num;
    y = (multMod(ty,ty,num) + c) % num;
    if (x == y) return PollardRho(num,c+1);
    p = gcd(num,llabs(x-y));
  }
  return p;
}

1811 Prime Testや2447 RSAで確認.実際にはcの値が1の時点で答えは見つかっているようだ.1811では2^16以下の数で篩を作りためし割りした.

また,Brentの改良を入れると次のようになる.

// Brentの改良
Int PollardRho(Int num,Int c){
  Int x,y,p;
  x = p = 1LL;
  int next = 2,i=1;
  while (p == 1){
    ++i;
    if (i == next){
      y = x;
      next *= 2;
    }
    x = (multMod(x,x,num) + c) % num;
    if (y == x) return PollardRho(num,c+1);
    p = gcd(num,llabs(x-y));
  }
  return p;
}

2447では速度上がらなかった.しょんぼり.

今回間違い多そうなので指摘してくだしあ.