とこはるのまとめ

多分考えたことがまとまっているはずです。きっと。おそらく。

とこはるの問題

今までに作った(or原案に携わったレベルの)問題と簡単なコメント

2012年

簡単な問題を作りたかった

タイトルだけ。内容は関与せず。

基礎的なフローの問題を作りたかった

当時は列になってる数をうにょうにょするDPを作りたかったはず。

高評価をいただいて大変ありがたい問題です。
本番中はwatashi(=rejudge)さんとrngさんだけが解きました。

2014年

やっぱり簡単な問題を作りたかった

よすぽさんと話し合ってたらできた。
よすぽさんが筋のいい問題を投げてくれたのでいい感じの解法のある問題が出来た。

地味にgeneratorが面倒で、適当にやるとビームサーチが通ってしまっていた。つまるところ局所解が少なかった。そこでgeneratorではi個外食したときの最適解f(i)のようなものを考えてそれの差分を導出してこれがランダムウォークっぽい挙動をするように調整したりした。

題名だけで放り投げておいたらshimomireさんが筋のいい問題を提案してくれていたので、いい感じの解法を付けて出題された。お気に入り問題のひとつ

知識ゲーを出したかった

JAGで出そうとした問題の没問。ごく一部に知ってる人はいたけど高校生用だからいいでしょってことで出してもらいました。

2015年

超簡単な問題を出したかった

大昔uwiさんと似たような問題を議論した覚えがあるけど時効だし出してuwiさんが正解しても不公平にはならないと思ったので出した。
証明の仕方が競プロ的テク+ホールの補題なのがお気に入り。

投げやり題名。組合せ最適化に書いてある問題だけど出してみた。手で解いたときは最小平均長閉路だと思ったけど、みんな牛ゲーで解いていたのでしくじったと思った。

原題はKaraoke Schedulingだった。（人より音が取れない下手くそではあるけど）カラオケにたまに行くのは楽しいなぁみたいな気分のときに問題を作った。
それから、簡単バージョンとしてコストが二乗でなくて絶対値になっている問題も同時に提案していた。

提案時はAOJ-ICPC換算で600-700くらいで、（アイデアは）蟻本にも書いてる内容だしで、ちょうどいいぐらいの典型問題だと思って出しだけど、人々を虐殺してしまった。
writer解を作るときに割とバグらせて時間がかかったのでそのときに気づくべきだったかもしれない？
XVII Open Team Programming Collegiate Cup. ロシアだといいぐらいに上位層を選別する難度の問題として機能していたかなあという感じ。

VectorFieldを1次元にすればええやん、というそれだけ。
ただ、まじめに考えるときれいにできるのでよい

なんか行列累乗みたいな感じの問題を作りたかった。
サンプルにすべてのクエリーを網羅してなかったので申し訳ない

ここに書いた : 2015 JAG Regional J : Longest Shortest Path - とこはるのまとめ

（ノックアウトな）トーナメント表みたいなのは好きな構造なのでそれを使って何かをしたかったという話。
こういう問題はなかなか説明しづらいので、問題文のwriterには感謝。
最初は区間DPで行けるだけかと思ったけど実験的にやるとMongeが成り立っていそうだったので、Mi_Sawaさんに投げたら証明が返ってきました。

2016年

豪邸と宅配便 , jfen : あまり仕事ができず。

2017年

IOIで出た図書館系の問題が割と好きだったのでそういうのを作りたくなったので作りました。

昔の本家ICPCの問題 BrokenDoor http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1178&lang=jp をそのまま一般化したもの。
AOJ-ICPCにある難問を通勤中の電車で考えることを一時期やっていて、
BrokenDoorを考えているときになんとなく行けそうな気がしてきて、頑張って詰めた覚えがあります。

これを本番で通せるチームが複数いるあたり、やはり当時とはレベルが段違いであることを伺わせます。
昔のICPC勢と飲むときに酒のつまみにできる問題です。

問題の美しさは最高レベルだと思っています。
wataさんの資料からも参照されていてとても嬉しいです。

模擬地区に向けて問題が足りないということで必死こいて作りました。結構短期間で作った覚えがあります。

2019年

  • All your base are belongs to us

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2972

JAG内部の問題Wikiに雑すぎる解法を書いたため埋もれていた問題です。
notさんがエレガントな証明を思いつくことで日の目を見ました。

2013アジア地区大会振り返り

おさけーさんによる別視点
http://www.osak.jp/diary/diary_201312.html#20131205

まとめ(1/8 追記)

binding.pryの一員としてICPCアジア地区大会の会津大会(日本大会)およびDanang大会(ベトナム大会)に参加してきた。

会津大会で国内大学としては、東大に次ぐ形となり、これが決め手となって世界大会(エカテリンブルク・ロシア)に行けることになった（まだ非公式だが）。Danang大会でもいい感じの順位まで来たがここでは次点止まりだった。

今回はFCCPC_alphaがかなり強いので半分は負けると考えていたが、その中で勝てたのは正直かなり幸運だったように思う。

チーム戦略としては、二人が実装主体で、一人（ぼく）が後ろでアルゴリズムなどを考えるというもの。
要するにこれの劣化版

