def yasuharu519(self):

日々の妄想

Facebook Hacker Cup 2013 Round1

感想

プログラミングの練習も兼ねて、Facebookプログラミングコンテストが開催されるということで、参加してみた。去年も参加しようとしてたけど、去年は気づけば終わってた。Facebookというと、映画「ソーシャル・ネットワーク」でのハッカーチャレンジみたいな、がちがちのむずかしい問題ばっかりなイメージだったので、けっこうビビって参加。

結果的には、GoogleCodeJamみたいな、テストケースをローカルにダウンロード、ローカルで出力した結果を提出という流れだったので、言語の縛りなどもなく、また、問題自体もわけわからん問題ばっかりという感じではなかった。ただ、CodeJamと違って、間違った答えを提出したらペナルティを受けるってだけではなくて、各問題1回しか提出できない。そのため、簡単なテストケースでコードが通ることを確認しても、ダウンロードしたテストケースの値が想定よりも大きく、計算が終わらないってパターンも多かった。

Round1の結果は945位。1問目はPythonで書いて見事に計算終わらないパターンに陥って断念。2問目はなんか簡単に書いてしまったけどまず解釈が間違ってるみたい。これは他の人の回答もみて、答え合わせをあとでする。3問目は1問目の失敗から慎重に解く。最終的に3問目だけあってるという結果に。3問目は明らかにメモリ不足になるのがみえみえだったので、最初からいろんな方法を試したのが良かったみたい。QualificationRoundもあったけど、それも後でまとめる。

#1: Card Game

N枚のカードからK枚を取り出すときに、すべての取り出し方に対して、一番強いカードの番号の和を求める問題。

最初、Pythonのitertoolsのcombination関数とmaxを使って、愚直に計算するようにした。その結果ダウンロードしたテストケースの計算が終わらず、提出終了。数十分ほどしかたってなくて、1問目を逃す結果に。

あとから解法思いついてC++で書きなおしたやつが下のやつ。sortして順番に組み合わせの数をかけて行ったら終わり。ただ、普通に足しあわせて行くとバッファオーバーフローするみたいなので、適宜mod計算をしていく必要があるみたい。(掛け算のmodがmod同士の掛け算で求められるかは不安)

#2: Security

決められたchunkに分解して、複合できるか見るやつだと思って、場合分けみたいなのを作った。サンプルは通ったし、いけるかなーと試したのが下のやつ。どうやら間違ってるみたいなので、あとで確かめてみる。

#3: Dead Pixels

W×Hの大きさのディスプレイの決められた場所にピクセルの欠けがあり、ピクセル欠けを含まないP×Qの長方形がいくつ取れるかを数え上げる問題。

まずはピクセルそれぞれが配列で準備できたら簡単だなーと思ったので、W, Hの大きさを2次元配列で表現できるか確かめた。結果、エラーで強制終了となることを確かめた。そのため、他の方法をのそのそと考えだす。

この形の数え上げ、なにか見たことあるなーと思って、imosさんのいもす法(http://imoz.jp/algorithms/imos_method.html)を思い出す。いもす法は、多次元の累積和を簡単に求める方法で、これを使用することにする。欠けピクセルの座標がもとまった際に、そのピクセルを右下角に含むようなP×Qの大きさの長方形を考え、その長方形の左上角(x, y)に-1を与える。その後、(x+P, y)に+1, (x, y+Q)に+1, (x+P, y+Q)に-1を与える。これにいもす法にて書かれているように計算をしていくと、0の値が与えられているところが、欠けピクセルを含まずにP×Qの大きさの長方形をとれる部分だということがわかる。

実際は一気に数え上げてしまうとやはりメモリ不足となってしまうので、あるx一列分の配列だけ用意してDPのように0かそうでないかを確定していった。

ゆっくりやったために時間はかかったものの、なんとか正解で、全問不正解は防ぐことができた。

最後に

いもす法すげ