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では速度上がらなかった.しょんぼり.

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

ICPC2010 国内予選

興奮覚めやらぬうちに参加記を書く.

チームについて

うちのチームはメインコーダー,電波(アルゴリズマー),サブコーダーという役割分担をしている,と思う.
メインコーダーが抜群の安定感で重めの実装をこなす.簡単な問題は僕と電波で解く.
メインコーダーが実装するだけっぽい感じなら,完全に任せて僕と電波で解けそうな問題を探しておく.
メインコーダーが考えたら解ける問題も多いので,メインコーダーに考える時間を作れるようにできたら調子が良い.
ペアプログラミングは大事.

開始2週間ぐらい前

学内で練習会.結構余裕でまぁ突破はできるかなーと思った.

開始1週間ぐらい前

模擬国内予選で10以内すら入れず.学内も3位で,今年で引退も見えて焦る.

前日

チームメイトと基本的なことを確認.失敗しなきゃいけるはず…

当日

過去問をたくさんといて,頭をICPC脳にする.開始前にはちょっと昼寝.起きたときに寝ぼけてて,寝過ごしたかとかなり焦った.

本番

  • A問題みんなで読む.
  • なんか概要が読めた気がする.書き出そうとする.
  • 500*500のテーブル作れば通るよなーって感じで始める.Aにしてはむずくねー?って言いながら.
    • 別にそんなことしなくても良かったらしい.
  • メインコーダーがBの方が簡単じゃね?って言ったのでいったんパスしてBを任せる.
    • その間にAを速攻通せるように考えを詰めておく.
  • Bをちょっと詰まったみたいなので,プリントしてAをやる.
  • 電波に見てもらいながら書いて,一部間違いを直してもらって提出.AC.(16:47)
  • Cを電波が読んで,簡単らしい.一緒に問題を読む.
  • Bの間違い気づいたみたいで直した.提出.AC.(16:56)
  • Cを電波が書き出す.この時点で僕は完全に理解していなかったので,配列の生成などだけ書く.
  • 途中から理解.簡単なDP.二人で一緒に書いたり直したり.提出.AC(17:06)
  • Dをメインコーダーが書き出す.なんかめんどくさい実装らしい.完全に放置して電波と残りの問題を読み進める.
    • 僕がEを読み,電波がFを読む.
    • Eはグラフか…すぐには思いつかないなぁ.でもグラフならメインコーダーとか思いつく可能性は高いなぁ.
    • 電波がFできるかもって言ってる.Fを読む.まず問題文が難しい…けど,なんとなく理解.よくわからん.
    • Gを読む.問題文は超簡単w重めの幾何だろうなぁ.解法は結構簡単に思いつくけど,実装できるかねー?
  • (30分ぐらい経過)
  • Dをメインコーダーが通した(17:41).さすがです!僕は問題すら知らない.
  • 予選突破はこれでできたと思うので,とりあえず順位を確認.あれ?一位じゃねー?
    • このあと京都に抜かれてたらしい.
  • で,みんなで次何やるか相談.
  • ちょっとEが怪しい解き方を思いついた気がしたので,とりあえず書き出してみた.
  • 途中,電波がもっとヨサゲな解法を思いついたのでメインコーダーと相談してバトンタッチ.
  • 電波とメインコーダーがペアプログラミング.僕はとりあえずループするサンプルを考える.
  • 結構早めに実装終了.適当に作ったサンプルも通った.
  • ループ回数を最初多めにとって提出…しようとするもなかなか終わらないので仕方ないからループ回数を終わりそうなぐらいにとって提出AC. まじか!?(18:28)
  • 順位を確認._に続いて2位.
  • さて,残り時間を幾何に突っ込むか,謎の文字列に突っ込むかを相談.
  • 幾何は実装終わる気がしないという判断で文字列に突っ込む.きっと思いつけば.実装できるさ!
  • 文字列を全生成してみる.生成に結構時間かかるからこの方針無理っぽー(19:00ぐらい)
  • 残り30分で何もできなくねーって感じになってお菓子食べたりお茶飲んだりし始める.
  • 確か上位2チームは海外だからこのまま順位固定しねーかなーなんて考えながら集中できずにFを考える.
  • のこり3分ぐらいで東大が6問めを通した!うおおお!
  • 終了.

結果は3位.大学別では2位なので,去年と同じ派遣方式だと海外いけるか…?

なんにせよ,これ以上ないような結果だった.自分はチームの中ではたいしたことないので,本当にチームメイトのおかげだと思う.アジア地区予選は更に頑張りたい.

後輩も結構成績よくて,来年引退してからの楽しみも増えた(*´v`*)

TCO Round1

すぐ寝ようかと思ったけど,惜しかったからイライラっとしてねれないので更新.

250 EqualizeStrings

二つの文字列を同じにする.各文字を1文字進める/戻るコスト(a -> b, a -> z)は1.最小コストでおなじになる文字列を求めよ.複数ある場合は辞書順最初のを.

  • とりあえず文字の小さい方に適当に合わせてみよう.
    • tとgの場合真ん中のaにした方がいいのか…
    • tとgの真ん中あたりってどう求めよう.偶奇で分ける?う〜ん…
    • a-z全部やってみるか.a - > zに変換するときに25とかにしないように気をつけよう.
    • サンプル通った.出そう.

500 TwoRegisters

レジスタにX=1,Y=1が入っている.可能なオペレーションは X=X+Y,Y=X+Yのみ.命令数最小ででRにする命令列を求めよ.複数ある(ry

  • 後半加速しませんかね.X=1,Y=1からキャッシュmap[1000000][1000000]でやってみるか.
    • 余裕のTLE
  • 適当にノートに書いて考える.
  • 発想を逆転させるのよ,ナルホドくん!
  • 逆にやってみよう.X=R,Y=1..RをX=1,Y=1に戻すって考え方で.
    • 仮にひとつずつ減っていって,R * R / 2ぐらいかなぁ…間に合わなそうだけどやってみよう.
    • 500000ぐらいまでなら答えが出そう.
    • チューニングすれば通るか?どこ速くなるかな…
    • 文字列処理が明らかに遅いけど,早くする方法が上手く思い浮かばない…
    • あれ,gcd(R,i) != 1のときって(1,1)にならなくない?
    • xの倍数どおしの差はxの倍数だろう.これで刈れる?
    • 1000000が通った!これで勝つる!

チャレンジフェイズ

  • 500落ちてると仮定すると,ギリギリ通ってない程度.
    • 自分がやったような間違いをしているソースが,勇気を出せ…

出せませんでした.誰かに落とされてました.自分と同じ間違いは他の人のを落とすチャンスなので,とても大事.点数的には落としに行くのが最適戦略だよなぁ.

結果

500はTLEで通らないケースが有った.あとで人のソース見て,文字列を生成しない方法にしたら通った.string(x,'X')みたいの大杉…

今回は十分考えられて,十分手を動かすことができたのでよく戦えた.今回の感想.

  • とりあえず手を動かす
    • コード書くにしても,ノートに書くにしても.
  • 逆転裁判
    • 結論から考えたりしてみる.

次にいけたなぁ.(´・ω・`)