劣化版というのは University of Agitsune より遥かに能力が低いということだが、今回はそれなりにうまく行ったように思う。あと、実際には二並列ではなくて、何回かやってみて我々のチームでは「メインコーダー」と「サブコーダー / デバッガー / 読解」みたいな分け方が妥当だなあと思った。書いてみたけど改めて後者が「何でも屋」って感じがする。すごい。

メリットは

  • 後ろの人は両メンバーと話し合いながらすすめることが多いので、時間的にどの問題からやるかとか、コーダー交代のタイミングを（それなりに）正しく制御できる。
  • 実装苦手な人が実装しなくてよい / 逆も。
    • ただし、実装量の見積もりはそれなりに正しく出来る必要があるので、本当の素人に任せるわけにはいかない感じがする

デメリットは

  • 後ろの人は実装する人に正しいアルゴリズムを正確な言葉で伝えなければならない
    • これは出来る人が全部一からやるよりも時間的ロスが大きい
    • また、間違った言葉で伝えてしまって大惨事になるリスクもある(Danang,C問題)

というところだと思う。

===================================================================
以下、大会中の流れ

注：以下は全くまとまってない
・もうだいぶ時間経ったので時系列が嘘っぱちかも。
・読み返していないので文章がおかしいかもしれない

会津大会


・すごいドキドキする
0完
・ドキドキしつつも事前の打ち合わせ通り自分はCを読む。
・ドキドキしているがまあこれは普通に座標圧縮でゴニョゴニョすれば大丈夫だと思う
・あとEを読んでおく
1完(A)
・領域の間に辺があるかどうかの判定がどうにもめんどくさそうだが、特に解決策も思いつかなかったのでそのままosa_kさんに投げる。
・その後、osa_kさんが領域の間を別の色で塗るというナイスな案を考える。すごいいけそう
・Eの概要も伝える。何も考えていなかったが、Dijkstraだと言われる。たしかに。
・Dを考える。何を考えればいいんだ…
・Gについてosa_kさんから3次元のマトリョシカだと言われたが、そういう系見たこと無いし、すぐに取っ掛かりが見つからないので絶対にヤバイ問題だと思う。
・思い違いかもしれないが、少なくとも3段階で最も簡単な難易度というのは大嘘だと感じてAを☓印で消す
2完(B)
・Dの詳細を詰めようとする。心臓バクバクする。なんだこれ。やばい。JOIですらこんなに緊張したか怪しい。
・C、 おさけーさんが失敗してるけど、みけきゃっとさんが行けそうと言っているので行けるかも。とりあえず任せてみる。
・D、 よく考えたら秒針を変数として(0<=x<60)としたら普通に式が立つじゃん。大体式立ちそう。
・Cがヤバイらしい。見てみると、たしかにみけきゃっとさんの方針はやばい。見落としだった。しくった。とりあえずおさけーさんに再び交代。
3完(C)
・D,Eどっちが早いか問われる。Eは20分でできるらしい。すごい。Dは式が完全ではないので、Eを任せる。
・Eをやってもらっている時間でちゃんと確認。これなら大丈夫そう
・みけきゃっとさんも分数を定義して行けそう、と言ってくれる
4完(E)
・みけきゃっとさんにDを任せる。
・そろそろドキドキが収まってくる。
・Hをosa_kさんがいい感じの幾何だと見破ってくれる。
・本質部分の話は昔きゅうりの問題で見たことがあると言ったが、僕自身完全に忘れていた。
・その問題は分割統治法で解いた覚えがあったが、今回はそれよりも制約がきついし、詳細忘れていたし、osa_kさんにメリットを説明することが出来なかったのでそれは実現せず(分割統治を使えば幾何のめんどい式を一切使わずに答えを求めることが出来る)
・osa_kさんが頑張ってHを詰めているうちにIを考える。わからん。
・Gもちょっと考えてみる。やっぱりやばい問題じゃないのという感想を持つ。
・Hの詰めの際に詳細の確認をされる。それっぽい証明を言って完全に方針が定まる。
・Dが少し詰まっているようにも見えたのでチラチラ見る。少し想定と違ったので少し指示を出しつつ、バグを直したら通る。
5完(D)
・Hの実装を開始。
・Iを考える。区間DPっぽいものを考えるがやっぱりわからん。
・みけきゃっとさんと新規問題の開拓をしようとするが、成果はない。
・そろそろ時間も押してくる時間だったので、osa_kさんのコードを見るようになる。
・なんかうまく行ってないっぽいのでみけきゃっとさんに印刷したコード投げると、すぐにヤバイ箇所を見つける。さすがデバッガだ。
・そこから何かあったか忘れたが、もう少し直したら通る。
6完(H)
・次に何を解くか。選択肢はF,G,I.どれもいうほど開拓できてない。実力不足感。
・おさけーさんの魔法の言葉「落ち着いて考えよう」
・ぼくはJを解くことを推奨しようとしていた（が、多分おさけーさんが完全に無理と判断しているので、どっちにしろ退けられていた）
・Gはやばいと主張し続けた。（これが正しかったかはわからん
・Iもきっとやばいと主張した
・その結果Fを考えてみた。
・Fでその前までわかっていたことといえば、「球面をうまいこと分割することだけど、球面とかうまいこと分割できるわけ無いじゃん」ぐらい。
・その辺を説明している辺りで、球面上での距離の大小関係は3次元の直線距離でも同様の大小関係を保つことに気づく。
・勢いのまま話して、それは蟻本にあることを言われ（もちろん僕も気づきつつ）開き、3次元をどうするかを考えて、それ以外の部分をまずはかき上げることにする。
・実装パートはおさけーさん、詳細の詰めはとこはる＆みけきゃっと。
・まずは蟻本のアルゴリズムを思い出す。見たことはあったので、その辺は比較的楽。
・次に次元を上げた時にどうするか。いろいろ出たが、実装量的には、単純に2次元のときに枝刈？のようなことをそのまま流用するのが最善と判断。もしTLEならそのときに考える。
・ちょうどおさけーさんも書き終わったっぽいので、蟻本を見せつつ説明。理由も示しつつ説明したつもりだった（が、言われるがまま、という感じだったらしい。その辺難しい
・実装が終わる。なんかうまく行かない。
・以後はおさけーさんの日記通り。添字ミスが原因。
・最後の最後のSubmit。通った。安堵した。
7完(F)
・F問題のACに至るまでの過程が全員の力を使い切った感じがして非常にドラマチックだったのでかなり印象に残った

