今年も参加してきました〜！！(@huskyB4llと@sosamjayo)
www.yamagula.ic.i.u-tokyo.ac.jp
去年はこちらです
コンテスト中の様子
[16:30] 僕「は？サイト繋がらないじゃんwwTwitterみよ〜」
[16:40] 僕「は？B全くわからん．愚直にやっていいんか，なんか上手く判定できる条件あんのかわからん」
[16:55] 僕「B解けたwwwやるだけでしたww」
マクロいっぱいですみませんが，こんなコード書いてました．「変更できるのは列か行か，何列/行目」をペアにしたキューに入れて順に処理してました．
int main() { while (1) { int h, w; cin >> w >> h; if (h == 0) break; queue<pair<int, int>> q; q.push({0, 0}); vvi v(h, vi(w, INF)); vi x(w, INF); vi y(h, INF); x[0] = 0; rep(i, h + w - 1) { int a, b, c; cin >> a >> b >> c; v[b - 1][a - 1] = c; } while (!q.empty()) { auto t = q.front(); q.pop(); int num = t.se; int type = t.fi; if (type == 0) { // 列を確認 for (int i = 0; i < h; i++) { if (y[i] != INF) continue; if (v[i][num] == INF) continue; y[i] = v[i][num] - x[num]; q.push({1, i}); } } else { for (int j = 0; j < w; j++) { if (x[j] != INF) continue; if (v[num][j] == INF) continue; x[j] = v[num][j] - y[num]; q.push({0, j}); } } } bool ans = true; rep(i, w) if (x[i] == INF) ans = false; rep(i, h) if (y[i] == INF) ans = false; YN(ans); } }
この辺りでA担当してたhuskyとsosamjayoがAバグらせ太郎をしてました．
[17:05] husky+sosamjayo「A解けたwww」
この辺りで僕がCを考えてたんですが，"""ヤバさ"""を理解してて困ってました．standingの様子からD狙いに移ります．
[17:10] 僕「Dこれ貪欲で良くね？」
sosamjayoと主に話してて，サンプル2で合わないことがわかります．
[17:15] 僕「Dこれ末尾3つ全探索であとは貪欲で良くね？」
良さそうですが，超怪しいです．saosamjayoとhuskyと三人で本当か検証します．
謎証明により「ヨシ！w」の合図が出ます(※証明間違ってます)．提出します→WA
ここからいっぱい嘘解法を考えます．落ちるテストケースが知りたいので，僕作のrimeのようなテストツールを使います．
(間違えてb_i <= 100だと勘違いしてますが)以下のケースで落ちました...
8 100 8 51 41 30 39 64 16
[18:00] husky「末尾3つ全探索で，末尾3項の(min,max)に含まれる要素は列の中間に，他の要素は前半におけばいいんじゃね？」 要はこんな感じです
8 [100 8] [51 41 30] [39 64 16] (64-16の範囲外を降順) (64-16の範囲内を降順) (全探索した3つ)
当然のようにダメでした．そのまま嘘を大量に生成してました......
結果
92位でした．C以降が解けなかったのが戦犯です．あーあ．
