Round1programming感想プログラミングの練習も兼ねて、Facebookのプログラミングコンテストが開催されるということで、参加してみた。去年も参加しようとしてたけど、去年は気づけば終わってた。Facebookというと、映画「ソーシャル・ネットワーク」でのハッカーチャレンジみたいな、がちがちのむずかしい問題ばっかりなイメージだったので、けっこうビビって参加。結果的には、GoogleCodeJamみたいな、テストケースをローカルにダウンロード、ローカルで出力した結果を提出という流れだったので、言語の縛りなどもなく、また、問題自体もわけわからん問題ばっかりという感じではなかった。CodeJamと違って、間違った答えを提出したらペナルティを受けるってだけではなくて、各問題1回しか提出できない。そのため、簡単なテストケースでコードが通ることを確認しても、ダウンロードしたテストケースの値が想定よりも大きく、計算が終わらないってパターンも多かった。Round1の結果は945位。1問目はPythonで書いて見事に計算終わらないパターンに陥って断念。2問目はなんか簡単に書いてしまったけどまず解釈が間違ってるみたい。これは他の人の回答もみて、答え合わせをあとでする。3問目は1問目の失敗から慎重に解く。最終的に3問目だけあってるという結果に。3問目は明らかにメモリ不足になるのがみえみえだったので、最初からいろんな方法を試したのが良かったみたい。QualificationRoundもあったけど、それも後でまとめる。GameN枚のカードからK枚を取り出すときに、すべての取り出し方に対して、一番強いカードの番号の和を求める問題。最初、Pythonのitertoolsのcombination関数とmaxを使って、愚直に計算するようにした。たってなくて、1問目を逃す結果に。あとから解法思いついてC++で書きなおしたやつが下のやつ。sortして順番に組み合わせの数をかけて行ったら終わり。普通に足しあわせて行くとバッファオーバーフローするみたいなので、適宜mod計算をしていく必要があるみたい。Security決められたchunkに分解して、複合できるか見るやつだと思って、場合分けみたいなのを作った。サンプルは通ったし、いけるかなーと試したのが下のやつ。間違ってるみたいなので、あとで確かめてみる。PixelsW×Hの大きさのディスプレイの決められた場所にピクセルの欠けがあり、ピクセル欠けを含まないP×Qの長方形がいくつ取れるかを数え上げる問題。Hの大きさを2次元配列で表現できるか確かめた。結果、エラーで強制終了となることを確かめた。そのため、他の方法をのそのそと考えだす。この形の数え上げ、なにか見たことあるなーと思って、imosさんのいもす法(http://imoz.jp/algorithms/imos_method.html)を思い出す。いもす法は、多次元の累積和を簡単に求める方法で、これを使用することにする。y+Q)に-1を与える。これにいもす法にて書かれているように計算をしていくと、0の値が与えられているところが、欠けピクセルを含まずにP×Qの大きさの長方形をとれる部分だということがわかる。実際は一気に数え上げてしまうとやはりメモリ不足となってしまうので、あるx一列分の配列だけ用意してDPのように0かそうでないかを確定していった。やったために時間はかかったものの、なんとか正解で、全問不正解は防ぐことができた。(1)月別アーカイブはてなブログをはじめよう!yasuharu519さんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。