Danang 大会

会津とは対照的にわりと落ち着いた気分で大会に臨む。
世界大会ほぼ確実の状態だったからだろう。
0完
・問題文が1部しか配られないので、最初にホッチキスを外して、問題ごとに付箋を貼って最初に読む問題をそれぞれ渡す。
・Jを読む。どうみても行列累乗。でもSumのある形。一応メモに行列とその積を書いて確認。よさそう
1完(A)
・おさけーさんにJを渡す。これこれこうこう、という説明をする。やってもらっているうちに、Dを読む。
・Jがなんかおかしいらしい。色々見て、答えとしている行列の箇所が違うことを確認。サンプルがあったのを確認して提出するがWA.なんでや…
・印刷してもらって確認したりIやってもらったり、Cをちょっと考えたり。
・MOD 10^12じゃねえか！掛け算すると死ぬじゃねえか！！あほか！！
・なのでJを訂正。
・通る。
2完(J)
・Iもすぐ直すだけだったらしい
3完(I)
・Cの解法を伝える。
・O(NlogN)だったら通ると思い、1~Nで篩っぽい操作をする旨を伝えた（が、普通の篩の操作をしてしまっていた。篩なんて表現で伝えるべきではなかった。
・その間にFを考えるなどする。
・Fは0011100みたいなビット列で管理すると頭がおかしくなるので、0がa個あって、1がb個あって、みたいな記法で表現して考えることにする。0,1が逆でも問題変わらないので、(a,b,...)の列だけ考えればよいので、こっちのほうが楽である。
・Cがなんか合わないらしい。解釈を議論する。やはりよくわからん。色々試すけどダメっぽい。
・ので、Fを渡す。結局、縮約処理をシミュレートする感じにした。証明はできてない
・Fを実装してもらっている間にGの問題概要を聞いたりする。
・みけ「いくつかグラフが与えられて、それが同じグラフか判定する問題」とこ「へー、それって木だったりするん？」みけ「木だね」とこ「まじでｗｗｗｗｗｗ」
・つまるところ聞いたことある問題だったので、これは解けると確信するが、それは時間がある話であって、果たしてこれはうまく行くのか…
・Fのサンプルがそれっぽいので投げる。AC
4完(F)
・引き続き闇のCを考えてもらう。なんかみけきゃっとさんが気づいたらしいのでそれを元に検証が行われている。
・Bの問題も聞いておく。全域木の数え上げらしい。
・知ってた。正確に言えば、解けることを知ってた。詳細はあんま覚えてなかった。やばい。これは正念場だ…。
・思い出す。覚えている情報は次の通り。
+ 行列式が答え。
+ 隣接行列を使う。
+ Traceはなんか別に割り振る。
+ なんかマイナスを掛けるとか出てきたような気がする。
・いつか忘れたけど、いい感じにCもなんとか解けたらしい。
5完(C)
・それで、さっきの箇条書きを組み合わせてそれっぽい行列を作る。
具体的には、普通の隣接行列に対角部分に次数に-1かけたものを入れたもの。まあテストして正しいっぽい値でたし大丈夫でしょということでGOサインを出す。（計算ミスで正しい値が出ていた。これでGOサインを出したのは色々やばかった。
・投げている間にDを考える。なんか二部グラフっぽい。最小費用流で答えは出そうな感じはする。正当性はみけきゃっとさんに丸投げする。
・Bの行列式が0になるらしい。ほんとだ。たしかに計算しても0になる。
・もう一回さっきの行列式を思い出す。
・そういえば、さっきの行列の行列式を出しても常に0だったような気がしてきた。
・それだったら、確か一行一列抜かすんじゃないかなあ
・ということで、最後の行を抜かして行列式を求めてもらう。
・サンプルでそれっぽい値が出るが、+になったり-になったりするらしい。
・みけきゃっとさんから修正案も出るが、僕が「これは偶奇で場合分けだろう」と言う。
・結局偶奇がそれっぽい値が出るように見える。出してみる。AC
(結局、思い出した行列式はTrace部分は正で、それ以外の隣接行列の部分は-1を記入する、ということだったし、二重に間違って思い出していた)
6完(B)
・あと解ける問題は時間的にDのみ。
・最小費用流を実装してもらい、そして費用について逐一説明する。
・なんとか書き終わったが、時間がない。サンプルにも食わせず提出。WA。終戦。

