Mac Book Proの環境を整える

Mac Book Pro Retina 13インチ(OS X Mountain Lion 10.8.3)を買いました。初Macです。

今回Macを買った理由としては、

  1. Mac使い、なんかかっこいい：厨二病
  2. 今のPCが不調だった：キーボードが不調・処理が重い
  3. 今の環境に不満があった：コーディングはTerminalベース、スライドはパワポがよいけどデュアルブートでいちいち再起動つらい
  4. iPhoneアプリをいじりたかった：インターンで作ったのも放置しているし、そもそも就職するとそういうことやる予定だし
  5. Macの経験値も欲しい

などがありました。
とかいうと「それWindowsでできるよ」とか「Linuxでできるよ」みたいな人が現れそうです。いい案がある方は今後のために教えていただけると嬉しいです。

(余談：この前pear linuxというやばいやつも知ったのでこれもそのうち試してみたいです。むしろMacに慣れてから触ってみたい。)

で、とりあえず自分なりに最低限の環境を整えることにしました。

Step0 keynote

Macの標準的なプレゼンソフトにはKeynoteというのがあります。
Mac用のMicrosoft Office PowerPointもあるようですが、せっかくなので&&1700円だったのでこれを入れました。

僕はMBPをオンラインで買ったのですが、そのときにオプションとしてKeynoteをはじめとするiWorksのソフトがデフォで入れられるので、Keynoteだけ入れました。
いわゆるWordやExcelは僕はあまり使わない上、旧Windowsマシンには入っているので、使いたいときはそっちでやることにしました。

Keynoteは正直まだ慣れなくて使い勝手が悪く感じてしまいますが、パワポより綺麗に作れるなあ、と感じています。

Step1 ウイルス対策

やはりネットに繋ぐ以上は気になるので、調べてみました。
Macユーザーは明らかに増えているのでウイルスも結構狙っているのかなあ、と思ったら、ぱっと調べた感じだとそこまででもなさそうで、普通にLinuxっぽい感じでした。

後々きちんと調べることにして、ここでは特にソフトをインストールしたりはせずにとりあえずいつもの環境を整えることにしました。

Step2 諸々ソフトとかアプリとか

あたりを入れました。
MacのTwitterクライアントだと、夜フクロウが人気のようですが、僕はWindowsでJanetterが気に入っていたのでとりあえずそれを入れました。

MacでのインストールはApp Storeに行くか、.dmgとか.pkgとかをダウンロードしてきてダブルクリックするとあとはだいたいフィーリングでできます(適当)
アプリのアイコンをダブルクリックしたり、アプリケーションフォルダにドラッグ&ドロップするとインストールできます。

Step3 研究やプロコン用

インターンでiPhoneアプリ開発にXcodeを使っていたので、それをまず入れることにしました。

すると、
http://blog.livedoor.jp/umtoto/archives/65341739.html
にgnuplotとかMacPorts(Linuxでいうyumとかapt-getとかのMac版)の入れ方も含めて書いてあったのでその通りにしました。

Terminalからg++を呼び出すためには、以下のようにXcodeのpreferenceに入って、Command Line Toolsをインストールすればよいです。
http://hirooka.pro/?p=108

次にEmacsを入れることにしましたが、ここでハマりしました。
portが便利なのでそれでEmacsも入るだろうと思ったら確かに入ったのですが、それだとどうも&をつけてもTerminal外の新規ウインドウで立ち上げられないらしいです。
ということで、調べるとCarbon EmacsとかCocoa EmacsとかEmacs for Mac OS Xとかいろいろ出てきて、いろいろ試すうちにどのemacsが動いているのかわからず、ディレクトリに入り込みながらいじっているうちにsudoが効かなくなる状態に陥ったので、OSをClean Installし直しました。わからないのに適当にいじるのはホントよくないのでやめましょう(自戒)

http://wayohoo.com/mac/tips/how-to-clean-install-os-x-mountain-lion.html

おおむねここに書いてある通りにClean Installして、その後Emacs for Mac OS Xを落として

http://asakanomiyako.blog11.fc2.com/blog-date-20120408.html

にある通りに.bash_profileを設定したらできるようになりました。

TeX執筆用にはTeXShopというのがあるらしいのでそれを使ってみることにします。
http://ballrw.web.fc2.com/tex/install_mountainlion_new.html
ここにあるBall Installation Assistantというのを落としたら一発でした。

Step4 細かいところ

Terminalはアプリケーションの下のユーティリティというディレクトリに入ってます。

Terminalを起動すると、マシン名が「"氏名"-no-MacBook-Pro」とかいう激ダサの名前になっていることが判明したので、直します。
システム環境設定から共有にいくと、コンピュータ名が表示されるので、そこを編集するだけです。

あとは、デフォルトでは拡張子を表示してくれない設定なので、これを変更しました。
Finderを開いて、左上の"Finder"から環境設定に行き、詳細タブをみるとチェックボックスがあります。

Step5 これから

いろいろ調べたり教えてもらいながらうまく使っていきたいと思います(小並感)

Google Code Jam 2013 Qualification Round

A,B,C,Dsmallを解きました。

問題はこちら

A. Tic-Tac-Toe-Tomek

　所謂四目並べの盤面が与えられるので、勝・敗・引き分け、あるいはまだ進行中かを答える問題。

解法：

　さすがにやるだけ。
　縦・横・対角のX,O,Tの数をカウントして、X(or O)が4つ、または3つ + Tが1つなら勝敗がわかる。
　勝敗がついてないときは、'.'が盤面にひとつでもあれば進行中、なければ引き分け。
　文字のカウントは'.'も入ってめんどくさかったのでmapを使った。1ケースあたりO(10*4*log4)
　例えば横を調べるときは以下のような感じ。

  for(int i=0;i<4;i++){
    map<char,int> cnt;
    for(int j=0;j<4;j++)cnt[board[i][j]]++;
    if(cnt['X']==4 || (cnt['X']==3 && cnt['T']==1))ans = "X won";
    if(cnt['O']==4 || (cnt['O']==3 && cnt['T']==1))ans = "O won";
  }

　smallとlargeの違いはテストケース数だけなのでそのままやればlargeも通る。

B. Lawnmower

　N×Mの芝生があり、初期状態ではすべて長さ100である。
　縦もしくは横一列を一斉に任意の長さに変える操作が可能である。
　この操作を好きなだけ繰り返せるとき、指定した芝生の状態を作れるかを問う問題。

　制約：small 1≦N,M≦10, 1≦a[i][j]≦2
　　　　large 1≦N,M≦100, 1≦a[i][j]≦100

解法：

　これ(AOJ 1079)を思い出して逆順シミュレーションすればよいと気付く。
　すなわち、与えられた芝生の状態からすべて長さ100の状態に戻せるか、を考えればよい。
　そうすると、与えられた芝生の中で一番短い芝生は、最後に刈られていることになる。
　ということは、その縦、もしくは横一列の全ての芝生もまた、最も短い芝生と同じ長さでなければいけないことになる。
　よってこの条件を満たし続けるように復元していけばよい。
　(一度復元したところはそのときどんな長さでもよいので適当にドントケアにしておく)
　1つのテストケースあたりO(N*M*(N+M))。
　きっちり復元を再現しなくてもよいらしい。(こちらを参照)

　smallだけ解けるような解法が思いつかなくてほげ。

C. Fair and Square

　自身が回文数(=文字列とみなしたときに回文になっている)、かつ、自身の平方根も回文になっている数をFair and Squareであるという。
　区間[A,B]中に存在するFair and Squareの数を求めよ。便宜上制約を1≦A≦B≦Nとする。

　制約：small N=1000
　　　　large-1 N=10^14
　　　　large-2 N=10^100

small解法：

　ナイーブに調べればよい。AからBまでループを回して、自身が回文数ならその平方根を求め、平方根が整数ならそれが回文数か調べる。以下のようなコードでよいと思われ。

