全国高等専門学校プログラミングコンテスト舞鶴大会
(この記事はCompetitive Programming Advent Calendarの24日目の記事です。)
日本全国の競技プログラマのみなさん、こんばんは！
今日はTopCoder SRM→Xmas Contest→Codeforcesとコンテストが目白押しでしたが、調子のほどは如何でしたか？
頭をフルに使った後はこの記事でも読んで休憩をしていただくと良いかと思います（ ＾ω＾）
さて、突然ですが、先日行われた高専プロコン舞鶴大会の競技部門において、私@natrium11321、@nikollson、@grrifon_zeroの3人による久留米高専チームが優勝を飾ることができました！
この記事では、高専プロコンの説明、今回の競技についての久留米の解法、競技全体を通しての所感について、簡単ではありますがまとめさせて頂こうと思います。諸事情あり時間があまり取れず文章の推敲が行えていないので、全体的に読みづらいかと思いますが、ご理解とご容赦の程宜しくお願いします。
高専プロコンとは？
皆さんは高専プロコン(以下、プロコン)という大会をご存知でしょうか。恐らくここを見ている高専生ならば一度は耳にしたことがあるでしょうし、選手として出場した経験のある人も多いと思います。反対に高専生になったことのない方には馴染みの薄い大会かも知れません。
高専プロコンとは全国高等専門学校プログラミングコンテストの略称で、まぁ簡単にいうとロボコンのプログラミングバージョンです。毎年10月中頃に日本のどこかの高専が主管校となって開催されます。出場権を持つのは高専生(本科・専攻科)のみですが、国際大会が併催されるので外国の大学も参加します。開催回数も22回を数え、高専生対象のコンテストとしてロボコン・デザコンに並ぶ知名度を持っていると言われています[要出典]。
プロコンは大きく以下の3つの部門に分かれています。
自由部門
5人以下のチームで自由にソフトウェアを開発し、デモンストレーションやプレゼンテーションを行なって審査します。6月頃に書類による予選審査があり、それを通過した全20チームのみが本選に出場することが出来ます。1高専最大2チームです。
課題部門
基本的には自由部門と同一ですが、与えられたテーマに沿ったソフトウェアを作成する必要があります。テーマは2年毎に変わっており、去年及び今年のテーマは「旅とコンピュータ」です。
競技部門
3人以下のチームで、与えられた問題を解くプログラムやゲームAIを作る部門です。問題は4月の時点で公開されるので、10月の本選までじっくりと開発することができます。1高専1チームです。本稿はCompetitive Programming Advent Calendarの記事ですのでこの部門の話がメインとなります。
例年の競技部門
さて、ここで競技部門の雰囲気を感じ取って頂く為に、幾つか例年の競技部門の内容を紹介します。
2006年(米子大会)
640×480ピクセルのカラー画像1枚と、その画像の一部を加工した画像100枚が与えられます。加工画像は、元画像の一部を切り出し、拡大・縮小・上下左右反転・回転・色調変更を施し、ハート型に切り出したものです。ダミーも含まれています。加工画像が元画像を加工して作られたものなのか、そうであるならばどの位置を切り出したものなのかというのをできるだけ多く時間内に答えたチームが勝利となります。優勝は久留米高専でした。
2009年(木更津大会)
最大20×20の大きさの盤面が与えられ、各マスには最大8種類の色がついています。この盤面に対して、マスの頂点を中心とした、一辺が偶数の正方形の領域について、90°・180°・270°の回転操作を行うことが出来ます。出来るだけ少ない回転操作で、全ての同じ色のマス同士を隣接させたチームが勝ちとなります。例えば右図の左の状態が初期状態として与えられ、これに回転操作を施し右の状態に変えれば完成です。この大会では大阪府立高専が優勝しました。
2010年(高知大会)
一辺が20の大きさの六角形の盤面を舞台にした陣取りゲームです。6チームが同時に対戦し、それぞれ3台のコマを動かします。青いマスが水汲み場で、ここでまず水を汲んでから他のマスに配水することで自分の陣地とすることができます。配水は同じマスに複数回重ねることが出来、時間はかかりますが他のチームに乗っ取られにくくなります。自分の配水マスで閉曲線を作った場合、その内部も全て自分の陣地として数えられます。この大会は3Dのビジュアライザの完成度が非常に高く、観客もリアルタイムに楽しく観戦をすることが出来ました。優勝校は石川高専です。
決勝戦の動画
第22回高専プロコン舞鶴大会
さて、本項以降は今年の高専プロコンについて、書きたいと思います。
例年10月中頃に本選が開催される高専プロコンですが、今年は震災の影響*1で開催が12月の下旬となってしまいました。
自分は21日に舞鶴入りで、24日に帰ったのですが、ほんと舞鶴は遠いですね…。京都からさらに1時間半。久留米より少し暖かく過ごしやすいように感じました(2日目は霰が降りましたが…。)
課題内容
今年の競技部門の問題内容について簡単な説明を行います。
- 最大640×480の大きさの二値画像が2つ与えられる。それぞれ、初期画像・完成画像とする。
- 最大128×128の大きさの二値画像が最大128枚与えられる。スタンプと呼ぶ。
- 初期画像の任意の位置に任意のスタンプを"押す"ことができる。スタンプを押すと、スタンプの黒マスの位置に対応する初期画像のマスの白黒が反転する。すなわち、初期画像とスタンプを任意の位置でXORすることが出来る。
- 1×1で黒色のスタンプが必ず与えられることが保証されている。
- 競技時間は1分以上10分以下。
例えば、
この画像の左下の所に、
このトナカイのスタンプを押すと
こうなります。スタンプは画像から一部がはみ出す位置に押すことも出来ます(この場合はみ出した部分は無視されます)。
勝敗の判定は以下のようになります(nで勝敗が決まらなかった場合はn+1で勝敗を決めます)。
- 最終画像との不一致数が少ない
- 手数が少ない
- 提出時間が早い
- じゃんけん
一度の競技では2つの問題セットを解くことになります。1問目の制限時間が終了した直後に2問目が始まります。不一致数・手数・提出時間について、それぞれ2問分の合計値で上記の基準による勝利判定が行われ順位が決まります。
次節で自分たちが考え、実際本番に用いた作戦やアルゴリズムについて、本邦初公開しようと思います。
久留米高専の作戦 1. 問題分析
まず簡単な考察により、問題を簡略化します。
- 初期画像を最終画像に変えることは、初期画像と最終画像のxorを取った画像を真っ白な画像(以降「盤面」と呼びます)に変える作業に等しい。
- 1×1で黒いスタンプが必ず与えられるので、実質勝敗判定の1は考えなくて良い。特徴的なインプットでない限り手数が全く同じになることはほぼ無いので、勝敗判定の3や4もそこまで考えなくて良い。つまり、手数を最小化することのみを目的とすれば良い。
これはパンフレットを見る限り、ほとんどどのチームも行なっている方法でした。
次に、この問題の種類を2つに大別しました。
- 盤面とスタンプどちらも何かの形のシルエットである等、白黒の領域がはっきりと分かれている場合
- 盤面やスタンプのどちらか一方がノイズである場合
おそらくこの2つは問題の性質が大きく異なります。しかしインプットの作成方法が全く公開されていないので、どちらか片方に注力し他方を蔑ろにするのはあまりよくないと考えました。
本戦で用いられるインプットについて、本戦1週間程前にtwitter上では
@colun 競技練習場にある全問題が、実は本選の出題と根本的に違うんじゃないかという気がしてならない。練習場の様なノイズ的スタンプではなく、直径10ピクセルの中黒スタンプとか、アルファベットを模した大きめのスタンプとかが出題されたら、練習場の上位は、総崩れなのでは？ #procon2011
という感じの議論があり、それに対して
@natrium11321 @colun 高専プロコンの運営がアップロードしている簡易競技システムの使い方動画があるのですが、これを見るとスタンプはノイズのように見えます。 http://t.co/onU33YEd
というツイートをしてあたかもノイズ以外のインプットを想定してない雰囲気を醸し出したり
@nikollson 大きすぎるスタンプはノイズと性質が変わらないと思っている
ととんちんかんなことを言ってみたりしたのですが、実はシルエット入力は完全に想定して、対策を練っていました。
久留米高専の作戦 2. すごく小さいスタンプ対策
tokura
今回の競技では、釧路高専OBの方が作って下さった高専プロコン2011練習競技場で、競技前から多くの高専生がお互いにスコアを競い合うことが出来ました。
このうち、問題1や4のような非常に小さなスタンプしか存在しないような入力に対しては、焼きなまし法(以下SA)で解を出すようにしています。具体的には、縦5×横5の正方形のマスのビットパターン2^25全てにおいて、それを全て0にするような厳密な最短手数を幅優先探索を用いて求めます。ただしこの時正方形からスタンプがはみ出ないようにします(つまり、5×5に収まるスタンプしか使うことが出来ません)。盤面のあるランダムな5×5領域において、その領域にすでに置かれているスタンプを全て除去し、先ほど求めた厳密解をそこに当てはめ、近傍界とします。解評価は置かれているスタンプの数+黒マスの数で、後は通常のSAと同じです。この方法だと、練習競技場の問4で3000程度の解を出すことが出来ます。この解法にtokuraというコードネームをつけています*2。
sakura
tokuraを進化させた方法で、最後の解評価を置かれているスタンプの数+左上から5×5の正方形を敷き詰めてた時の手数に変えたものです。競技練習場問4で2900程度の解になりました*3。
久留米高専の作戦 3. シルエット対策
ikura
tokura→sakuraと進化した次はikuraになりました。おいしそうですね（ ＾ω＾）
ikuraはsakuraの進化というよりは、sakuraを下請けとして使うアルゴリズムなのですが、盤面・スタンプ共にシルエットが多いインプットにおいて、盤面の黒い領域にうまくスタンプを組み合わせて押していくアルゴリズムです。上下左右に微妙に動かしたり、スタンプを削除したり、別のスタンプに変える近傍界生成を用いるSAを使っています。このSAを十分に回した後、サッと貪欲法を回し*4、その後にsakuraを回します。SAを多重化する等他にも多分なんかいろいろやってると思うのですがikuraは主にnikollsonが開発したので自分はあまり詳しく知らないのです……ごめんなさい。
右の画像はikuraを回してみた(貪欲やsakuraはまだ回していない状態の)盤面です。(水色は無視して下さい)
久留米高専の作戦 4. ノイズ対策
loli
競技練習場の問11や12等の、sakuraを回せそうなスタンプが存在しない、大きなノイズスタンプが多い入力に対して強いアルゴリズムです。縦1×横22〜26くらいの長方形のすべてのパターンの厳密解をtokuraと同じ方法で求め、左上から右下方向に適用していきます。パターンを作るときは、スタンプの左上の部分のみを使い、長方形の右下にのみスタンプがはみ出るようにします。これがなんか普通に強くて、練習競技場問12で9500くらいの解が出ます。*5
mädchen
loliを進化させた解法です。幼女が少女になりました。*6
基本的にloliと同じなのですが、loliのように単純に左上から1×w (wは22から26くらい)で割り当てていくのではなく、各行について組み合わせのDPを行うようにしています。ある行について、dp[i]を、左からi番目のセルまでの手数の最小値を表す配列だとすると、dp[i]はmin dp[i-j]+(左からi-j番目のセルから、i番目のセルまでのjマスを0にする最小手数)で求まります(1≦j≦w)。当然本当の意味の厳密解には遠く及びませんが、割と改善します。競技練習場問12で8000程度になります。
あと細々とした点として
- 左上からのみ試すのではなく、「左上から1×w」「左上からw×1」「右上から1×w」…など8パターン全て試して最適値を取ります。
- 中央に大きな空白がある場合、その空白を中心として四隅に向かって埋めていくと効率が良いので、中に黒マスを含まない最大の直交凸包(通称ロリ包)を頑張って求めて良い解が出るか試します。ロリ包を求めるアルゴリズムは盤面の一辺の長さをnとするとO(n^4)のものしか思いつかず、計算に時間がかかってしまうためある条件を満たしたちょっと悪いロリ包をO(n^3)で求めて使うようにしています。
- ロリ包の四隅に向かって埋めていくアルゴリズムを1×wからw×1に変えたものも解が改善するかどうか試します。
- 本番での作戦は、まず速攻で終了するw=20の解を前述の10パターン全てについて求めて、その中で最も良かったものについてwを少しずつ大きくしていきながら順次解を作成しました。
久留米高専の作戦 5. 基本操作の高速化
盤面にスタンプを押す操作は全解法の基本です。これを高速化することはひいてはプログラム全体を高速化することに繋がります。(パターン生成に時間がかかるloli系は異なりますが…。)
マスの01をビットで管理すると1バイトに8個のマスの情報を載せることができますが、スタンプを押す操作をビット毎のループで処理するとものすごく遅いです。これを高速化する方法としてまず考えられるのは、64ビット型整数のxor演算を用いて一気にxorすることです。スタンプを押すx座標が8で割り切れない場合はビットシフトとか色々面倒なので、最初に0〜7マスだけ右にずらした画像を作成します。
64ビット整数型のxorは最初に比べて速いといえば速いのですが、まだ速度が足りません。今時のIntel CPUにはSSE拡張命令という素晴らしい命令があり、なんと128ビットのビット列に対して1命令でxorが行えます。SSEのxor命令(pxor)はSSE2で対応しているため、ほとんどのIntel CPUで動きます。1度に横に連続する128セルxor出来るということは、x座標が8で割り切れない場合でも最大で2回の命令で1行のxorを完了することができます。これを実装すると最初のループによるxorよりだいたい70倍くらい速くなりました。素晴らしいね！
次に、スタンプを押したときの黒マスの数の増減を知るという操作を考えます。これもおそらく使う機会が多いと思うのですが、黒マスの数の増減を知るにはビットのpopcountが必要になります。ビットのpopcountはAND演算とかシフト演算を駆使した闇魔術的コードが知られていますが、実はSSE4.2の中に64ビットのpopcount命令が含まれています。つまりたったの1命令で64ビットの中の1の数を知ることができるので、具体的な速度比は計測していませんがものすごく速いです。しかしSSE4.2はCorei7系以降のCPUでしかサポートされていないので、i7系のCPUを搭載したPCを使う必要があります。
その他OpenMP使って並列化したりとかいろいろしました。L3キャッシュは全CPUで共通なのが嫌ですね;X
久留米高専の作戦 6. 人力操作
人力で解きやすいインプットが出るかもしれません。その場合に人力で解くチームに負けてしまうことが考えられます。
これを憂慮した久留米高専チームは人力ソルバーを開発し、最強人力選手TKNGを養成しました。これにより練習競技場の問13や14において驚異的に手数が少ない解を手動で生成することが可能となりました。
競技本戦
今回の競技は、(1日目)予選→(2日目)準決勝→決勝 という順番でした。結果から言うと、久留米チームは全ての競技において1位*7をとり優勝することが出来ました。
実際に競技を行なって自分が最も驚いたことは、与えられるインプットが盤面・スタンプ共に全てノイズ形式だったことです。他の高専は、競技練習場の問4のようなスタンプがとても小さいインプットに対して強かったり、そのようなインプットでないと計算時間が爆発するような解法を使っていたところがほとんどだったようでした。PCを2台まで持ち込むことができるので、片方のPCでikuarを回しもう片方のPCでmädchenを回すという作戦を取っていたのですが、mädchenが火を吹いて優勝に導いてくれました。可哀想なikura…(と盤面を目の前に呆然としていたTKNG)。
決勝戦のustreamの録画はこちらから見ることができます。一問目(「絆」の文字)の久留米の修復手順が若干変なのは、中央に大きなロリ包を作り、そこから四隅に向かって修復を行なっている為です。
最終的にloli系と同じような方針で解いていたのは久留米、ハノイ、宇部の3校だけだったように思います(有明はよくわかりません)。ハノイや宇部に対する久留米の差はやはりloliとmädchenの差に尽きると思います*8。
感想
元々今回の高専プロコン競技部門のモチベーションは前年度の競技部門で準々決勝敗退したところから始まります。前年度の問題は前述の水撒きゲームだったのですが、割と強い(と思っていた)プログラムを本戦に投入して1回戦快勝したのに準々決勝でまさかの敗北を喫してしまいました。今考えるといろいろと反省するべき点はあるのですが、翌年(=今年)優勝したいという強い気持ちを明確に持ったのはこの辺が理由だと考えています。
じゃあ問題が公開されてから必死にやったのかと言われるとそうでもなくて、実際結構やり始めたのは11月に入ってからだったりします。もちろんそれ以前にも問題の分析等は行なっていたのですが・・・。
なにはともあれ、リベンジを果たすことが出来非常に嬉しいく思います。
以下に、私から見た今年の問題の良い点と悪い点について箇条書きにしてみました。
- 良い点
- 他のチームに集中的に妨害されない。強いプログラムを組めば高い確率で結果に反映される。
- 練習用サーバ等が積極的に公開されており、本番に近い環境を構築し動作テストを行うことが出来た。
- 悪い点
- 入力の作成方法が公開されていない。勝ちを確実に取りに行くには様々な種類の入力に対応する必要が生じ、開発期間がいたずらに伸びる。
- 観客から見て去年のような躍動感がない。
- ルールを簡単に説明しにくい。
- フルサイズの問題セットが決勝でも出ない。制限時間が1〜10分ならば、決勝では10分の問題を出題するべきだと思う。
おわりに
これを見ている出場経験のない高専生の方は、来年是非挑戦してみましょう。「私ちょっと競技系苦手かも…」「マラソンが苦手でなにも出来ません」と思っている方もいるかも知れませんが、高専プロコン競技部門は開発期間が非常に長いことが特長です。実に半年の期間があれば最初の能力差など完全に覆ってしまうことも考えられます。
また出場経験のある高専生の方は、来年も是非出場して、自分と優勝争いしましょう。
高専生以外の方は、来年は10月に有明高専*9で開催予定なので、是非ustream等で観戦して頂けると嬉しく思います。
それでは、主催の高専プロコン実行委員会の方々、舞鶴高専の方々、一関高専の先生方、練習競技場を提供して下さった釧路高専OBの@kasahara716さん、その他応援して下さった方々へ感謝の意を示しつつ、本稿の締めくくりとさせて頂きます。
ご精読ありがとうございました。
*1:元々今年の高専プロコンの開催地は一関でしたが、こちらも震災の影響で舞鶴に変更になりました。
*2:ドグラ・マグラが語源…らしい(nikollson命名)。
*3:語源は謎。
*4:時間がやばいときは、スタンプと盤面の黒濃度からそこにスタンプを押したときに減る黒マスの数の期待値と標準偏差を求め、中心極限定理に従いこれが正規分布していると仮定し標準化変換して閾値と比較したりして枝刈りします。
*5:loliって名前だけどマリオのスター状態で力押しで突っ切っていく感じで全然loliっぽくないよねむしろgoriだよね by nikollson
*6:ちなみに、さらに改良アルゴリズムが出来る場合にはloli→mädchen→woman→babaaと進化する予定でした。babaaにならなくてよかったね。
*7:1回戦第6試合の1問目は、久留米は39手で1位だったのですが、タッチの差で沖縄が38を出せたものの時間内に送信することが出来なかったようです。
*8:宇部は1日目の夜に久留米の解法を研究して、1晩でloliと同じようなコードを組み上げ全体順位第3位まで上り詰めたそうです。すげぇ。
*9:久留米から電車で30分ほどの場所です。
FizzBuzzライブラリ
twitterでFizzBuzzが書けないプログラマがどうのこうのという話題を目にしたので、日本のどこかにいるFizzBuzzが書けないプログラマさんの為に、FizzBuzz用のC++ライブラリを作ってみました。
ヘッダ(FizzBuzz.h)とソース(FizzBuzz.cpp)があるだけだから簡単にプロジェクトに追加できるよ！
使い方は下の方にありますです。
コード
FizzBuzz.h
#ifndef _FIZZBUZZ_H_ #define _FIZZBUZZ_H_ #include <map> #include <string> #ifdef __GNUC__ #define NONNULL __attribute__((nonnull)) #else #define NONNULL #endif class FizzBuzz : public ::std::map<int, ::std::string> { public: ::std::string& operator()(int n, ::std::string& str)const; ::std::string operator()(int n)const; char* operator()(int n, char* str)const NONNULL; }; #endif
FizzBuzz.cpp
#include <cstdio> #include <cstring> #include <sstream> #include "FizzBuzz.h" using namespace std; string& FizzBuzz::operator()(int n, string& str)const { bool added = false; for(const_iterator itr=begin(); itr!=end(); ++itr){ if(n % itr->first == 0){ if(added) str += ' '; else added = true; str += itr->second; } } if(!added){ stringstream sstr; sstr << n; str = sstr.str(); } return str; } string FizzBuzz::operator()(int n)const { string str; return operator()(n, str); } char* FizzBuzz::operator()(int n, char* str)const { if(str == NULL) return NULL; string s; operator()(n, s); strcpy(str, s.c_str()); return str; }
使い方
例えばこう
#include <iostream> #include "FizzBuzz.h" using namespace std; int main() { FizzBuzz fb; fb[3] = "Fizz"; fb[5] = "Buzz"; for(int i=0; i<=20; ++i){ cout << fb(i) << endl; } return 0; }
出力はこう
Fizz Buzz 1 2 Fizz 4 Buzz Fizz 7 8 Fizz Buzz 11 Fizz 13 14 Fizz Buzz 16 17 Fizz 19 Buzz
fb[n] = nの倍数の時に出力させたい文字列
これを最初に設定して、fb(n) とすれば文字列がstring型で返ってきます。
mapを継承しているので、clearするとかイテレータ回して何を設定したのかを確認するとか、色々出来ます。
これであなたも今日からFizzBuzzマスターだね！(
ICPC2011国内予選
team:IkannoI Mk-Iで参戦していました。
A
素数がどうのこうのという問題だったらしいですが、チームメイトに任せてたので自分は見てません。
1発AC。この段階で全体の3位だったらしいです。
#include <cstdio> #include <vector> #include <algorithm> #include <string> #include <map> #include <set> #include <queue> #include <cstring> #include <deque> #include <cstdlib> #include <stack> #include <cmath> #include <iostream> using namespace std; #define reep(i,f,t) for(int i=f ; i<int(t) ; ++i) #define rep(i,n) reep(i, 0, n) typedef vector<int> vi; typedef vector<vi> vvi; typedef pair<int,int> pii; int main() { vector<int> prime(1000000, 1); prime[0] = prime[1] = 0; reep(i, 2, sqrt(1000000)){ if( prime[i] == 1 ){ for( int j = i*2; j < 1000000; j+=i ){ prime[j] = 0; } } } int n; while(scanf("%d",&n), n!=0){ int cnt = 0; for( int i = n+1; i <= 2*n; ++i ){ cnt += (prime[i]==1?1:0); } printf("%d\n", cnt); } return 0; }
B
チームメイトがAを解いてる裏でペーパーコーディングしてました。
最初は開カッコの最後の1文字だけ保存しておけば大丈夫かなと思っていたんですけど
ペーパーコーディングしているうちにstackにしないと駄目だなーと気づきました。
チームメイトにその旨を伝えて1発AC。この段階で5位くらい。
#include <cstdio> #include <vector> #include <algorithm> #include <string> #include <map> #include <set> #include <queue> #include <cstring> #include <deque> #include <cstdlib> #include <stack> #include <cmath> #include <iostream> using namespace std; #define reep(i,f,t) for(int i=f ; i<int(t) ; ++i) #define rep(i,n) reep(i, 0, n) typedef vector<int> vi; typedef vector<vi> vvi; typedef pair<int,int> pii; int main() { string str; while(getline(cin, str), str!="."){ stack<char> s; bool flag = true; rep(i, str.size()){ if( str[i] == '(' || str[i] == '[' ){ s.push(str[i]); } if( str[i] == ')' ){ if( !s.empty() && s.top() == '(' ){ s.pop(); } else{ flag = false; break; } } if( str[i] == ']' ){ if( !s.empty() && s.top() == '[' ){ s.pop(); } else{ flag = false; break; } } } if( flag && s.empty() ){ puts("yes"); } else{ puts("no"); } } return 0; }
C
問題の意味を理解するのに5分ほどかかりました。
盤面のサイズが小さく、電極に接続されているのが左上のパネルで固定だったので全探索するプログラムを書きました。
少しだけバグにはまった…。
#include <cstdio> #include <vector> #include <algorithm> #include <string> #include <map> #include <set> #include <queue> #include <cstring> #include <deque> #include <cstdlib> #include <stack> #include <cmath> #include <iostream> using namespace std; #define reep(i,f,t) for(int i=f ; i<int(t) ; ++i) #define rep(i,n) reep(i, 0, n) typedef vector<int> vi; typedef vector<vi> vvi; typedef pair<int,int> pii; int counto(vvi& p, vvi& visited, int y, int x) { const int dy[] = {-1, 0, 0, 1}; const int dx[] = {0, -1, 1, 0}; int h = p.size(); int w = p[0].size(); int ans = 1; int tmp = p[y][x]; p[y][x] = -1; visited[y][x] = 1; rep(i, 4){ int py = y+dy[i]; int px = x+dx[i]; if(py<0 || h<=py || px<0 || w<=px) continue; if(visited[py][px]) continue; if(p[py][px] == tmp) ans += counto(p, visited, py, px); } p[y][x] = tmp; return ans; } void change(vvi& p, vvi& visited, int y, int x, int ne) { const int dy[] = {-1, 0, 0, 1}; const int dx[] = {0, -1, 1, 0}; int h = p.size(); int w = p[0].size(); int tmp = p[y][x]; p[y][x] = -1; visited[y][x] = 1; rep(i, 4){ int py = y+dy[i]; int px = x+dx[i]; if(py<0 || h<=py || px<0 || w<=px) continue; if(visited[py][px]) continue; if(p[py][px] == tmp) change(p, visited, py, px, ne); } p[y][x] = ne; } void dump(vvi& p){ vvi v(p.size(), vi(p[0].size(), 0)); printf("count = %d\n", counto(p, v, 0, 0)); rep(i, p.size()){ rep(j, p[i].size()) printf("%d", p[i][j]); puts(""); } puts(""); } int search(vvi p, int d, int c) { // printf("d=%d\n", d); // dump(p); // getchar(); if(d == 5){ vvi v(p.size(), vi(p[0].size(), 0)); return counto(p, v, 0, 0); } int ans = 0; reep(i, 1, 7){ if(i == p[0][0] || (d==4 && i!=c)) continue; vvi next = p; vvi v(p.size(), vi(p[0].size(), 0)); change(next, v, 0, 0, i); ans = max(ans, search(next, d+1, c)); } return ans; } int main() { int h, w, c; while(scanf("%d%d%d", &h, &w, &c), h){ vvi panel(h, vi(w)); rep(i, h) rep(j, w) scanf("%d", &panel[i][j]); int ans = search(panel, 0, c); printf("%d\n", ans); } return 0; }
E
A→B→Cと比較的快調に解き進めた次はEに挑戦しました。
「なんか制約多い…めんどくさい…」と思ってたんですけど少し考えて累積和+領域のDPで解けることが分かったのでコーディング。
何故かmapを使ってメモ化再帰するという頭悪いコードになってますがご容赦ください。
Submitするときにデバッグ用の出力が入ったアウトプットファイルをそのまま出してしまい無駄な1WAを喰らってしまいました…。
#include <cstdio> #include <vector> #include <algorithm> #include <string> #include <map> #include <set> #include <queue> #include <cstring> #include <deque> #include <cstdlib> #include <stack> #include <cmath> #include <iostream> using namespace std; #define reep(i,f,t) for(int i=f ; i<int(t) ; ++i) #define rep(i,n) reep(i, 0, n) typedef vector<int> vi; typedef vector<vi> vvi; typedef pair<int,int> pii; vvi sum; map<pair<pii, pii>, pii> memo; int s; int lack; int get(int y, int x, int h, int w) { return sum[y+h][x+w] - sum[y][x+w] - sum[y+h][x] + sum[y][x]; } pii search(int y, int x, int h, int w) { pair<pii, pii> hoge = make_pair(pii(y, x), pii(h, w)); if(memo.count(hoge)) return memo[hoge]; pii ans(1, get(y,x,h,w)); if(lack > get(y,x,h,w)) return pii(-1, 0); reep(i, 1, w){ pii a = search(y, x, h, i); pii b = search(y, x+i, h, w-i); if(a.first==-1 || b.first==-1) continue; pii ne(a.first + b.first, min(a.second, b.second)); ans = max(ans, ne); } reep(i, 1, h){ pii a = search(y, x, i, w); pii b = search(y+i, x, h-i, w); if(a.first==-1 || b.first==-1) continue; pii ne(a.first + b.first, min(a.second, b.second)); ans = max(ans, ne); } return memo[hoge] = ans; } int main() { int h, w; while(scanf("%d%d%d", &h, &w, &s), h){ memo.clear(); vvi field(h, vi(w)); rep(i, h) rep(j, w) scanf("%d", &field[i][j]); sum = vvi(h+1, vi(w+1, 0)); reep(i, 1, h+1) reep(j, 1, w+1){ sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + field[i-1][j-1]; } lack = sum[h][w] - s; pii ans = search(0, 0, h, w); printf("%d %d\n", ans.first, s-(sum[h][w]-ans.second)); } return 0; }
D
だいたい1時間強でここまで来たんですけど競技の残り時間を全てDに費やしてしましました…。
枚数が高々24枚なので、状態数は2^24ということでメモ化再帰で組んだんですけど
何故かWA。問題文を10回くらい見直してもWA。
最終的に51行目のbreak;を消去すると正常に動くよ！と競技終了後id:hyon さんに指摘された暁にはなんかもう虚無感が。
#include <cstdio> #include <vector> #include <algorithm> #include <string> #include <map> #include <set> #include <queue> #include <cstring> #include <deque> #include <cstdlib> #include <stack> #include <cmath> #include <iostream> using namespace std; #define reep(i,f,t) for(int i=f ; i<int(t) ; ++i) #define rep(i,n) reep(i, 0, n) typedef vector<int> vi; typedef vector<vi> vvi; typedef pair<int,int> pii; struct C { int x, y, r, c; C(){} C(int x, int y, int r, int c) : x(x), y(y), r(r), c(c){} }; bool okok(const C& a, const C& b) { int sq = (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y); return (a.r+b.r)*(a.r+b.r) > sq; } vector<C> c; map<int, int> memo; int n; int search(int mask) { if(memo.count(mask)) return memo[mask]; vector<bool> top(n, true); rep(i, n){ if(mask & (1<<i)){ reep(j, i+1, n){ if(mask & (1<<j) && okok(c[i], c[j])){ top[j] = false; break; } } } } vi color(5, 0); rep(i, n){ if(top[i]) ++color[c[i].c]; } int ans = 0; rep(i, n){ if(top[i] && (mask & (1<<i)) && color[c[i].c] >= 2){ reep(j, i+1, n){ if(top[j] && c[i].c == c[j].c && (mask & (1<<j))){ int next = mask & ~((1<<i) | (1<<j)); ans = max(2+search(next), ans); } } } } return memo[mask] = ans; } int main() { while(scanf("%d", &n), n){ c = vector<C>(n); memo.clear(); rep(i, n){ scanf("%d%d%d%d", &c[i].x, &c[i].y, &c[i].r, &c[i].c); } int ans = search((1<<n)-1); printf("%d\n", ans); fprintf(stderr, "%d\n", ans); } return 0; }
F, G
Fは難しそうな幾何です。
GはDを解いたら考えるつもりでしたがそんな時間はありませんでした。
結果
4AC(1WA)の17位です。
Dで嵌らなければ10位以内には入れてたはずなんですけど…。ぐぅ。
しかしでもなんとかアジア地区予選には進める感じですし、高専1位を死守出来たのでこれは喜ぶべきですね。
アジア地区予選では英語の壁がありますができるだけ頑張っていきたいと思います。
三角形と円の位置関係判定
AOJ0153 を解いたメモ。
三角形の頂点の座標と円の中心座標及び半径が与えられた時に、
- 円が三角形に含まれる場合 a
- 三角形が円に含まれる場合 b
- それ以外の場合で、共通部分がある場合には c
- 共通部分がない場合には d
を出力します。
但し線や点同士が接している場合も「共通している」判定です。
以下、上手くいった方法。
- 三角形の各頂点が全て円の中に含まれている場合 : b
- 三角形の各頂点の内円の中に含まれているものと含まれていないものがある場合 : c
- 三角形の各頂点が全て円の中に含まれていない場合
- 三角形の辺と円の中心の距離 < 円の半径 な辺が存在する場合 : c
- 三角形の全ての辺について、円の中心との距離≧円の半径 な場合
- 三角形の中に円の中心が存在する場合(CCWで判定) : a
- 三角形の外に円の中心が存在する場合
- 円周と接する辺が存在する場合 : c
- 円周と接する辺が存在しない場合 : d
最後の円周と接する条件を見落としていて、WAをたくさん貰ってしまった…。
結構エレファントになってしまったので、もっとこうするとスマートに判定できるヨ！的な情報あったらぜひ教えてください。
.NETからNativeDLLの中にあるC++のboolが引数/戻り値の関数をP/Invokeで呼び出す
以下のようなコードを動かしたいと思ったとします。
// hoge.cpp // hoge.dll を生成する extern "C"{ __declspec(dllexport) bool isEven(int n) { return n % 2 == 0; } }
// fuga.cs using System; namespace Fuga { static class Program { static void Main() { int n = int.Parse(Console.ReadLine()); Console.Write(isEven(n)); } [DllImport("hoge.DLL")] extern static bool isEven(int n); } }
しかし、このコードは、期待したとおりに動かないことがあります。
それは何故かというと、bool型は通常UnmanagedType.Boolという、32bit整数型としてMarshalされるからなんですね。
これを正しく動作させるには、DllImportの次行に
[return: MarshalAs(UnmanagedType.U1)]
の一行を追加するようです。
引数の場合は、その直前に同じようにMarshalAsを書けば良いですね。
Single Round Match 481
死にました＼(^o^)／
250
「卵が先か鶏が先か」という命題に対して、n人がその答えを知っている。
各人に尋ねたところ、eggCount人が「egg」と答え、n-eggCount人が「chiken」と答えた。
n人の内、lieCount人は嘘をついて自分の知っている答えの逆を言っている。
n人の内、liarCount人はそもそも知っている答えが正答の逆である(正答の逆を答えだと思っている人が嘘をついて更にその逆=正答を言っている場合もある)。
このとき、卵が先か、鶏が先か、どちらともとれるか、どちらもありえないのかを計算する。
eggCount個の0とn-eggCount個の1をlieCount個反転させた後、liarCount個更に反転させて全て0or1になるかを判定すれば良い。
lieCount個反転させる段階で、考えうる0の最小個数と最大個数を算出して、その間にliarCountが入っているか(鶏はn-最swap(小, 大)個数)を判定したのですが
0もしくは1の数って2こずつしか変化しないので、偶奇の検査も要るということに終了1分前に気づいて、修正が間に合いませんでした。
しにました。
Easy: ChallengeSucceeded 0.00points
500
コンピュータのジョブのスケジューリング問題。
名前とジョブの処理時間の組が与えられる。一人が複数ジョブを与えていることもある。
コンピュータは同時に複数のジョブを処理できない。
各人の待ち時間(その人の与えたジョブが全て終わるまでの時間)の平均値を最小化する。
待ち時間の平均が最小なジョブの処理の順番が複数ある場合、コンピュータはその順番をランダムに選択するので
それぞれのジョブが終了する時刻の期待値を計算する。
まず、同じユーザが複数のジョブを与えている場合、必ずそれらは連続して処理される。
また、同じユーザのジョブはどのような順番で処理してもそのユーザの待ち時間は変わらないので、ここで期待値の計算が必要になる。
ジョブは最大50個与えられるので、もしも全部ユーザが同じ人だった場合
一つのジョブJの期待値を計算するのに、他のジョブそれぞれを処理する順序がJの前/後の組合せがあるのでO(50*2^49)とかかかるので全探索だと死にます。
ここでいい方法を思いつけなかったので死にました。
正しい解法は、ある順列はそれと対称な(前/後処理を入れ替えた)順列が必ず存在するので、その二つで相殺し中央値から計算できるようになります。
Challenge Phaseで他人のコードを見て気づきました。
Midium: Opened
1000
あけてないです。
Hard: Unopened
結果
0.00points
1284->1262
Div2へ降格しなくて良かったです。
Easyを安定してAccepted出来るプログラマになりたい。
SuperCon2010
先日、東京工業大学と大阪大学の方でSuperConという大会がありました。
スーパーコンピュータを使わせていただくことの出来る太っ腹な大会です。
自分は、LovePlusというチーム名で大阪会場の方に参加させていただきました。
予選
2*n及び3*mの広場を1*2の大きさのタイルで敷き詰める通り数を求める問題。
普通に漸化式を導き行列累乗をバイナリ法を使ってlog(n)で求めているだけですが、興味のある方は下のスライドをどうぞ。
SuperCon2010予選アルゴリズム解説
View more presentations from natrium11321.
本選
n*m (n, m≦50)の広場を1*2の大きさのタイルで敷き詰める通り数を求める問題。障害物もあります。
これが100000問出題されるので、東工大のスーパーコンピュータ・TSUBAMEの9ノード*8コアを45分間使ってできるだけ多く解いたチームの勝ち。
- 島ごとに分けて計算し後で乗算
- ボトルネックになっている1lineを分割し再帰的に計算
- ここに置かなければならないと確定する所は先に置く
- 2個同時置き
以上を実装し、練習用の入力ファイル(10000問)では最終日では多分5000問弱位解けるようになっていました。
また、並列化に関しては
- statistics.txt(問題の統計情報が書かれているファイル)を読み込み評価関数を通し簡単な順にソート
- 100問ごとに同じファイルに分けて読み込む
の2点に重きを置きました。
これでまぁまぁ解けるのではないかなと思っていたのですが、本番で評価関数を通した際に何故か難しい問題が上位に混入してしまい
スーパーコンピュータさんがその問題を解こうと必死にうんうん唸り始めてしまったため残念なことになってしまいました。
健気で一途なのはいいのですが、タイムアウト機能を入れておけばよかったなと激しく思います。
あと最後の最後まで動的計画法を実装が面倒そうだからという思考実験だけで完結させてしまっていたことも心残りです。
そんな感じで余りいい結果は残せませんでしたが、スーパーコンピュータに触れるというだけでも非常に良い経験になったと思います。
SuperConは今年で最後でしたが、まだ高専プロコンやパソコン甲子園がありますし、来年以降はICPCなどでも活躍していけたらいいなと思っています。
最後にソースコードを貼っておきます。
コメントは基本的に嘘つきです。
#include <stdio.h> #include <stdlib.h> #include <mpi.h> #include <math.h> #include "sc10.h" #define TEAMNAME "loveplus" int RANK; // 自分のRank int PROCESS; // 全体のプロセス数 int TOTAL; // 問題の数 void initialize(int* argc, char* argv[]); void finalize(); void parent_arg(char* argv[]); void parent_all(int argc, char* argv[]); void child(char* argv[]); int solve(int m, int n, int k, char table[MAXSIZE][MAXSIZE]); int compute1(int m, int n, int k, char table[MAXSIZE][MAXSIZE]); void unionfind(int m, int n, char table[MAXSIZE][MAXSIZE], int set[], int* setn); void fill(int m, int n, char table[MAXSIZE][MAXSIZE], int y, int x, char c); void animate(int m, int n, char table[MAXSIZE][MAXSIZE]); void getseparate(int m, int n, char table[MAXSIZE][MAXSIZE], int* horizon, int* pos); int separate(int m, int n, int k, char table[MAXSIZE][MAXSIZE], int horizon, int pos, int now); typedef struct { int s_filenum; int probnum; double score; }sub_Level; double serch_score2(int n, int m, int obs, double s1, double s2, double s3); void fsort(char* statistics, int fnames[], int* qnum); int compare2(const void* a, const void* b); int main(int argc, char* argv[]) { int i; if(argc == 1){ puts("Usage: loveplus (filename | -a dirname)"); return 1; } initialize(&argc, argv); if(argc == 2) TOTAL = sc10_readfile(argv[1]); if(RANK == 0){ if(argc == 2) parent_arg(argv); else parent_all(argc, argv); }else{ child(argv); } finalize(); return EXIT_SUCCESS; } /* ------------------------------------ rank0 のプロセスの処理(引数1個, デバッグ用) ---------------------------------------*/ void parent_arg(char* argv[]) { int i, sent=0, solved=0; int problems[100000], pnum; for(i=1; i<PROCESS; ++i){ MPI_Send(&sent, 1, MPI_INT, i, 99, MPI_COMM_WORLD); ++sent; } while(solved<TOTAL){ MPI_Status status; int result[2]; MPI_Recv(result, 2, MPI_INT, MPI_ANY_SOURCE, 99, MPI_COMM_WORLD, &status); sc10_output(result[0], result[1]); ++solved; if(sent < TOTAL){ MPI_Send(&sent, 1, MPI_INT, status.MPI_SOURCE, 99, MPI_COMM_WORLD); ++sent; } } MPI_Abort(MPI_COMM_WORLD, -1); } /* ------------------------------------ rank0 のプロセスの処理(引数2個, 本番用) ---------------------------------------*/ void parent_all(int argc, char* argv[]) { int i, j, c=0; int problems[100000], qnum; char statistics[256]; sprintf(statistics, "%s/statistics.txt", argv[2]); fsort(statistics, problems, &qnum); i=0; if(argc == 4) i = atoi(argv[3]); for(; i<qnum/100; i+=c){ int sent = 0, solved = 0; char fname[16]; for(c=1; (i+c)*100<qnum; ++c){ if(problems[i*100]/1000 != problems[(i+c)*100]/1000) break; } for(j=1; j<PROCESS; ++j){ int hoge = -(problems[i*100]/1000%100)-1; MPI_Send(&hoge, 1, MPI_INT, j, 99, MPI_COMM_WORLD); } sprintf(fname, "%s/prob%02d.in", argv[2], problems[i*100]/1000%100); fprintf(stderr, "%d: %s\n", i*100, fname); sc10_readfile(fname); for(j=1; j<PROCESS; ++j){ int hoge = problems[i*100 + sent] % 1000; MPI_Send(&hoge, 1, MPI_INT, j, 99, MPI_COMM_WORLD); fprintf(stderr, "%d to %d\n", j, problems[i*100+sent]); ++sent; } while(solved < 100*c){ MPI_Status status; int result[2]; MPI_Recv(result, 2, MPI_INT, MPI_ANY_SOURCE, 99, MPI_COMM_WORLD, &status); sc10_output(result[0], result[1]); ++solved; if(sent < 100*c){ int hoge = problems[i*100 + sent] % 1000; MPI_Send(&hoge, 1, MPI_INT, status.MPI_SOURCE, 99, MPI_COMM_WORLD); fprintf(stderr, "%d to %d\n", status.MPI_SOURCE, problems[i*100+sent]); ++sent; } } } } /* ------------------------------------ rank0 以外のプロセスの処理 ---------------------------------------*/ void child(char* argv[]) { for(;;){ MPI_Status status; int index, result[2]; int probname, m, n, k; char table[MAXSIZE][MAXSIZE]; MPI_Recv(&index, 1, MPI_INT, 0, 99, MPI_COMM_WORLD, &status); if(index < 0){ char fname[16]; sprintf(fname, "%s/prob%02d.in", argv[2], -index-1); sc10_readfile(fname); }else{ sc10_getproblem(index, &probname, &m, &n, &k, table); result[0] = probname; result[1] = solve(m, n, k, table); MPI_Send(result, 2, MPI_INT, 0, 99, MPI_COMM_WORLD); } } } int solve(int m, int n, int k, char table[MAXSIZE][MAXSIZE]) { int i, j, o; int setn; int set[MAXSIZE * MAXSIZE]; int result = 1; char buf[MAXSIZE][MAXSIZE], buf2[MAXSIZE][MAXSIZE]; // fprintf(stderr, "hogehoge!\n"); // animate(m, n, table); // sleep(1); unionfind(m, n, table, set, &setn); for(i=0; i<setn; ++i){ int left, right, top, bottom; int pm, pn; int tmpresult; for(j=0; j<m; ++j){ for(o=0; o<n; ++o){ buf[j][o] = table[j][o] == '.' ? '#' : table[j][o]; } } fill(m, n, buf, set[i]/n, set[i]%n, '.'); left = top = MAXSIZE; right = bottom = 0; for(j=0; j<m; ++j){ for(o=0; o<n; ++o){ if(buf[j][o] == '.'){ top = top < j ? top : j; bottom = j < bottom ? bottom : j; left = left < o ? left : o; right = o < right ? right : o; } } } pm = bottom - top + 1; pn = right - left + 1; for(j=0; j<MAXSIZE; ++j){ for(o=0; o<MAXSIZE; ++o){ buf2[j][o] = '*'; } } for(j=top; j<=bottom; ++j){ for(o=left; o<=right; ++o){ buf2[j-top][o-left] = buf[j][o] == '#' ? '*' : buf[j][o]; } } if(pm * pn <= 75){ tmpresult = compute1(pm, pn, k, buf2); }else{ int horizon, pos; getseparate(pm, pn, buf2, &horizon, &pos); //fprintf(stderr, "horizon=%d, pos=%d\n", horizon, pos); tmpresult = separate(pm, pn, k, buf2, horizon, pos, 0); } result = (result * tmpresult) % k; } // fprintf(stderr, "%d returned.\n", result); // sleep(1); return result; } /* ------------------------------------ 分割 ---------------------------------------*/ void getseparate(int m, int n, char table[MAXSIZE][MAXSIZE], int* horizon, int* pos) { /** int hor[MAXSIZE], ver[MAXSIZE]; int hsum[MAXSIZE] = {0}, vsum[MAXSIZE] = {0}; int i, j; int best, bestdiff; for(i=0; i<m; ++i){ for(j=0; j<n; ++j){ hor[i] += table[i][j] == '.'; ver[j] += table[i][j] == '.'; } } for(i=1; i<=m; ++i){ hsum[i] = hsum[i-1] + hor[i]; } for(i=1; i<=n; ++i){ vsum[i] = vsum[i-1] + ver[i]; } best = MAXSIZE; bestdiff = MAXSIZE; for(i=0; i<m; ++i){ if(hor[i] == 0) continue; if(best > hor[i]){ *pos = i; best = hor[i]; *horizon = 1; bestdiff = abs((hsum[i]) - (hsum[m]-hsum[i])); }else if(best == hor[i]){ int diff = abs((hsum[i]) - (hsum[m]-hsum[i])); if(diff < bestdiff){ *pos = i; best = hor[i]; *horizon = 1; bestdiff = diff; } } } for(j=0; j<n; ++j){ if(ver[j] == 0) continue; if(best > ver[j]){ *pos = j; best = ver[j]; *horizon = 0; }else if(best == ver[j]){ int diff = abs((vsum[j]) - (vsum[n]-vsum[j])); if(diff < bestdiff){ *pos = i; best = ver[j]; *horizon = 0; bestdiff = diff; } } } /*/ *horizon = m > n; *pos = m > n ? m/2 : n/2; *pos-=2; /**/ } int separate(int m, int n, int k, char table[MAXSIZE][MAXSIZE], int horizon, int pos, int now) { int result = 0; int i, j; int dy = horizon ? 0 : 1; int dx = horizon ? 1 : 0; int y = horizon ? pos : now; int x = horizon ? now : pos; int put = 0; // fprintf(stderr, "now = %d started.\n", now); for(; y<m && x<n; y+=dy, x+=dx){ // fprintf(stderr, "(%d, %d)\n", x, y); if(table[y][x] != '.') continue; table[y][x] = '%'; if(table[y+dy][x+dx] == '.'){ // fprintf(stderr, "a in(now = %d)\n", now); table[y+dy][x+dx] = '*'; result = (result + separate(m, n, k, table, horizon, pos, horizon ? x+2 : y+2)) % k; table[y+dy][x+dx] = '.'; // fprintf(stderr, "a out(now = %d)\n", now); ++put; } if(table[y+dx][x+dy] == '.'){ // fprintf(stderr, "b in(now = %d)\n", now); table[y+dx][x+dy] = '%'; result = (result + separate(m, n, k, table, horizon, pos, horizon ? x+1 : y+1)) % k; table[y+dx][x+dy] = '.'; // fprintf(stderr, "b out(now = %d)\n", now); ++put; } if(table[y-dx][x-dy] == '.'){ // fprintf(stderr, "c in(now = %d)\n", now); table[y-dx][x-dy] = '%'; result = (result + separate(m, n, k, table, horizon, pos, horizon ? x+1 : y+1)) % k; table[y-dx][x-dy] = '.'; // fprintf(stderr, "c out(now = %d)\n", now); ++put; } table[y][x] = '.'; if(put != 0) return result; } result = (result + solve(m, n, k, table)) % k; // fprintf(stderr, "now = %d finished.\n", now); return result; } /* ------------------------------------ unionfindかと思いきや ---------------------------------------*/ void unionfind(int m, int n, char table[MAXSIZE][MAXSIZE], int set[], int* setn) { int i, j; char buf[MAXSIZE][MAXSIZE]; *setn = 0; for(i=0; i<m; ++i){ for(j=0; j<n; ++j){ buf[i][j] = table[i][j] == '.' ? '#' : table[i][j]; } } for(i=0; i<m; ++i){ for(j=0; j<n; ++j){ if(buf[i][j] == '#'){ fill(m, n, buf, i, j, '@'); set[*setn] = i*n + j; ++*setn; } } } } void fill(int m, int n, char table[MAXSIZE][MAXSIZE], int y, int x, char c) { int dy[] = {-1, 0, 0, 1}; int dx[] = {0, 1, -1, 0}; int i, j; table[y][x] = c; for(i=0; i<4; ++i){ int py = dy[i] + y; int px = dx[i] + x; if(py<0 || m<=py || px<0 || n<=px) continue; if(table[py][px] != '#') continue; fill(m, n, table, py, px, c); } } /* ------------------------------------ 探索木による計算 ---------------------------------------*/ void animate(int m, int n, char table[MAXSIZE][MAXSIZE]) { int i, j; for(i=0; i<m; ++i){ for(j=0; j<n; ++j){ putchar(table[i][j]); } puts(""); } puts(""); } int compute1(int m, int n, int k, char table[MAXSIZE][MAXSIZE]) { int i, j; int tmpresult = 0; int by=-1, bx=-1; for(i=0; i<m; i++){ for(j=0; j<n; j++){ int a, b, c, d; if(table[i][j] != '.') continue; a = table[i][j+1] == '.'; b = table[i+1][j] == '.'; c = j ? table[i][j-1] == '.' : 0; d = i ? table[i-1][j] == '.' : 0; if(a+b+c+d>=2 && by == -1){ by = i; bx = j; }else if(a+b+c+d==1){ table[i][j] = '*'; if(a){ table[i][j+1] = '*'; tmpresult = (tmpresult + compute1(m, n, k, table)) % k; table[i][j+1] = '.'; }else if(b){ table[i+1][j] = '*'; tmpresult = (tmpresult + compute1(m, n, k, table)) % k; table[i+1][j] = '.'; }else if(c){ table[i][j-1] = '*'; tmpresult = (tmpresult + compute1(m, n, k, table)) % k; table[i][j-1] = '.'; }else if(d){ table[i-1][j] = '*'; tmpresult = (tmpresult + compute1(m, n, k, table)) % k; table[i-1][j] = '.'; } table[i][j] = '.'; return tmpresult; } else if(a+b+c+d==0){ return 0; } } } if(by == -1) return 1; /* It's mendokusai. */ i = by; j = bx; table[i][j] = '*'; /* horizonal */ table[i][j+1] = '*'; if(table[i+1][j] == '.'){ table[i+1][j] = '*'; if(table[i+1][j+1] == '.'){ table[i+1][j+1] = '*'; tmpresult = (tmpresult + compute1(m, n, k, table) * 2) % k; table[i+1][j+1] = '.'; } if(table[i+2][j] == '.'){ table[i+2][j] = '*'; tmpresult = (tmpresult + compute1(m, n, k, table)) % k; table[i+2][j] = '.'; } if(j>0 && table[i+1][j-1] == '.'){ table[i+1][j-1] = '*'; tmpresult = (tmpresult + compute1(m, n, k, table)) % k; table[i+1][j-1] = '.'; } table[i+1][j] = '.'; }else{ tmpresult = (tmpresult + compute1(m, n, k, table)) % k; } table[i][j+1] = '.'; /* vertical */ table[i+1][j] = '*'; if(table[i+1][j+1] == '.'){ table[i+1][j+1] = '*'; if(table[i+2][j+1] == '.'){ table[i+2][j+1] = '*'; tmpresult = (tmpresult + compute1(m, n, k, table)) % k; table[i+2][j+1] = '.'; } if(table[i+1][j+2] == '.'){ table[i+1][j+2] = '*'; tmpresult = (tmpresult + compute1(m, n, k, table)) % k; table[i+1][j+2] = '.'; } table[i+1][j+1] = '.'; }else{ tmpresult = (tmpresult + compute1(m, n, k, table)) % k; } table[i+1][j] = '.'; table[i][j] = '.'; return tmpresult; } /* ------------------------------------ 初期化処理 ---------------------------------------*/ void initialize(int* argc, char* argv[]) { MPI_Init(argc, &argv); MPI_Comm_rank(MPI_COMM_WORLD, &RANK); MPI_Comm_size(MPI_COMM_WORLD, &PROCESS); sc10_init(TEAMNAME); } /* ------------------------------------ 終了時処理 ---------------------------------------*/ void finalize() { MPI_Finalize(); } /* ------------------------------------ サッ☆ ---------------------------------------*/ void fsort(char* statistics, int fnames[], int* qnum) { FILE *fp; int i, j,loop,l_count,cp_i[100]={0}; int n, m, k; int obs; double s1, s2, s3; int pnum; char fname[16]; int cp_filename[100][100]; sub_Level* s_level = (sub_Level*)malloc(sizeof(sub_Level) * 100001); *qnum=0; fp = fopen(statistics, "r"); while(fscanf(fp, "%d%s%d%d%d%d%lf%lf%lf", &pnum, fname, &n, &m, &k, &obs, &s1, &s2, &s3) != EOF){ int f; /*問題番号*/ s_level[*qnum].probnum = pnum; s_level[*qnum].s_filenum = pnum/1000%100; s_level[*qnum].score = serch_score2(n, m, obs,s1,s2,s3); ++*qnum; } qsort(s_level, *qnum, sizeof(s_level[0]), compare2); loop=0; for(i=0;i<*qnum;i++) { cp_filename[ s_level[i].s_filenum ][ cp_i[s_level[i].s_filenum ]]=s_level[i].probnum; cp_i[ s_level[i].s_filenum ]++; if(cp_i[ s_level[i].s_filenum ]==100) { for(l_count=0;l_count<100;++loop,++l_count) { fnames[loop]=cp_filename[ s_level[i].s_filenum ][ l_count ]; } cp_i[s_level[i].s_filenum]=0; } } free(s_level); fclose(fp); } double serch_score2(int n, int m, int obs, double s1, double s2, double s3) { double temp = 1.0/(n*m-obs);//sqrt(s1*1.5+s2+s3*0.5)/10000.0; double _obs = ((double)obs/((double)n*(double)m)); // double a = temp; int flg = 0; if(s1 < 60){ temp *= 0.6; } /* if(s1 > 40 && s3 > 200){ temp *= 0.4; _obs = sqrt(_obs); flg = 1; } */ else if(s1 < 10 && s3 < 70){ temp *= 0.75; _obs = sqrt(_obs); flg = 1; } else if(s1+s2+s3 < 220){ temp *=0.5; _obs = sqrt(_obs); flg = 1; if(s1+s2+s3 < 40){ temp *= 0.75; } } if(s1 + s2 + s3 > 700){ temp *= 3; } temp *= (_obs/5); // printf("%lf * %lf * srore >> %lf\n",a,flg == 0 ? 1.0 : 0.6,temp); return temp; } int compare2(const void* a, const void* b) { double aa = ((const sub_Level*)a)->score; double bb = ((const sub_Level*)b)->score; return aa > bb ? -1 : (aa < bb ? 1 : 0); }