DP俯瞰?

他のDPの記事
http://d.hatena.ne.jp/Tayama/20111210/1323502092
http://d.hatena.ne.jp/komiyam/20111212/1323615687

Typical DP Contest
http://tdpc.contest.atcoder.jp/

  • 基本(1)
  • 基本(2)(有名問題)
    • 最長共通部分列問題(LCS)
    • 編集距離問題
    • 最長増加部分列問題(LIS)
    • 硬貨両替問題
      • 硬貨が1,3,4円だったときにn円で必要な最小枚数を求める問題を指す
    • 最短経路問題?
      • Bellman-ford法
      • Warshall-Floyd法
  • bitDP
    • 巡回セールスマン問題
    • 漸化式がdp[S] = min(dp[T] + dp[U] + f(S,T,U)) ( T,U \subset S, T and U = empty ) (パッと見O(4^n)かかるがO(3^n)で済む形)
    • いくつかの状態を確定したら残りの部分はgreedyで確定するもの
    • ドミノ敷き詰め問題
    • connectedな情報をプラスして持つbitDP
  • 木DP
    • 木の直径
    • (問題)
      • comittee(JOI 春合宿2008)
      • Distribution(JOI 春合宿2009)
      • MultiEndingStory( AOJ2344 )(難)
  • 区間DP
    • 蟻本のBribe the Prisonersなど、大概O(N^3)
    • Monge性を持たせて高速化O(N^2)
      • 最適二分探索木問題
    • 区間+もうひとつの情報でO(N^5)->O(N^4)の高速化 : SRM492D1Med, SRM499D1Med
  • 確率DP
  • 桁DP(DigitDP)
  • 累和を用いるDP
    • 累和で得た結果を中心に使う問題
      • JOI2010本選1, Uva108, APIO2009 Oil
    • 累和を使う高速化
    • imos法(累和の逆演算)
      • Nails(2012JOI本選4), Pyramid(AutumnFest2012)
  • BITやsegmentTreeと組み合わせるDP
  • 行列累乗(二乗反復)
    • 基本は蟻本がくわしい, O(N^3 log k)
    • (E+A+A^2+..+A^k)を求めるもの
    • 上三角/下三角テプリッツ行列, O(N^2 log k)
    • 巡回行列, O(N^2 log k)

追記

http://codeforces.com/blog/entry/8219

GCJ 2013 Qual

http://snuke.hatenablog.com/entry/2013/04/14/164938
ここにsnuke神さんが解説書いてくれています。

C

制約をうまく使って解を全列挙して、クエリが来るたび二分探索をすることを考えます
(制約とは、すべての桁の(数字)^2の総和<=9を意味します)

以下はPracticeで通したコードです。

//(include略)

typedef long long LL;
typedef pair<int,int> PII;
#define MP make_pair
#define REP(i,n) for(int i=0;i<(int)n;i++) 
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++) 
#define ALL(c) (c).begin(),(c).end() 


vector<string> data;

void trans(string s) {
  int n = s.size();
  string k = "";
  for(int i=0; i<106-n; i++) k+="0";
  data.push_back(k+s);
  
}


string two(string s) {
  string ret;
  int n = s.size();
  for(int i=0; i<2*n-1; i++) {
    ret += "0";
  }
  for(int i=0; i<n; i++) if(s[i]!='0') {
      for(int j=0; j<n; j++) {
	ret[i+j] += (s[i]-'0') * (s[j]-'0');
	if(ret[i+j]-'0'>=10)
	  cout<<"hogehoge"<<endl;
      }
  }
  
  return ret;
  
}


void saiki(string t, string s, int sum, int length) {
  if(s.size()+t.size()>=52) return;
  if(sum>=10) return;
  if(t[0]!='0')
    trans(two(t+s));
  
  saiki("0"+t, s+"0", sum, length+1 );
  
  saiki("1"+t, s+"1", sum+2, length+1);
  
}


void init() {
  {
    string t="";
    string s ="2";
    trans("9");
    //    trans("484");
    saiki(t,s,4,1);
    s = "1";
    saiki(t,s,1,1);
    saiki(s,s,2,1);
    s="0";
    saiki(t,s,0,1);
    saiki(s,s,0,1);
    
  }
  
  {
    string s = "2";
    string t = "";
    for(int i=0; i<26; i++) {
      trans(two("2"+t+"0"+t+"2"));
      trans(two("2"+t+"1"+t+"2"));
      trans(two("2"+t+t+"2"));
      t+="0";
    }
    
  }
  sort(ALL(data)); 
}
int solve() {
  string s,t;
  cin>>s>>t;
  
  while(s.size()<=105) s = "0"+s;
  while(t.size()<=105) t = "0"+t;
  
  int ans =upper_bound(ALL(data),t) - upper_bound(ALL(data),s);
  if(binary_search(ALL(data), s)) ans++;
  return ans;
}