for(int i=A;i<=B;i++){
  if(isPalindrome(i)){
    int a = sqrt(i);
    if(i == a*a && isPalindrome(a))ans++;
  }
}

問題はisPalindromeの実装だが、stringstreamとか使って文字列にしてやるのがたぶん一番楽。

bool isPalindrome(int x){
  stringstream ss; ss << x;
  string s = ss.str();
  for(int i=0;i<s.size();i++){
    if(s[i] != s[s.size()-1-i])return false;
  }
  return true;
}

O(N*log_10 N)なのでsmallは余裕。

large-1解法

　このままだとO(10^14*14)になって死亡するが、ちょっと発想を変えればいける。
　逆にAが回文数のとき、A^2が回文数ならA^2はFair and Squareである。
　ということで、N^(1/2)まで回文数チェックを行い、その二乗を求めてそれが回文数なら答えに追加すればよい。
　ちなみに、smallも含めて答えを列挙してあとから(二分or線形)探索する方が効率的である。

#define all(a) (a).begin(),(a).end()

vector<long long> fs; //Fair and Square Numbers
for(long long i=1;i<=10000000;i++){
  if(isPalindrome(i)){
    if(isPalindrome(i*i))fs.push_back(i*i);
  }
}

for(int i=0;i<TestCase;i++){
  cin >> a >> b;
  int ans = upper_bound(all(fs),b) - lower_bound(all(fs),a);
  cout << "Case #" << i+1 << ": " << ans << endl;
}

large-1のサイズならO(7*10^7 + T*log|fs|)程度なので間に合う。

large-2解法：

　10^100はやばすぎなので、普通にやっては解けない。のでOEISを使おう。
　というのが賢いやり方だと思うが、僕は普通に解いたのでそれを説明する。

　まず、二乗といえど普通の掛け算なので、筆算で書いてみる。
　回文数なので下のように変換しても同じ。
　

　よく見ると各桁の和も対称になっている。
　すなわち、キャリー(足し算の繰り上がり)が無ければ回文数になるのは明らか。
　問題はキャリーがある場合だが、キャリーがあると回文数にはならない。以下簡易証明。

　最下位(=最上位)に注目すると、キャリーがある場合、キャリー=最下位桁にならなければならない。
　すなわち、1〜9までの二乗のうち、2桁になり、1桁目と2桁目が一致、あるいは2桁目+1が一致するものとなる必要があるが、
　そんなものはないので、最下位桁でキャリーは起きない。
　となると、最下位桁は1,2,3のどれかになる。そうすると、最上位桁にキャリーを持ち越すと回文が崩れるので一個下の桁もキャリーはない。
　というのが再帰的に起こるので、絶対キャリーは起きない。

　となると、条件は各桁の和が10よりも小さければOKということになる。
　中央の桁に注目すると、これは2乗和になっているので、少なくとも2乗和が10よりも小さいことがわかる。
　ということは、3を使う場合それ1個のみ、2を使う場合中央か端で1回のみ、となるので、ほとんどが0と1のみのケースとなる。
　回文であることを頭に入れると、前半だけ決めると後半も決まる。1は前半で4回までしか使えない。
　よって、100桁でも大雑把に50C4程度しか組合せの数は存在しないため、全部調べても余裕。
　実は中央の桁が最大になることも(少し頑張ると)わかるので、2乗和が10を越えないような列を生成すればOK。

　ただ、二乗と大小比較を行うため、BigIntegerが欲しくなったりするところも割とめんどくさい。
　僕の自作BigIntがある前提だと以下のコードになる。(っていうかコレを提出した)

vector<BigInt> ps;
string a,b;
ll ans;

int cnt = 0;
void rec(int l,int n,string s,int sum){
  if(2*l>=n){
    cnt++;
    if(n&1)l--;
    for(int i=l-1;i>=0;i--)s += s[i];
    ps.push_back(BigInt(s)*BigInt(s));
    return;
  }

  for(int i=0;i<=3;i++){
    if(l==0 && i==0)continue;
    s += (char)('0'+i);
    int tmp = sum;
    if(2*(l+1)<=n)sum += i*i*2;
    else sum += i*i;
    if(sum<10)rec(l+1,n,s,sum);
    sum = tmp;
    s.erase(s.end()-1);
  }
}

int main(){
  int testcase;
  for(int i=1;i<=51;i++)rec(0,i,"",0);

  cin >> testcase;
  for(int casenum=1;casenum<=testcase;casenum++){
    cin >> a >> b;
    ans = upper_bound(all(ps),BigInt(b)) - lower_bound(all(ps),BigInt(a));
    cout << "Case #" << casenum << ": ";
    cout << ans << endl;
  }
}

D. Treasure

　箱がN個ある。鍵の種類が決まっていて、鍵と鍵穴の種類がマッチすると開けられる。
　初期に持っている鍵の他に、箱から新たに鍵を手に入れることもある。
　箱の鍵穴の種類、初期の手持ち鍵、それぞれの箱から手に入る鍵の情報に基づいて、すべての箱を開ける手順のうち辞書順最小の手順を示せ。

　制約：small 1≦N≦20,1≦鍵の総数≦40
　　　　large 1≦N≦200,1≦鍵の総数≦400

small解法：

　制約が20なので、お約束のbit全探索を疑う。
　どの箱が開いているかを0,1で表現すると、2^Nの状態がある。
　これに掛けることの今手持ちの鍵の情報……と考えてしまうが、開いている箱が同じであれば、手持ちの鍵の状態は常に同じになる。
　なぜならば、初期の鍵も、箱を開いて手に入る鍵も、箱を開くために消費した鍵も、すべて変わらないためである。
　よって、状態数は2^Nしかないため、全て開いていない状態→全て開いた状態へのパスを探せばよい。
　ただし普通に再帰して全探索するとつらそうなのでメモ化再帰にした。これで計算量はO(N*2^N)。
　また、鍵の数を状態ごとに復元するのがめんどくさかったので、関数の引数には鍵の数を持たせた(がメモ化のkeyとしては使わなかった)
　辞書順最小は、辞書順で若いものから優先的に使うように探索するだけでよい。

int k,n;
vector<int> ans,path;
int memo[1<<20];
int c[300],kn[300],gk[300][500];

int rec(int state,vector<int> keys){
  if(state == (1<<n)-1){
    ans = path;
    return 1;
  }

  if(memo[state]>=0)return memo[state];
  
  rep(i,n){
    if( (state>>i)&1 )continue;
    if(keys[c[i]]){
      keys[c[i]]--;
      path.push_back(i+1);
      rep(j,kn[i])keys[gk[i][j]]++;

      if(rec(state|(1<<i),keys) == 1)return memo[state] = 1;

      rep(j,kn[i])keys[gk[i][j]]--;
      path.pop_back();
      keys[c[i]]++;
    }
  }
  return memo[state] = 0;
}

int main(){
  int testcase;
  int tmp;

  cin >> testcase;
  for(int casenum=1;casenum<=testcase;casenum++){
    vector<int> keys(201);
    for(int i=0;i<=200;i++)keys[i] = 0;

    cin >> k >> n;
    rep(i,k){ cin >> tmp; keys[tmp]++; }
    rep(i,n){
      cin >> c[i] >> kn[i];
      rep(j,kn[i])cin >> gk[i][j];
    }

    path.clear(); ans.clear();
    rep(i,1<<n)memo[i] = -1;

    rec(0,keys);

    cout << "Case #" << casenum << ": ";
    if(ans.empty())cout << "IMPOSSIBLE" << endl;
    else rep(i,n)cout << ans[i] << ((i==n-1)?"\n":" ");
  }
}
large解法：

　わからん。神々のソースコードを読もう(提案)。

Bitwise Tricks & Techniques

　この記事はCompetitive Programming Advent Calendar Div2012、20日目の記事です。(余談：そういえば本日2012/12/20は良い日ですね！)