int main() {
  init();
  /*
  for(int i=0; i<80; i++) {
    cout<<data[i]<<endl;
    }
  */
  int t;
  cin>>t;
  REP(i,t) {
    int ans = solve();
    cout<<"Case #"<<i+1<<": "<<ans<<endl;
  }
  return 0;
}

D

snukeさんみたいに何の操作をするのが最善かは特に考えませんでした。
ですが方針は同じです。操作を一つ行なってその手の先に解がなければその操作を行わず、解があれば一歩進んでその中で考えます。

解の有無判定は以下のような考えをしました。
とりあえず、「解なし」<=>「ある開けていない箱の鍵をどうやっても手に入れられない」と考えます。
自分が鍵を持っていたらその番号には到達可能です。
次に、ある箱を開ける鍵がKEYAiでその箱にKEYBijが入っているとすればKEYAi->KEYBijに辺を張ってります。
これで到達不可能な鍵があれば解なしだ、というかんじでやりました。

（証明してないのであんま詳しいことは言えない…）

あと、明らかにダメなケース（鍵が足りない）は事前に除きました

REPとforが混じってます

//(include略)

typedef long long LL;
typedef pair<int,int> PII;
#define MP make_pair
#define REP(i,n) for(int i=0;i<(int)n;i++) 
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++) 
#define ALL(c) (c).begin(),(c).end() 

const int MAXKEY = 210;
const int MAXCHEST = 210;
bool usedMain[MAXCHEST];
vector<int> solve() {
  int K,N;
  cin>>K>>N;
  int calcKeys[MAXKEY];
  int keys[MAXKEY];
  REP(i,MAXKEY) {
    keys[i] = 0;
    calcKeys[i]= 0;
  }
  REP(i,K) {
    int p;
    cin>>p;
    p--;
    keys[p]++;
    calcKeys[p]++;
  }
  
  vector<vector<int> > chest;
  vector<int> openKey;
  for(int i=0; i<N; i++) {
    int p,q;
    cin>>p>>q;
    vector<int>tmp;

    p--;
    calcKeys[p]--;
    openKey.push_back(p);
    for(int j=0; j<q; j++) {
      int r; cin>>r; r--;
      tmp.push_back(r);
      calcKeys[r]++;
    }
    chest.push_back(tmp);
  }
  vector<int> noSolution;
  for(int i=0; i<MAXKEY; i++) 
    if(calcKeys[i]<0) 
      return noSolution;
  
  vector<int> ans;
  
  REP(i,MAXCHEST) usedMain[i] = false;
  
  REP(turn,N) {
    bool update = false;;
    REP(chestNum, N) if(!usedMain[chestNum]) if(keys[openKey[chestNum]]>0){
      usedMain[chestNum] = true;
      keys[openKey[chestNum]]--;
      for(int i=0; i<chest[chestNum].size(); i++) {
	keys[chest[chestNum][i]]++;
      }
      bool ok = true; 
      {
	bool usedQueue[MAXCHEST];
	bool usedKeys[MAXKEY];
	queue<int> qu;
	vector<int> graph[MAXKEY];
	REP(i,MAXKEY) {
	  usedKeys[i] = false;
	  usedQueue[i] = false;
	}
	REP(i,N) if(!usedMain[i]) {
	  //	  cout<<"node"<<i<<endl;
	  int s = openKey[i];
	  usedKeys[s] = true;
	  REP(j,chest[i].size()) {
	    int t = chest[i][j];
	    graph[s].push_back(t);
	    //	    cout<<"edge"<<s<<" "<<t<<endl;
	  }
	}
	REP(i,MAXKEY) if(keys[i]>0) {
	  qu.push(i);
	  usedQueue[i] = true;
	}
	while(!qu.empty()) {
	  int cur = qu.front(); qu.pop();
	  //	  cout<<"cur"<<cur<<endl;
	  //	  usedQueue[cur] = true;
	  for(int i=0; i<graph[cur].size(); i++) {
	    int next = graph[cur][i];
	    if(!usedQueue[next]) {
	      qu.push(next);
	      usedQueue[next] = true;
	    }
	  }
	}
	/*
	REP(i,N) cout<<turn<<" "<<i<<" "<<usedQueue[i]<<endl;
	REP(i,3) cout<<keys[i]<<endl;
	REP(i,3) cout<<usedQueue[i]<<" "<<usedKeys[i]<<endl;
	*/
	REP(i,MAXKEY) if(!usedQueue[i] && usedKeys[i] ) ok = false;
	
      }
      if(!ok) {
	usedMain[chestNum] = false;
	keys[openKey[chestNum]]++;
	for(int i=0; i<chest[chestNum].size(); i++) {
	  keys[chest[chestNum][i]]--;
	}
      }
      else {
	update = true;
	ans.push_back(chestNum+1);
	break;
      }
    }
    if(!update) return noSolution;
  }
  return ans;
  
}



int main() {
  int t;
  cin>>t;
  REP(i,t) {
    vector<int> ans = solve();
    if(ans.empty())
      cout<<"Case #"<<i+1<<": IMPOSSIBLE"<<endl;
    else {
      cout<<"Case #"<<i+1<<":";
      REP(x, ans.size()) 
	cout<<" "<<ans[x];
      cout<<endl;
    }  
  }
  
  return 0;
}

xmas contest 2012 G問題について

ネット環境がよい場所に来たので書きます。
日本語が合っているかはよくわかりませんがどうぞ。