はじめに

　今回はDonald.E.Knuth著”The Art of Computer Programming”のVolume4-1の前半パートであるBitwise Tricks & Techniquesで取り上げられているビット演算について記事を書きたいと思います。ただし、ここで取り上げられているものは必ずしも競技プログラミングにおいて実用的とは限りません。すでに関数として定義されているものはそれを使った方が実装量が減らせてよいと思います。なので、「ビット演算やべぇおもしれぇ！！」と思ってもらう一助となることを目指した読み物、という感覚で読んでいただけると幸いです。

　今回はC++言語を基本としてコードを紹介しますが、だいたい普通の言語なら実装されているであろうビット演算しか使いません。基本的にはAND、OR、XOR、NOT、LEFT(RIGHT) SHIFT、+、-、*があれば十分です(本の中ではアーキテクチャレベルでbit matrix演算が1ステップで出来ることが想定されてたりするMMIXというやばい言語が使われています)。また、x番目のビット、というときは特に断りがない限り右から0-originで数えて下さい。例えば(01000)は3番目のビットが立っています。unsigned long longをullと略記します。

　次節は本のあらまし、そのまた次節はビット演算の基礎で、本の内容には直接関係ないので興味のない方は読み飛ばしてもらって構いません。

KnuthとThe Art of Computer Programming

　Donald Ervin Knuthは単文では紹介しきれないほど偉大な業績*1をお持ちの計算機科学者です。プログラミングコンテストに参加している方なら文字列検索アルゴリズムであるKMP(Knuth-Morris-Pratt)法などで名前を聞いたという方も多いと思います。The Art of Computer ProgrammingはKnuth先生が自らライフワークと宣言するほど力を入れている著書で、現在4巻の分冊4までが出版されています(7巻まで出す予定らしい)。濃い内容で演習問題も鬼畜の如く充実していることでも有名です。

　今回紹介するVolume4-1は論理関数に関する話を取り扱ったもので、前半がビット演算、後半がBDD(Binary Decision Diagram)について記されています。数え上げお姉さん動画で有名になった(？)ZDDも載っているので興味がある方は手に取ってみるとよいでしょう。今回は前半のビット演算からトピックを持ってきて紹介したいと思います。

ビット演算

　そもそもコンピュータは内部では0か1かの二値(=ビット)ですべての情報を扱っています。二値を扱う演算は論理演算と呼ばれ、全部で2^{2^2}通り考えることができます。

　このビットを複数個組み合わせたものを見ることでコンピュータは様々な情報を表現します。たとえばC++言語の通常の整数型では、32ビットを利用して-2^{31}〜2^{31}-1までの整数を表現しています。ビット演算とは、このようなビットのまとまりに対する操作を行うものです。つまり整数型では32ビットを一気に扱う操作となります。

　これはよくよく考えるとものすごいことで、論理演算を32回行わないといけないこともまとめて処理することで1回で済む、つまり32倍高速化できるわけです(その効力は去年のxhl_kogitsuneさんの記事”悪い子のためのビットベクターによる定数倍高速化”等を参照)。このように、ビット演算を駆使することで計算を効率的にしたり、情報をわかりやすく表現したりすることで、より幅の広いプログラムを書くことができます。

　情報をわかりやすく表現する、という一例として、集合の表現があります。これはi番目のビットに1が立っていればi番目の要素が集合に含まれている、と解釈するもので、プログラミングコンテストチャレンジブック(第2版が好評発売中です！やべぇ！)などでもわかりやすく紹介されています。