問題概要

平面上の格子点にn個の点があって、凸5角形が何個作れるか。
ただし任意の三点は同一直線上に存在しない
n<=400

解法

求めるのは、5点選んでそれの凸包が5点で構成されるもの。
したがって、5点選んで凸包が4点または3点で構成されるものを数え上げることが出来れば答えを求めることができる。

まず、４点の凸包のものについて考えてみる。
選んだ5点で、「ある3点で三角形を作り、内部に1点、外部に1点存在する」ようなものは2通りある。


f:id:tokoharu-sakura:20121228201400p:plain

次に3点の凸包のあるものについて考えてみる。
これも同様に
選んだ5点で、「ある3点で三角形を作り、内部に1点、外部に1点存在する」ようなものは2通りある。

f:id:tokoharu-sakura:20121228201407p:plain

さらに、「ある3点で三角形を作り、内部に1点、外部に1点存在する」ような5点の選び方をすると、上記のいずれかに当てはまります。
したがって、(「ある3点で三角形を作り、内部に1点、外部に1点存在する」ような5点の選び方 )/ 2を計算すれば良いことになります。

愚直に4重ループを回せば以下のようなシンプルなコード（変数名などは雑）ができます

LL yobi(PII A , PII B) {
	LL ret = (LL)A.second * (LL)B.first - (LL)A.first * (LL)B.second;
	return ret;
} 

LL menseki(PII A , PII B , PII C) {
	LL ret = yobi(A,B) + yobi(B,C) + yobi(C,A);
	if(ret<0) ret = -ret;
	return ret;
}

void solve() {
	int n;
	cin>>n;
	vector<PII> coor;
	for(int i=0; i<n; i++) {
		LL x,y;
		cin>>x>>y;
		coor.push_back(MP(x,y));
	}
	LL ans = (LL)n*(n-1)*(n-2)*(n-3)*(n-4) / 120;
	LL tmp = 0;
	LL cntA = 0;
	for(int i=0; i<n; i++) for(int j=0; j<i; j++) for(int k=0; k<j; k++) {
		int cnt = 0;
		LL total = menseki(coor[i] , coor[j] , coor[k]);
		for(int t=0; t<n; t++) if(t!=i && t!=j && t!=k) {
			LL hikaku = 
				menseki(coor[i] , coor[j] , coor[t])
			 + menseki(coor[j] , coor[k] , coor[t])
			 + menseki(coor[k] , coor[i] , coor[t]);
			if(hikaku==total) cnt++;
		}
		cntA += (LL) cnt * (n-3-cnt) ;
	}
	cout<<　ans - cntA/2  <<endl;
}


int main() {
	int t;
	cin>>t;
	for(int i=0; i<t; i++) solve();	
	return 0;
}

何分かしたら答えが返ってくると思います。
3点選んだ時の内部の点数の列挙ってどうするのが高速になるんでしょう。
すごいうまい方法があってもよさそうだなぁと思ったので誰か是非教えてください。


ちなみにこんな感じの解法を6角形にしてみた問題に適用させようとしましたが、位置関係の場合分けの時点で多すぎて死亡しました。5角形のうまく行きすぎ感がすごかったです。

2012年JAG夏合宿Day2の作問について

この記事について

この記事はhttp://partake.in/events/3fcea6d7-0bab-4597-82db-86439aadb1b9
Competitive Programming Advent Calendar Div2012の12/18の記事です。

コンテストの概要

9/15(土)(11:00-16:00)の http://judge.u-aizu.ac.jp/onlinejudge/contest_standing.jsp?id=JAGSummerCamp12Day2 で
shioshiota , not , kawatea さんと自分で出題をしました。

作問の機会を与えてくれたeomoleさんに感謝です。

この記事の目的

作問の経験をふまえて、よいコンテストにするにはこう準備すれば上手くいくのではないかなあというポイントについて書いていきます。
3-4人程度での作問を想定しています。

なお、このページに日時などが書いていますが、このようなスケジュールでよく準備ができることは保証できません。多分全体的にもう一週間くらいみておくと余裕を持って作業ができると思います。

もくじ
  • A : いろんな案を出そう
    • A1 : wikiで積極的に書き込む
    • A2 : 問題ドリブンと解法ドリブン
    • A3 : 問題の案が増えれば選択肢も増える
    • A4 : できるだけオフラインで集まろう
  • B : スケジュールは大事
    • B1.ネタを出す時間を作って、最後はオフラインで問題を選ぼう
    • B2.準備するコードは結構多い
    • B3. 問題文を作る時間を計算に入れよう
    • B4.スライドを作る時間も考えよう

A.いろんな案を出そう

今回のコンテストでよかったと思うのは、複数人の相互作用でできあがった問題がいくつかあったことだと思います。

A1.wikiで積極的に書き込む

問題案をたくさん出すという意味でも大事ですが、それに突っ込みを入れるのも相手の考えとのギャップを埋めるのによいと思います。
shioshiotaさんが積極的にやっていた覚えがあります。

A2.問題文ドリブンと解法ドリブン

今回のコンテストの準備では両方のアプローチがあって、7-8割は解法ドリブン、もしくは原案そのままという感じだったように思っていて、残りは問題文ドリブンで出来上がったように思います。

問題文ドリブンで作られた問題はDと、Bの一部分だったように思います。

どちらも問題として出来上がるまでの流れが面白く、作問側としては記憶に残るものでした。
ただ、どちらも最初想定していたよりもだいぶ難しくなってしまったのでコンテスタント側からすれば困った問題だったかもしれません。

A3.問題の案が増えれば選択肢も増える

問題を出しても無駄になってしまうのは惜しいという気持ちはあるが、そこまでケチケチしないほうがよいです。

というのは、今回はICPCの地区予選の練習ということで、バランスや問題の特色（複雑な設定とか重い実装）を似せるほうがよいため、そういう意味で制約が多いものになります。少ない案しか出ていないと問題採択の選択肢が減ってしまっていたと思うので、そのあたりはよかったと思いました。

初回の会合までに完成度の高い問題からそうでないものまで17の案が出されており、自分はこれくらいあれば楽勝だと思っていました...が、実際にはそうはいかずに未決定のものを残しつつ完成した問題から作業を進めることになりました。

A4.できるだけオフラインで集まろう

作問の作業というのはオンラインで作業できることがだいたいですが、それでもオフラインで集まった方が作業が捗ります。
さらに、問題の微調整もしやすいので効率的だと思います。

実際、問題の細部の調整はみんなが集まっているときにできたものがいくつかあります
(例えば、Bの全探索お姉さんの座標系、動き方のルールなど

B.スケジュールは大事

今回のコンテストだと日程はほぼ確定しているのでどのくらいのことをどれくらいにするか逆算しないといけません。
このときには、唯一の経験者だったshioshiotaさんにスケジュールなどの助言をお願いしました。

B1.ネタを出す時間を作って、最後はオフラインで問題を選ぼう

A3の理由で、ネタはたくさんあった方がよいのと、問題採択のときに全員が共通の認識を持てて、問題の修正も容易にできます。

チームが結成されたのは8月上旬（だったはず）で、初めて集まったのは8/24でした。
その日は7問(本番ではA,C,F,G,H,I,J)が修正されつつ選ばれ、2問(本番ではB,D)をもう少し考えよう、という形にしました。

B2.準備するコードは結構多い

それまではあまり意識していなかったのですが、準備するべきコードはたくさんあります。ですので、スケジュールを考えるときにはこれも意識するようにしましょう

hama_duさんの記事http://hama-du.hatenablog.com/entry/2012/12/10/231757 でも触れていますが、入力ジェネレーター、入力チェッカーのほかに、問題によっては出力チェッカーもいります。
問題を解くプログラムだけでも、想定解法(作問者+テスターのふたつ) , 想定誤解法 , 想定TLE解法といった具合に、たくさんコードを書く必要があります。（そうでないと、コンテスト直前に条件を変更するときに柔軟な対応をとれなくなってしまいます。

そのため、自分で作った問題でコードもすぐにかける、という問題でも思っていたよりも時間がかかってしまうと思います。

今回の作問ではこれらのコードの管理はnya3さんのrime(https://github.com/nya3jp/rime/)が使われました。

B3. 問題文を作る時間を計算に入れよう

最初、この作業を「日本語だし楽勝だろう」と自分は完全になめていました。shioshiotaさんに大変だといわれて意外に思っていましたが実際大変でした。

大変なのは具体的には以下の通りです

  • ICPCに似せるとすると問題文が長いこと
  • ICPCの問題は入力変数も多く、その分説明が増えること。
  • 書き方が悪いとcontestantが誤読をしてしまう可能性があるので細心の注意を払う必要がある

誤字どうこうではなく、表現のレベルまで見直さないといけないので結構大変です。
最終チェックはオフラインでやる形になりました。このときに、一斉に読んでみて「この表現はこうした方がよいのでは」などの話をして次の問題へ…という風にやっているとかなりの時間が経過していた覚えがあります。

B4.スライドを作る時間も考えよう

あまり作っていなかったのでいろいろ痛い目を見ました。
特に自分はよいスライドの作り方を心得ていなかったこともあり、
解説当日のスライドはなかなか悲惨だったと思います…。
ちゃんとレビューしてもらうべきでした…。


余談

  • D問題はもとは僕が題名だけつけた問題で、その後notさんを中心に問題が深められていきましたが、コンテスト一週間前に想定解法が誤解法だということがわかって冷や汗をかいたりして、思い出が多いです
  • qnighyさんにAdventCalendarの記事の相談をしたところunion-findの計算量解析を提案してくれましたが、結局やりませんでした。春休みの宿題にさせてください
  • 今年の序盤くらいにはDPの記事を書いてやるーと意気込んでいたりしましたが、いろいろと書いているうちに自分でも収拾がつかなくなってしまい、結局お蔵入りになってしまいました。

チェックした問題

http://d.hatena.ne.jp/anta1/20120730/1343650604 リスペクトanta1さん

今まで見た問題は確実に無理だし、昔見た系は使わないかも
最近もっぱらtopcoder系のまとめにしか使っていない

◎ 初見で解けた
○f 自分で解いたが、Practice System TestでFailedしてResubmitした
○ 解説/回答を見て解けた(自分でコードを書いた)
○- 他の人のコードをほぼ丸写し
○' 昔やってあったが、それが初見かどうかとかはわからない
△ 解説/回答を見てなんとなくわかった気がするが、自分のコードを書けてない
△? わかったかどうか微妙な所
△- ちょっと解説を見てへえと思っただけくらい
% 近似解もスコアのつく問題で、良いスコアではない
× 見ただけで出来てない。回答を見てもわかってない
？ 記録がないし、昔解いたかもしれないが忘れた

SRM

div1Medium

問題 状態 pt/max 解いた日時 コメント
463 ◎ 326.37/500 2013/3/19 規則性に気づくのに時間がかかる。1.1以上にされると死にそう
464 ○ no/550 13/3/19 答えみたら簡単だった
465 ○f 180.00/600 13/3/19 LLに直したら通った
466 ○' まぁすぐ思いついたし
467 ○ 晩飯を挟んだ
468 ○f 150.00/500 13/4/2 前処理/コーナーケース
469 ○ (null)/500 13/4/2 方針の時点で死亡
470 ◎ 355.00/500 13/4/2 前回は346だったらしい
471 ◎ 217.69/500 13/4/3 解法はすぐだが迷った
472 ○ (null)/600 13/4/3 数え上げ能力の不足
473 ◎ 416.06/500 13/4/4 easy.
474 ○f 240.16/500 13/4/4 easyなのに誤読+resubmit
475 ○f 180.00/600 13/4/4 6submit
476 ○f 165.00/550 13/4/7 確率bitDP,corner , 要再挑戦
477 ○f 175.58/500 13/4/9 2resubmit, 制約読み違え, 条件忘れ
480 ◎ ???/450 13/5/18 medとは思えない簡単さ
481 ◎ 390?/500 13/8/3 easy.初期化バグ
486 ○ ???/450 13/9/30 多分再帰でも書ける。シンプル確率
487 △ 面倒なだけっぽいので飛ばし
491 ○ 180/600 13/10/5 解くのに時間がかかる。TLE食らった
492 ◎ 179.91/550 13/10/6 時間かかる。良問
493 △ 面倒なだけっぽいので飛ばし
494 ◎ 209.4/500 13/10/7 自分が弱いパターンの問題っぽい
495 △ 普通に意味取り違ってた。あと詰めあまい(書いてない)
496 △ 考えればわかるが解くのは省略
497 △ めんどい
498 △
499 ○' 165/550 13/12/15 類題ということに気づかず非常に悔しい
501 ◎ 329.87/500 13/12/22 やりやすいDP
502 ? 昔解いてた。解法も(例のGreedyをわかってれば)簡単。
503 ◎ 288.43/500 13/12/22 この界隈によくある確率問題
504 ○f 150/500 13/12/22 誤読+resubmit. swapとflipは違います
506 13/12/29 簡単
504.5 ◎ 450?/550 13/12/30 Medとは思いがたい簡単さ
507 ◎f 150/500 13/12/30 SimpleMathだが、ハマってしまった。ありうるパターンを列挙しきれていなかった。
513 ◎ --/500 14/2/6 確率。詳細を詰め切れなかった

Div1Hard

問題 状態 pt/max 解いた日時 コメント
466 △? わからん
467 ☓ わからん
473 ◎ 432.44/1000 2013/4/4 複雑数え上げ
474 わかんね
481 ◎ 317.05/900 2013/8/4 誤読・方針迷走
487 ○' ???/950 ??? かんたんなD1H
491 ☓ わからん
494 △ flip,2のべき乗のパターンだけ把握
495 ◎ 295?/950 13/10/8 面白い対応付けのできる問題
496 ☓
497 ○' 解いたことはあるが忘れた
498 △ 13/12/15 答えを見て一応理解したつもり（だがすぐに忘れそう
499 △ 13/12/15 解法はわかるが実装は無理な気がする
506 13/12/29 惜しいかもしれないが結局解けず解説を見る
504.5 13/12/29 一目簡単
512 ○f 13/12/31 自分で考えれてよかった。数え上げ。
590 ○ 300/900 2013/9/9 フロー
612 ◎ 328/900 14/3/27 簡単なHard(時間かかった

Codeforces系

識別子 問題 タイトル 状態 pt/max 解いた日時 その他 コメント
172Div1 A ◎ 2013/3/10 初見では場合分けが必要。これに適したライブラリがあるので使えるようにしたいところ
172Div1 B ◎ 2013/3/10 綺麗な構造。priority_queueとリストを使えばさらさらとかける
172Div1 C ○ 2013/3/10 式が綺麗だが、なぜこのように解けるのかがわからない。深さの逆数の総和

OI系

識別子 問題 タイトル 状態 pt/max 解いた日時 その他 コメント
APIO 2007 backup ◎ 100 2013/3/3 リスト構造+priority_queueの面白い問題

一般OnlineJudge系(POJ,SPOJ,ZOJ,AOJ,CodeChef)

識別子 問題 タイトル 状態 pt/max 解いた日時 その他 コメント
AOJ 1185 チョコレート分割 ◎ 2013/3/11 スキー合宿のバスの中で考えてたら解けました

特殊(?)OnlineJudge系(HackerRank,ProjectEuler(ネタバレしないように))

||識別子|問題|タイトル|状態|pt/max|解いた日時|その他|コメント|