　この表現の凄いところは最小完全ハッシュ関数になっている上にsubset→supersetの順に昇順になっており、しかもデコードせずとも様々なクエリをO(1)で処理できるなど挙げればキリがありません。あまり注目されていない性質な気もしますが、例えば順列の最小完全ハッシュ関数としてよく知られているもの(http://www.ic-net.or.jp/home/takaken/nt/slide/hash.html)は愚直に構築するとO(n^2)かかってしまいます*2し、コードのまま操作する方法も考案されていないようなので、操作しようとするとデコード→操作→エンコードというように、一度解凍しないと使えないです。集合のように自由にはいきません。このように、集合のビット表現は非常に面白い性質を持っていて、プログラムで集合を扱うときにとても便利です。

　以上、ビットを駆使するメリットの一部を紹介しましたが、他にもここでは書ききれないほどたくさんあります。今年2日目のPhylloさんの記事"へ、変態っ！！読めないからやめてっ！bit使ったデータ構造・アルゴリズム実装集"なども見てみるとよいでしょう。ビット演算に興味が湧いてきたところ(？)で、いよいよ本題の本の内容に入ります。

rightmost bit

　xのrightmost bitとは、xの一番右に立っているビットのことです。例えばx = (10100)だと右から2番目のやつですね。これを取り出す簡単な式は有名で、y=x&-xです。でも、これはあくまでy=(00100)というのを手に入れただけで、”2番目”という情報はこれだけでは得られません。つまり、直接yに2を代入してほしいこともあります。これを\rhoとする(すなわち、最右は\rho番目のビット)と、どうすれば\rhoを求められるでしょう？普通にやるとO(n)かかってしまいます。
　これには2通りの方法が紹介されています。1つ目は、”magic mask”を利用する方法。“magic mask”とは以下のようなものです。

　\mu_0 = (…010101010101010)
　\mu_1 = (…011001100110011)
　\mu_2 = (…000111100001111)
　\mu_3 = ……

　すなわち\mu_iでは2^i個の連続した0と1が交互に現れます。この“magic mask”は以降も頻繁に現れます。これを使うと以下のような式で\rhoを書き下せます([A]はAが真なら1,偽なら0の値を取ります)。

　\rho = [x & \mu_0 == 0] + 2[x & \mu_1 == 0] + 4[x & \mu_2 == 0] + …

\rhoの2進数表示におけるi番目のビットが1かどうか、を\mu_iでマスクすることによって調べているわけです。よって、64bitなら以下のようにコーディングできます。

 int right_num(ull x){
  ull M[6] = {0x5555555555555555, 0x3333333333333333,
	      0x0f0f0f0f0f0f0f0f, 0x00ff00ff00ff00ff,
	      0x0000ffff0000ffff, 0x00000000ffffffff};
  int rho = 0, pow = 1;
  x = x&-x;
  for(int i=0;i<6;i++){
    if(!(x&M[i]))rho += pow;
    pow <<= 1;
  }
  return rho;
}

これで、O(logn)まで落とせました。
　2つ目の方法ははっきりいうと埋め込みです。

　\rho = decode[( (a*(x&-x) )mod2^{64})>>58]

とすると、例えばa = 0x03f79d71b4ca8b09 と以下のdecodeテーブルでO(1)で\rhoが求まります。ullを用いるとオーバーフローすると勝手にmod2^{64}と同じことになるので便利です。decodeの[　]の中の部分はハッシュ関数のようになっているわけです。

  int decode[64] = {  0, 1,56, 2,57,49,28, 3,61,58,42,50,38,29,17, 4,
                     62,47,59,36,45,43,51,22,53,39,33,30,24,18,12, 5,
                     63,55,48,27,60,41,37,16,46,35,44,21,52,32,23,11,
                     54,26,40,15,34,20,31,10,25,14,19, 9,13, 8, 7, 6 };

aは何でもよいわけでなく、8bitずつスライドさせていって出てきた2進列が全て異なる必要があります。この制約を守ることでハッシュ関数の全単射性を保っているのです。

leftmost bit

　leftmost bitは一番左に立っているビットです。y番目に立っているとすると、y=⎿lgx⏌です(ただし、xは正整数)。以下のコードでO(logn)で求まります。

  int left_num(ull x){
    int lam = 0, pow = 32;
    for(int i=0;i<6;i++){
      if(x>>pow){
        lam = lam + pow; x >>= pow;
      }
      pow >>= 1;
    }
    return lam;
  }

上位powビットがすべて0なら下位powビットに最左ビットがあり、0でないなら上位powビットのどこかに最左ビットがある。二分探索ですね。

sideways addition

sideways additionとは、所謂popcountと同じです。つまり、立っているビットの数のことです。xのsideways additionを\nuとおくと、

　\nu = x_{n-1} + … + x_1 + x_0

です。簡単な方法として、rightmost bitを消していく方法があります。つまり、

  res = 0;
  while(x){x = x&(x-1); res++;}

これはxがsparse、すなわち立っているビットが少ないとき有効です。逆にdenseなときは、

  res = 64;
  while(x<-1ULL){x = x|(x+1); res--;}

などとすればよいです。ullだと-1ULLは2^{64}-1になります。
　しかしこれだと結局最悪時O(n)です。これは以下のようにすると改善できます。

  ull popcount(ull x){
    x = x-((x>>1)&M[0]);           //2bit毎のpopcountが32個並ぶ
    x = (x&M[1])+((x>>2)&M[1]);   //4bit毎のpopcountが16個並ぶ
    x = (x+(x>>4))&M[2];           //8bit毎のpopcountが8個並ぶ
    return (0x0101010101010101*x)>>56;  //8個を足した数を返す
  }

分割統治法の要領で、小さい部分問題からより大きい部分問題の答えを求めています。2^{i+1}ビット毎のpopcountを出すために(x&M[i])+((x>>2^i)&M[i])すればよいのは手でやってみるとわかると思います。よって、1,3行目もそのように書けばよいのですが、ここはコードのように書くことで演算回数(式中の+とか&とか>>とかの個数)を減らすことができ、最適化されています。returnのところがなぜこうなるのかは、筆算のように書き下してみるとわかると思います。

bit reversal

　bit reversalはビットを逆順にする操作です。これは局所的なreverseを繰り返し、範囲をどんどん広げながら行うことでできます。

  ull reverse(ull x){
    x = (x>>1)&M[0] | (x&M[0])<<1;
    x = (x>>2)&M[1] | (x&M[1])<<2;
    x = (x>>4)&M[2] | (x&M[2])<<4;
    x = (x>>8)&M[3] | (x&M[3])<<8;
    x = (x>>16)&M[4] | (x&M[4])<<16;
    x = (x>>32)&M[5] | (x&M[5])<<32;
    return x;
  }

これもsideways additionと同じような分割統治法とみることができます。

bit swap

　bit swapは、i番目のビットとj番目のビットを入れ替える操作です(i>j)。δ=i-jとすると、

y = (x>>δ)&2^j, z = (x<<δ)&2^i , x = (x&(~(2^i | 2^j))|y|z

でできます。yにはxのjビット目が立っているときiビット目が立っているものが、zにはxのiビット目が立っているときjビット目が立っているものが入ります。最後にxのi,jビット目を0にしたものとy,zのORをとればＯＫです。でもこれだと普通すぎてつまらないです。XORをつかうともっと短く出来ます。

  ull swap(ull x, int i, int j){
    ull d = i-j, y = (x^(x>>d))&(1ULL<<j);
    return x^y^(y<<d);
  }

これはXORの特性を使っています。XORは異なるビットのときのみ1を返します。すなわち、x_i≠x_jのときだけ、yのjビット目が立っています。さらに、1とXORをとるとそのビットは反転します。よって、yのjビット目が立っているとき(=x_i≠x_jのとき)、xのi番目のビットとj番目のビットが反転します。x_i≠x_jなので、これでx_iとx_jが入れ替わったことになるのです。x_i=x_jのときは何もしませんが、同じなので入れ替える必要はありません。何もしなくてよいのです。

Application to Data Structure

　プロコン勢の皆さんおなじみのデータ構造にheapがあります。これは格納順に番号を付けていくと以下のようになります(右は番号を2進数にしたもの)。

　これと似たようなものとしてさらにsideways heapというものがあり、これは以下の図のようなものです。

　これはin-order(通りがけ順)に対応するように番号付けするものです。注意すべき点は、すべての頂点を参照するためにはn(図ではn=10)を越えた番号の頂点も途中で現れることがある、という点です。この2つのヒープは面白い違いがあり、要素が無限個あると仮定すると、通常のheapは根が定まる(1)のに対して葉は定義できませんが、逆にsideways heapは無数の葉がある(奇数番号)が根がありません。
　それぞれのヒープ上の頂点xからみた関係クエリは以下のように行えます。k=x&-xです。

　このsideways heapを考えることでなにが嬉しいかというと、nearest common ancestor(所謂LCA、最近共通祖先)を任意の有向森に対して求めることができたり、priority queueとして使えたりします。この辺が面白いところなのですが、時間上紙面上割愛させていただきます。興味のある方は読んでみて下さい。

おわりに

　長くなってしまい＆説明不足でごめんなさい。しかしBitwise Trick & Techniquesで取り上げられているトピックはまだまだたくさんあります(一度に複数箇所操作したりとか、他の応用の話とか)。興味を持っていただいた方は是非原著を読んでみるとよいと思います。
　明日の記事担当はtomerunさんとtouyoubuntuさんです。楽しみですね！

*1:代表的なものでは、TeX・METAFONT開発、チューリング賞(1974)、フォンノイマンメダル(1995)、京都賞(1996)など

*2:見かけないですがfenwick木を用いればO(n logn)にできるはずです。まあハッシュ関数値が実用的に機能するのはn=20くらいがせいぜいなのであまり影響は大きくないと言えなくもないです

会津大学競技プログラミング合宿　参加記

9/3〜5に会津大学で行われた競技プログラミング合宿に参加してきました。

この合宿は毎日3〜5時間程度のコンテストを行い、実力向上を目指すのはもちろん、他大学の人と一緒にチームを組むなど、普段会えないような人達と交流を深めることも目的となっています。

大学の団体が主体となって行われるプロコン合宿は去年も行われた会津合宿が初であり(たぶん)、今年3月の立命館合宿に続き3回目の合宿となります。
去年は合宿の存在すら知らなかった僕ですが、3月の立命館合宿に参加したのがとても楽しく刺激になったことと、ちょうど東京を訪れる用事があり陸路で簡単に行けそうだったことがあり、参加させていただきました。今回の合宿もとても楽しかったので、少し感想など書いてみようかと思います。

Day1

1日目はインターンの最終日と重なっていたため、参加できませんでした。

問題は立命館大学の方々の作問で、ついにRespect2Dさん一押しのやよいちゃんが問題に登場したらしく、楽しそうです。(チーム練習用にとってあるのでまだ問題読んでません)

2日目に向けて、インターンが終わってすぐに電車＆新幹線で移動を開始しました。インターン勢も会津合宿勢も懇親会をやっていてうらめしかったうらやましかったです。

ここで、どうやらkmatsunaga先生と同じ電車に乗っていたらしく、合流してお話しさせていただきました。
先生のお話は大変ためになりました。というのも、僕は学生であり、コンテスタントとしてもまだ3年目です。
先生とお話して、歴史とまではいかなくとも時代の流れであったり、教員・社会人として見た競技プログラミングであったり、自分の今までの視点とは違ったプログラミングコンテスト観を知ることができました。
やはり僕は考えも能力も子供だなあ、と思いました。いろいろと精進せねば。
先生、ありがとうございました。

会津に着いて先生と別れてからはすぐにホテルで休みました。

Day2

朝起きて、さあ出発だ、と思ったら、スマホの電池が赤かった。
ふとコンセントの近くを見てみると、「消灯中は電気が供給されません」との文字が。
もともとデフォルトで「リアル運×、迷子◎」の属性を有する僕は、G○○gle M○ps大先生という武器を奪われてしまい、本気でやばかったです。なんか住宅地の細い路地とか通りまくりました。
なんとか無事時間ギリギリに到着することができ、会場へ。立命合宿で知り合った方々に久しぶりにお会いできて嬉しかったです。

2日目のチームは事前のアンケート結果から運営側が決めたチーム分けでした。立命館・会津の方とKOREというチームを組みました。Dで始まらないです。
このコンテストは非公開(のちのち別のopenコンテストとして開催するらしい)なので、問題については言及しません。
チームとしてはちょっと僕が実装しすぎてしまったかなあ、という感じで、もっとみんなで話し合いながら実力向上につなげられる形でできればよかったなあ、と反省しています。
チームを組んでくださったお二人、ごめんなさい＆ありがとうございました！

コンテストが終わった後は恒例のみんなで解法話し合いphaseで、やはり競技プログラマの皆さんだとここが盛り上がって楽しかったり悔しかったり。
解説が終わってから懇親会まで時間があったので、そのままぐだったりしてました。
その最中、必ず答えが"Shimejitan is Dead."になる問題が生まれたりしてやばかったです。

懇親会はカツ屋さんに行きました。
「注文が面倒なのでみんなカツ定食か味噌カツ定食にしよう」と決めた後にwinfieldさんだけカツ煮込み定食を頼んだりしてやばかったです。
真面目な話では、kmatsunaga先生による海外地区予選参加のススメが行われていて、やはり乗り気の人々が多かったようです。かくいう僕も興味はあるのですが、お金のこともあるので他のチームメンバー含め辛そうだなあ、と思っています。要相談。

そのあとは帰って寝ました。うずたんかわいい。

Day3

最終日は会津大のアジア地区予選出場チーム"oshieteZukky"（俗称"おしず")の作問セットです。"KND is So Sexy"でした。
この日は自由にチームメンバーを決めてよいとのことだったので、前日から決めていた通りshioshiotaさんとRespect2Dさんと組みました。shio2derseinというチームです。
TopCoderのレーティングや年齢などが近く、個人的にも好きなメンバーでチームが組めて面白そうだなと思いました。

コンテストが始まってshioshiotaさんがA、Respect2DさんがB、僕がDを読みました。
shioshiotaさんが数学苦手といっていたのでちょっと協力しながらAを解きました。
そのあとはRespect2Dさんが全自動でBを通してくれました。惜しくもファーストアクセプトは逃しましたがそれに迫る勢いで解いてくれてさすがでした。
Dはそれぞれの地点から最近傍のワープ地点を求めればいいだけだと気付きましたが、それを効率的に実現するアルゴリズムが思いつかず、断念してCとEにとりかかりました。
Cは幾何っぽい感じで解法もパッと思いつかず苦戦しました。一方、Eは明らかなライブラリゲー臭を漂わせており、基本Cを解きながら詰まったら交代してE用のライブラリを写経する戦略で回しましたが、残念ながらどちらも通せず2完に終わりました。
チーム練習をもっとして個々の強みや戦略を詰めればもっといけるポテンシャルを感じていただけに、余計に残念ではありましたが、その分学ぶことも多かったと思います。お二人ともありがとうございました！

飛行機の時間の関係で、すべてのスケジュールが完全に終わる前においとましました。
もっとみなさんとお話ししたかったので残念でした。

あ、あと、会津若松駅までの道中でやけにキャリーバッグが重いなあ、と思っていたらいつの間にか片輪がもげていてやばかったです。

あ、あと、郡山駅のお土産屋さんのおねいさんの方言かわいい。うずたんかわいい。

まとめ

コンテストとしてみると結果は芳しくないものが多かったですが、個人で芳しくないときよりも断然得るものが多かったと思います。
何より交流という面で、普段は手の届かないように感じてしまう強い人や、密かにライバル視している人と実際に対面して話し、競い合うことは貴重で有意義な経験だと思います。
競技プログラミングはマイナーで、同じ趣味をもつ同年代の人達と集まれることはなかなかないと思います。
でもその分やはりモチベーションが上がりますし、なにより純粋に楽しい！
どんどん交流の輪を広げ、実力をつけ、自分たちの手でもっともっと競技プログラミング界を盛り上げていきましょう！

今回参加した方も参加できなかった方も、ぜひまた次回参加しましょう！(また春休みに立命合宿があるとの噂が)
また、参加するだけでなく自ら合宿を開きましょう！(参考:Tayamaさんの資料 http://acm-icpc.aitea.net/index.php?plugin=attach&refer=2011%2FCoachWorkshop&openfile=5-ja.pdf)

合宿を企画・運営して下さった皆様、参加者の方々、本当にありがとうございました。
今後も様々な機会で皆さんとお会いできるのを楽しみにしています。

RPCC Day1 D

変数を含んだ式が文字列として与えられるので、別情報として与えられる単位系の関係から、式が表している単位を求める問題。
errorになるケースでは空のvectorが返り値になるように処理しています。

#include<iostream>
#include<string>
#include<map>
#include<vector>
#define pb push_back
using namespace std;

int n,m,p;
map<string,vector<int> > d;
string der[20];
map<string,string> v;

vector<int> parse(string s){
  vector<char> op;
  vector< vector<int> > res;
 
  for(int i=0;i<m;i++){
    if(der[i] == v[s])return d[v[s]];
  }

  int pos = 0;
  string tmp;
  while(pos<(int)s.size()){
    if(s[pos] == '('){
      int k = 1;
      pos++;

      while(pos<(int)s.size()){
	if(s[pos] == '(')k++;
	if(s[pos] == ')')k--;
	if(!k)break;
	tmp += s[pos];
	pos++;
      }
      res.pb( parse(tmp) );
      tmp.clear();
      pos++;
    }else if(s[pos] == '+' || s[pos] == '-' || 
	     s[pos] == '*' || s[pos] == '/'){
      if(tmp.size()){
	res.pb( parse(tmp) );
	tmp.clear();
      }
      op.pb( s[pos++] );
    }else tmp += s[pos++];
  }
  if(tmp.size())res.pb(parse(tmp));

  for(int i=0;i<(int)res.size();i++){
    if(res[i].empty())return res[i];
  }

  bool f = true;
  while(f){
    f = false;
    for(int i=0;i<(int)op.size();i++){
      vector<int> hoge;
      if(op[i] == '*'){
	for(int j=0;j<p;j++){
	  hoge.pb(res[i][j]+res[i+1][j]);
	}
      }else if(op[i] == '/'){
	for(int j=0;j<p;j++){
	  hoge.pb(res[i][j]-res[i+1][j]);
	}
      }
      if(hoge.size()){
	res.erase(res.begin()+i);
	res.erase(res.begin()+i);
	res.insert(res.begin()+i,hoge);
	op.erase(op.begin()+i);
	f = true;
	break;
      }
    }
  }

  while(res.size()>1){
    for(int i=0;i<n;i++){
      if(res[0][i] != res[1][i]){
	res[0].clear();
	return res[0];
      }
    }
    res.erase(res.begin());
  }
  return res[0];
}

int main(){
  while(cin >> n >> m >> p && (n||m||p)){
    for(int i=0;i<m;i++){
      cin >> der[i];
      vector<int> hoge;
      for(int j=0;j<n;j++){
	int a;
	cin >> a;
	hoge.pb(a);
      }
      d[der[i]] = hoge;
    }
    string str;
    cin >> str;
    for(int i=0;i<p;i++){
      string t1,t2;
      cin >> t1 >> t2;
      v[t1] = t2;
    }      
    vector<int> ans = parse(str);
    if(ans.empty())cout << "error\n";
    else{
      int i,j;
      for(i=m-1;i>=0;i--){
	bool f = true;
	for(j=0;j<n;j++){
	  if(d[der[i]][j] != ans[j])break;
	}
	if(j==n){
	  cout << der[i] << endl;
	  break;
	}
      }
      if(i<0)cout << "undefined\n";
    }
  }

}

HUPPC #1 問題解説

　HUPPC #1で取り上げた問題について、僕の想定解法＋αを解説します。
　コードに関しては、Aizu Online Judge→Virtual Arena→Contest→HUPPC #1→Standingと進めば参加者のコードが読めるようになっていますので、そちらを参考にして下さい。

A. Sum of Consecutive Integers

　連続した数字の和がNになるような数字の選び方が何通りあるか答える問題。

　始点と終点を決めて、その間の連続した数の和がNになるかどうかを調べて数え上げればよいです。
始点・終点ともにNまでの中から選べばよいのでO(N^2)のアルゴリズムとなります。
(より正確には、1<=始点<終点<=(N+1)/2で選べばよい。2つ以上の数の和でなければいけない、すなわちi==Nは数え上げないことに注意)
Nがたかだか1000までなので、このアルゴリズムで問題ありません。
これが想定解で、全探索の問題として採用したつもりです。

　ここからは余談といってもよいですが、この問題はさらに計算量を落とすことができます。
僕のVirtual Arenaのコードは、sum[i]に1からiまでの和を格納し、
sum[j]-sum[i]==Nとなるようなi,jの組合せがあるかどうか調べています。
sum[i] = 1+2+…+i , sum[j] = 1+2+…+j, より、sum[j]-sum[i] = (i+1)+(i+2)+…+jという連続部分を調べられます。
僕のコードのように愚直に調べるときはこの方法もO(N^2)ですが、
sum[i]が単調増加であることに注目すると、sum[i]+N == sum[j]となるようなjが存在するかどうかを二分探索で求めればよいので、O(NlogN)で解くことが出来ます。

　また、少し違う始点から問題を見てみましょう。連続した数が何個あるのかに注目します。
あるsに対し、s個の連続した数の和がNになる組合せはたかだか1つしか存在しません。
これは、始点を1だけズラすと和は必ずsズレることから明らかです。
ここで、s個の数の中央の値に注目します。
sが奇数の場合、中央の値をmとするとmより左側の値はm-1,m-2,…と減っていき、
もう一方の右側の値はm+1,m+2,…と増えていきます。
左右の数の個数も等しいので、s個の連続した数の和は、m*sとなります。
したがって、m*s==Nとなるmが存在するのか、すなわち、Nがsで割り切れるかを調べればよいことになります。
偶数の場合はもう少し複雑です。ちょうど中央となる値が整数として存在しないからです。
しかし、中央に位置する2つの値の和をm2とすると、同様にm2*s/2==Nを満たせばよいことに気付きます。
よって、Nがs/2で割り切れるかを調べればOKです。
sは最大でもNまで調べればよく、ひとつのsにつき定数時間でチェックができるため、この方法はO(N)で高速です。
ただし、すこし終了条件に気をつけないと、0+1+2+… +s-1= Nなどといったケースも数え上げてしまうので、注意が必要です。中央の値<(s+1)/2のとき終了するようにしましょう。
　ちなみにこのアルゴリズムは後輩が考えたもので、僕は彼の話を聞くまで思いつきませんでした。優秀で頭が下がりますね。

B. CamelCase

　U: 文字列における単語の先頭が大文字になっている(先頭文字も大文字)
　L: 文字列における単語の先頭が大文字になっている(ただし先頭文字は小文字)
　D: 単語と単語の間を’_’で繋いでいる
という文字列を、相互変換する問題です。文字列処理に関する問題として出題しました。
文字列の扱いは複雑で難しいですが、その分慣れる必要があると思います。

　問題としては言われたとおりに文字列に処理を行うだけなので、特に解説する部分はありません。
ただし、C言語などでchar型の定数長配列によって文字列を管理している場合、入力の文字列の長さが100文字以下でも、この問題の場合’_’の挿入により答えが100文字越えすることもある点には注意しましょう。
　大文字<->小文字の変換は、’a’-32や’A’+32を用いてできる、という知識は覚えておきましょう。
文字型<->整数型の変換で、char - ’0’を利用するのも頻出なので、是非覚えましょう。

　ちなみに、提出コードにはU->L,U->D,L->U,…というように、すべての場合の変換を書き下したものと、一度すべて小文字の単語に変換した後、結合する際に変換を施すものがありました。
個人的には後者の方をおすすめしたいです。
前者のような個々の場合分けが増えると、複雑になったり、コーナーケースが怖くなりますので、より一般化された後者のような解き方が選べるなら、そちらがよいと思います。

C. Red and Black

　二次元平面においてスタート地点(‘@’)から始め、隣接する上下左右のマスを辿り続け、赤マス(‘#’)を通らずに行けるマスの数を求める問題。

　典型的な探索問題です。探索は深さ優先探索(DFS)でも幅優先探索(BFS)でも構いません。
今回は、再帰関数の練習としてDFSを想定解とします。

　入力をchar board[H][W]などに受けたら、board[y][x]=’@’についてdfs(y,x)を答えとします。
dfs(y,x)は、マス(y,x)から到達可能なマスの数を返す関数です。
これは、(y,x)に隣接する4マスから到達可能なマスに、(y,x)の1マスを足した値ですので、
dfs(y-1,x) + dfs(y,x+1) + dfs(y+1,x) + dfs(y,x-1) + 1とすればよいです。
ただし、マス(y’,x’)が’#’であったり、範囲外であるときは0を返しましょう。
また、一度訪れたことのあるマスを重複して数えないような処理が必要です。
今回の場合、訪れたマスを’#’で上書きすることで解決できますが、盤面の状態を変更したくない場合もあります。
そういうときは、盤面とは別にvisit[H][W]のような配列を用意し、すでに訪れた場合は1を、訪れていない場合は0を値に取るようにする、などとすればよいです。
全てのマスについて、訪れる回数はたかだか一回なので、オーダーはO(H×W)となります。

　また、補足として、この問題に限ったことではありませんが、プロコンで二次元グリッド平面を扱うときには注意が必要です。
二次元配列に要素を格納するとき、入力の関係からもgrid[高さ][幅]とすることが多いですが、これを数学的な座標で表そうとすると(y,x)となります(上記でも暗黙としてこの表記を用いていました)。しかし、数学では座標を(x,y)と書くのが一般的で、混同しやすいです。
さらに、二次元配列では左上が(0,0)、右下が(y,x)ですが、数学では(0,0)が左下、(x,y)が右上で、上下関係も逆です。上に進みたいときはyの値を減らさなければいけない点も複雑なので、取り扱いには十分注意しましょう。

D. Cicada

　二次元平面を(0,0)から(H-1,W-1)まで最短経路で移動する。各マスに何匹かいる蝉にできるだけ遭遇しないようにするとき、出会う蝉の数の最小の数を求める問題。

　これも典型問題で、想定解法は動的計画法(DP)です。
最短経路でゴールに辿り着くためには、必ず右か下に進まなければなりません。
逆に言えば、あるマス(y,x)に到達するとき、左のマス(y,x-1)か上のマス(y-1,x)を通らなければなりません。
ということは、(y,x)に至るまでの最小の蝉の数は、(y,x-1)までの最小の数と(y-1,x)までの最小の数のうち小さい方に、(y,x)にいる蝉の数を足したものとなります。
これを(0,0)マスから始めて左から右へ、上から下へ求めていくと、(H-1,W-1)での最小の蝉の数が求まります。

　動的計画法は、
1. ある状態における解が一意に定まる
2. ある状態から別の状態に移る規則が定まる
3. 状態同士の順序関係(どちらから先にもとめるか)が定まる
とき、1つ1つの状態の解をメモしておくことで、複数回同じ状態の解を求めるときでも何度も計算しなおすことを防ぎ、効率的な計算を行うアルゴリズムです。
　今回の場合、
1.あるマスに至るまでの最小の蝉の数は一意に定まる
2.あるマスからは右、もしくは下のマスに移る
3.より左、もしくは上のマスから順に求める
とわかるため、動的計画法が使えます。
動的計画法のオーダーは基本的にO(状態数×ある状態から遷移できる状態の数)となるため、今回はO(H×W×2)= O(H×W)となります。

E. Carden Lantern

　ちょうちんで灯された道だけですべての史跡を訪れられるようにするとき、必要になるちょうちんの数を最小化する問題。

　町を頂点、道を辺とすることで、グラフ構造に落とし込めます。
このとき、ある道に必要になるちょうちんの数をその辺のコストとすると、
すべての頂点を連結するように辺を選んだときのコストの和を最小化すればよいことになります。
すなわち、このグラフの最小全域木(最小スパニング木、MST)を求める問題となります。
MSTを求めるアルゴリズムとしてはクラスカル法とプリム法が有名で、
どちらもO(|E|log|V|)です。どちらでも構いません(僕はクラスカル法で実装しています)

　この問題はMST、およびそれを求めるアルゴリズムを知っていればそれを実装するだけなので、知識があるかどうかを問う問題といってもよいです。覚えておきましょう。
プログラミングコンテストチャレンジブック2-5節に実装を含め説明が掲載されています。

F. Circle and Points

　平面上に点在する点を半径1の円で少しでも多く囲もうとするとき、最大いくつの点を囲めるかを求める問題。

　言うまでもなく幾何の問題で、明らかに今回のセットで最難の問題です。
幾何の問題は発想の部分でも数学色が強く、実装面でも独特の知識を要求され、また浮動小数点演算による誤差まであり、競技プログラマの中でも苦手だったり嫌いだったりという人が最も多いジャンルの１つです。
しかし、この問題は幾何の中ではそこまで難易度の高い問題ではないと思いますので、是非理解しておきましょう。

　まずはアルゴリズムについての解説です。

　実際に円を描いてみて、その中に何個の点が含まれるのか調べればよさそうですが、
離散でなく連続である平面の点全てを中心にして試してみる、というのは当然不可能です。
よって、中心とする点の候補を減らす工夫が必要となります。
ここで、１つの点だけを囲むのは簡単にできるので、2つの点を囲むことを考えます。
２つの点の距離が2よりも離れていると円で囲むことは出来ませんが、2以下であれば囲むことが出来ます。
このとき、この2点を囲みつつ他の点を最大限囲むにはどうすればよいでしょうか？
２点が円周に重なるようにギリギリにするのがよいように思えます。
下図を見ると、少しでも右にずらすと2点が囲めなくなり、逆に左にずらすと、右側の点が囲めなくなります。

もちろん、左にずらせば右側から外れる点よりも多くの点を囲むことが出来る場合もあります。しかし、結局そのような点に関しても、それを同様に円周上に乗せるようなギリギリの囲み方をする方が多くの点を囲めます。
すなわち、すべての2点の組合せについて、2点が円周上にあるような円を描いて、囲んでいる点の数を数えて最大値を求めればよいです。
任意の２点の組１つにつき、それらを円周上におくような円はたかだか2つなので、2点の組合せの数n(n-1)/2から、n(n-1)個の円だけ調べればよいことになります。
ある点が円に囲まれているかどうかは、その点と円の中心との距離が1以下かどうかを調べればよいので、すべての点について調べると１つの円につきn回かかります。
よって、全体でO(n^3)となります。nはたかだか数百なので、十分間に合いそうです。

　しかし、簡単に「2点を円周におく円を求めればよい」と言いましたが、実際どうすれば求められるでしょうか？作図しながら考えてみましょう。

2点A(xa,ya)とB(xb,yb)がわかっているとき、それを円周上に持つ円Oの中心(x,y)を求めたい、というのが今回の問題です。
２点が円周上にあるということは、中心からの距離が半径と等しいということです。
すなわち三角形OABはOA=OBの二等辺三角形となるので、OからABへの垂線との交点をMとすると、は、OMはABを二等分するためMはABの中点となり、
M=( (xa+xb)/2 , (ya+yb)/2)とわかります。
また、∠OMA=90°なので、ベクトルABの単位法線ベクトルに|OM|を掛けたものの始点をMに合わせると、Oの座標がわかります。

　実装について以下でさらに解説します。
幾何の基本はベクトルです。
C/C++にはベクトルを扱うデータ構造はライブラリとして与えられていないので、自作してもよいですし、C++のcomplex型という複素数を扱う型を代用することも多いです。複素平面を考えて利用します。

以下、僕の解答コードの一部です。

typedef complex P;

P center(P a,P b){
P m = (a+b)/2.0;
P n = (a-b)*P(0,1);
n = n/abs(n);

double x = abs(a-b)/2.0;
return m + n*sqrt(1.0 - x*x);
}

　typedefの部分は、単に何度もcomplexと書くのが面倒なだけなので、特に気にしなくともよいです。適宜補完して読んで下さい。
m = (a+b)/2.0の部分は中点mを求めています。そのままです。
n = (a-b)*P(0,1)は法線ベクトルを求めています。これは少しわかりづらいですが、ベクトルa-b = (x,y)とおくと、(x+yi)*(0+i) = (-y + xi)となり、すなわちベクトル(-y,x)を表します。
つまり、a-bを反時計回りに90°回転したものとなり、これは法線ベクトルとなります。
n = n/abs(n)は単位法線ベクトルを求めています。nの大きさで各座標値を割ることで標準化しています。
１つ飛んで、最後の行は、点mを始点とし、単位法線ベクトルに|OM|を掛けたものの座標を求めています。|OM|は三平方の定理より、sqrt(半径^2 - |AM|^2)に等しいため、最後の行の式となります。xは|AM|を表しています。

　幾何は一見しただけではなにをやっているのかわからないような独特の実装や知識が用いられることが多いため、慣れることはもちろんですが、よく使うものはテンプレ化して持っておくのがよいでしょう。今回は用いませんでしたが、内積や外積、３点の位置関係、線分の交差判定など、よく問われるものは他にも数多くあります。
また、誤差にも注意しましょう。例えばif(a+b==1.0)のような判定を使っていると小さな桁の誤差によりWAが出る可能性が高いです。小さな定数EPSなどを用いてif(abs(a+b-1.0)

大学の授業でICPC対策 - Competitive Programming Advent Calendar

　若輩者ながらCompetitive Programming Advent Calendarに参加させていただきます。
僕のは体験談のようなものなので、気軽に読んでください&長文で申し訳ないです。
今回は大学の授業としてICPC国内予選を突破するための対策を行ったときの話をしようと思います。

経緯

　僕は大学３年の時に初めてプログラミングコンテストというものを知りました。これがACM−ICPCです。2年の授業でC言語によるプログラミングを習い、「プログラミング面白い！」と思っていた僕は、すぐさま参加を決めました。結果的にその年(2010年)のICPC国内予選を突破し、アジア地区予選に進出することができたのですが、これはほぼすべて先輩の能力の賜物といってよい状況で、先輩がいなくなってからも予選を突破できるか不安に思っていました。

　そんな中迎えた3年後期、必須科目の中にコンピュータサイエンス実験2という授業がありました。これは「数人でチームを組み、課題に対する小研究を行う」というものです。この「課題」は教員から与えられたいくつかのものから選ぶのですが、最後の一枠に「自由課題」というものがあり、この枠では「顧問となる教員が見つかるなら、何をやってもよい」のです。他の課題を担当していなかったICPCに積極的な先生が「ICPC対策なら担当になってもよい」と(おそらく冗談くらいのつもりで)言ったのを聞き逃さなかった僕は、すかさず有志を3人集めてICPC対策をテーマとして申請し、次年度も国内予選を突破すべく対策を始めました。

前半

　とりあえず最初に始めたことは、プログラミングコンテストについて書いているWebページ・書籍などをしらべ、情報をまとめることです。この時の情報整理には「KJ法」というのを使いました。これは、とにかく断片的でもいいからキーワードのようなものをメモしまくって、あとでそれをグループ化して階層構造や関係付けを持たせることで、全体像を掴むというものです(たぶん)。先生はこのKJ法をやたらとプッシュしまくっていました。というのも、「たぶん成果が微妙になるだろうから目立つ手法とか使っとくか」的なノリだったんだろうと思います。僕はガチで国内予選突破したかったのでそんなのはどうでもよいと思いつつも、単位が恋しいのでやりました。もちろんこれをやったおかげで乏しかったプロコンの知識がついたのでとても感謝しています、はい。

　こうした調査の結果、重要な要素として、「アルゴリズム」「デバッグ」「チーム戦略」などが浮かび上がってきました。この辺で最終目標として「マニュアルを作る」という形を意識し始めました。実験の期間中に国内予選はないですし、成果としてあげられる「もの」がそれくらいしかないだろうと思ったので。しかしながら、マニュアル系の書籍として既に「プログラミングコンテストチャレンジブック」(通称・蟻本)という神本を始め、多くの書籍やWebページが存在するので、これらとの差別化を図らなければなりません。そこで我々は心を鬼にしてこれらをdisりつつ、「自コースから国内予選突破者を増やすことに特化した対策」を行うことで新規性を訴えました。少し具体的に説明すると、

  • 国内予選の傾向を分析し、必要となるアルゴリズムの重要度・優先度を与える
  • コースで授業を行っている内容については、説明を軽くし冗長性をなくす
  • 学科履修言語のCでの実装のみを考える

などです。その他、

等も加え、実用性を向上させる試みも考えました。

中間発表

　実験2では、11月の末に中間発表があります。ここまでの研究の進捗を報告し、先生方に意見をもらってこれからの研究に活かします。以下に中間発表の内容の一部を示します。


　これは過去の国内予選で出題された問題のカテゴリの構成比を分析した図です。右の「突破最低ラインの問題」とは、各年の予選結果から突破に必要な問題数を調べ、他のサイトの評価を参考に簡単な問題からその数ぶんだけ選んだものです。図をみると、全体として幾何やグラフの出題は多いですが、突破に最低限必要な問題に的を絞ると、これらはほとんど出題されていません。これを理由に僕らは、「構文解析や幾何、グラフなんてほっといて、探索やシミュレーションをきちんと解けるように勉強しろよ、JK」と主張しました。異論は認めます。

　ここで教授陣にはいろいろつっこまれましたが、一番印象に残ったのが「もっと問題解け」でした。当時一番解いていた僕でさえ30問程度、他はみんな一ケタ台という有様で、もっと解いた上で考察しなさい、という至極当然の話だったので、後半はそこから始めました。

アジア地区予選

　実験期間中に国内予選はないですが、なんとか参加できたアジア地区予選は中間発表後にありました。アジア予選の体験を話しだすと脱線するのでここでは深く触れません。とりあえずむっちゃ楽しかったです。実験の観点からすると、ここで成果が出ると箔がついていい感じだったのですが、残念ながら2問正答の順位なしで悔しい結果となりました。しかし、実験的にも個人的にも対策の必要性をより強く感じるきっかけになったので、良い経験だったとも思っています(事実この後の春休みからTopCoder, codeforcesなどを始めたり、約一年間でAOJの問題を400問程解くなど、それまでとは比べ物にならないくらいプロコンに浸かりだしたので)。この時、chokudaiさんとかimoさんとかusagiさんとかから軽くお話を聞いたり(皆さんはまず間違いなく忘れていると思います)して、勝手に対策の方向性の参考にしました。

後半

　後半は先に定義した「突破最低ラインの問題」をひたすら解くところから始めました。このとき、起きたバグ・間違いをすべてメモすることで、デバッグの章にも活かせるようにしました。で、問題をあらかた解き終わったころにはもうマニュアルを書き始めないと間に合わない状態だったので、すぐさま執筆作業に移りました。章立ては、

  1. ACM-ICPC概要
  2. 注意事項
  3. デバッグ
  4. 傾向分析
  5. 対策
  6. ライブラリ

　としました。デバッグは自分たちが問題を解いた経験を反映させました。対策の部分では、傾向分析の結果から、「シミュレーション」「探索」「数論(素数)」「動的計画法」を取り扱う事にしました。動的計画法が入っているのは分析よりも、個人的見解やimoの人たちが言ってたから、というのが大きいのはここだけの話です。実験メンバーにも内緒です。ライブラリには「素数(エラトステネスの篩など)」「リスト」「キュー」「スタック」(CだけだとSTLがないので)などを載せました。

二年生向け説明会

　最終発表の前に、二年生向けのACM-ICPC勧誘会があったので、そこで講演するとともにマニュアルの評価をしてもらいました。「国内予選で問題たくさん解くと酒おごってもらえるよ」とか、「アジア予選ではSake Challengeあるよ」とかネタを挟みましたがよくよく考えると未成年もいるはずなので危なかったです。あ、ちなみにスベりました。貴重な意見も多くもらえたのですが、時間がなかったためすべてには手をつけず、誤字脱字を直したり、根本的にマズイところを修正したりに留めました。

最終発表

　中間発表で傾向の話はしたので、最終発表では主に対策・ライブラリ周りの話を発表しました。アジア予選体験談も交えて尺を稼ぎました。コートをバッと脱いでICPC-Tシャツ(水色)を見せびらかしたりしました。あ、ちなみにスベりました。対策部分はトピック1つにつき例題を1つあげて、それを解説しつつ、考え方やそのカテゴリに分類するときの見分け方などを説明する形式をとりました。傾向がわかり、その問題を実装する能力が上がっても、判別する能力がないと話にならないと思っていたので、そこは少し意識しました。

国内予選2011

　時は流れて2011年6月、国内予選。敗北しました。大敗北です。つまり、このマニュアルでは不十分だったということです。まあそもそもがこのマニュアルは「傾向を分析して優先度を示す」部分がメインといっていい内容で、「ここやればいいよ、ってとこは教えるからあとは頑張って」となるので、これだけで十分なはずはないのですが。僕は危機感を持っていたのですが、チームメイトは「結構問題解いたしいけるやろ〜」みたいな油断があり、見事にやられました(一番戦犯なのはD問題が解けなかった僕ですが)。しかし、2011の問題は素数1問、探索(バックトラック)1問、DP2問の計4問が出題されていて、4問解けば突破の可能性が十分あったので、分析部分は通用するものだった、と虚勢を張っておきます。

感想

　実験は、単純に問題をいっぱい解けたので俺得でした。コンセプトをはっきりさせたのも、全体がすっきりしてよかったと思います。マニュアルの内容について細かく見ていくと、

  1. デバッグ部分はふとしたときに見返してみるのがむしろいいかな、という感じで、初心に返れますし良いです。
  2. 傾向分析はかなり役に立つ知見が得られたと思いますし、今後も使えると思うのでよかったです。
  3. 対策部分は判別法のところは重要だと思いますが、問題解説はぶっちゃけeditorialとか競技プログラマのblogを見ながらもっと問題数をこなすようにした方がいいと思うので微妙な感じではあります。
  4. ライブラリ部分はC++に切り替えてSTLを教えた方が効率がいいだろうと(今は)思っているので、あまり価値はないのかなあと思います。

　総評としては、マニュアルを作った、ということよりもマニュアルを作ろうとするために必要最低限の知識を得た、プロコンに慣れたことが僕の中では収穫です。
　来年までにまた、今度は「チームメイトとの知識共有、およびグラフ・幾何などのライブラリ」を意識してマニュアルを作りたいなと考えています。次こそは必ず国内予選を突破してみせるので、参加資格のある皆さん、お互い頑張りましょう＆アジア地区予選で会いましょう！

以上です。拙文・長文失礼しました。
明日以降もみなさん僕なんかより面白い記事をたくさん書いて下さるので、お楽しみに！
僕もとても楽しみです〜