ICPC2022国内予選参加記

今年もICPCに出場したので参加記を書きます。

チーム名はCUPC、メンバーは昨年と同じではにゅ(@hanyu_ipf), stoq(@stoq_), ころも(@uytvcc) の3名です。昨年は惜しくも予選敗退という結果に終わったのと、はにゅさんは今年が最後のため、今年は特に集中しました。

問題：
icpc.iisf.or.jp

～前日

自分が院試*1を控えてるのとはにゅさんが忙しいのもあって、チームで集まって練習したのは模擬国内だけでした。前日は申し訳程度に ABC と AOJ-ICPC を解きました。

開始前

ご飯を食べたりレッドブルを買ったり胃腸薬を飲んだりして整えていました。

ころもくんは大学の授業の関係で途中から参加するとのことだったので、最初は自分がA、はにゅさんがBを担当することになりました。

コンテスト本番

事前に打ち合わせしたように、まず自分がA、はにゅさんがBを開きました。

Aは素直な実装問題で、素早く実装しつつ絶対にペナを出さないよう何回も見直しました。緊張しながらsubmitするとAC。(4:19)
かなり速いと思っていたのですが、他のチームはもっと速くてびっくり。

ほどなくしてはにゅさんがBをAC。(28:54)
Bは本番中チラ見しただけでしたが、後から見返すとかなり重い実装問題だった（実際苦しそうだった）のでノーペナで通してくれてとても助かりました。

続いてCを開くものの、解法がすぐには思いつかなかったので少し焦ります。

二乗和なので、直感的には練習日を連続させ休息日を分断するのが最適に見えます。しかし直接的に最適解の構造が求まるのかどうかが不明瞭でした。そもそも $N,M\leq 10^6$ なので、直接求めるのではなく何かしらを全探索するのかなぁなどと考えていました。

そこでひとまず実験することにしました（ここえらい）。

すると最適解では

休息日は、いくつかの練習日によってほぼ均等な長さに分断されている

練習日は、一箇所だけ連続していて、残りの個所は単独で存在している

ことが判明。これにより練習日の連続している部分の長さを全探索する解法が可能となり、バグらせつつもなんとか実装しました。

しかし提出すると Wrong Answer の文字が。実験する前に $n\geq m$ の場合のみ途中まで書いていたのをそのまま残していたのですが、そこが嘘解法でした。該当箇所を全部消してもサンプルはあったのでそのまま提出すると AC。(43:16 +1)
折角愚直解を書いていたのだから、きちんとストレステストをすべきだったと反省しました。

その後Dを2人で考察します。

手元で例を書きだし、ひとまずは条件を満たす分断が存在するかだけを考えることにしました。手元での実験の過程をそのままプログラムとして実装可能に見えたので、書き起こしてみることに。

実装方針としては、

$t$ の要素を前から順に見ていき、実際に $s$ を分断しながらシミュレートする。列の先頭要素は std::set で管理する。
もし $t_i$ が先頭要素の集合に含まれていなければ $t_i$ の直前で $s$ を分断し、 $t_i$ を先頭要素の集合に入れる。
その後、もし $t_i$ が先頭要素の集合の中で最小でない場合、どうやっても $t$ の順にはならないので即終了する。最小の場合はそれを集合から削除し、 $s$ における1つ次の要素を集合に入れる（存在し、かつ未使用の場合）。

となります。これにより「絶対に分断されないといけない箇所」がわかります。もし「絶対に分断されないといけない箇所」の個数が $k-1$ 以上の場合は $t$ の順にできないので、これもまた即終了します。

問題は残りの箇所で、「分断してもしなくてもいい箇所」「分断してはいけない箇所」があります。

$s_i$ の直前を分断しても順番が変わらないための必要十分条件を考察します。
まず必要条件として、 $t$ において $s_i$ より左に $s_i$ より大きい要素があってはいけません。何故なら $u \gt s_i$ が $t$ において $s_i$ より左にあるならば、本来 $u$ が取り出されるタイミングで $s_i$ が取り出されてしまうからです。

そこからしばらく考察すると、先程の必要条件は実は十分条件でもあるのでは？と思い始めました。
実際、これは十分条件になっています。 $t$ の左の要素が全て $s_i$ 未満ならば分断しようがしまいが $s_i$ の取り出されるタイミングは変わらないので、全体の取り出される順番は変動しません。（コンテスト中は非自明だと思っていましたが、今見るとそうでもないかも）

さらに「分断してもしなくてもいい箇所」の選び方は独立に決めることができます。これは分断によって全体の取り出される順番が変わらないので、結局分断していないのと同じとみなせるからです。この性質が重要で、これにより単純な二項係数で解を求めることができます。

以上を実装するとサンプルが合い盛り上がりました。実装では一箇所サボって $O(n^2)$ になっていましたが実行は爆速で終わりました。はにゅさんの助言もあってとりあえず出してみることに。

するとなんと一発で AC。(1:23:28)
研究やら院試対策やらのおかげで正当性の証明に耐性がついていたのでよかったです。

本番中のコード（本質部分のみ、あまり綺麗ではない）

void solve() {
  int n, k;
  cin >> n >> k;
  if (n == 0) exit(0);
  vector<int> p(n), q(n);
  cin >> p >> q;
  p--, q--;
  vector<int> pos(n);
  rep(i, n) pos[p[i]] = i;
  vector<bool> used(n);
  vector<bool> cut(n);
  cut[0] = true;
  set<int> tops;
  tops.insert(p[0]);
  for (auto qi : q) {
    int i = pos[qi];
    if (not tops.count(qi)) {
      cut[i] = true;
      tops.insert(qi);
    }
    if (*tops.begin() != qi) {
      cout << 0 << "\n";
      return;
    }
    tops.erase(qi);
    used[i] = true;
    if (i + 1 < n and not used[i + 1]) {
      tops.insert(p[i + 1]);
    }
  }
  int div = accumulate(all(cut), 0);
  if (div > k) {
    cout << 0 << "\n";
    return;
  }
  int can = 0;
  vector<int> q_pos(n);
  rep(i, n) q_pos[q[i]] = i;
  rep(i, n) {
    if (cut[i]) continue;
    bool valid = true;
    int j = q_pos[p[i]];
    rep(jj, j) {
      if (q[jj] > q[j]) {
        valid = false;
        break;
      }
    }
    if (valid) can++;
  }
  mint ans = 0;
  rep(i, min(k - div + 1, can + 1)) { ans += bc.C(can, i); }
  cout << ans << "\n";
}

int main() {
  while (1) solve();
  // solve();
}

千葉大学からは~~例年通り~~1チームしか出ていなかったのでこの時点で予選通過がほぼ確定し、肩の荷が下りました。

ここら辺でころもくんとも合流し、3人でE, Fを考察します。

Eは問題文を流し読みすると「像には美しい像と恐ろしい像の二種類があり、」の文字列が見えたので「これ2-SATでは？」などと発言しましたがちゃんと読むと全然違いました。ごめん。しかもはじめ和が $0$ か $0$ でないかと誤読しており、サンプルを見てようやく気付きました。ごめん。

誤読に気付いた後は、行・列の少なくとも一方が $1$ の交点を全部決めた後、どちらも $0$ の交点で辻褄を合わせる、という方針を考えましたが、反例を発見し断念。括弧列との対応も考えましたが、特に何もありませんでした。

ヒューリスティックが得意な人なら焼きなましで通せそうだなぁという会話もしていました（マラソン詳しくないので実際どうなのかはわかりません）。

Fは構文解析の問題ですがBNF自体はとても簡素なもので、アルゴパートが本質のように見えました。
ころもくんが前から貪欲に解く解法を提示してくれましたが、はにゅさんが反例を発見し頓挫。制約、問題設定的に貪欲ではなさそうという結論になりました。

せめて3乗でも思い付けたらマシンぶん回しで解けるのに、などと考えていました。

コンテスト終了後に解説を見てなるほどなぁとなりました。構文解析において構文が木構造になっているのはよく知られていますが、構文木を陽に持って木DPする問題は見たことがなかったので盲点でした。構文木くらいは思い付きたかった。

G,H はほとんど読んでいません。Hに謎の図があったのだけ記憶に残ってます。

そうこうしているうちにコンテストが終了。
3h コンですが、体感時間は一瞬です。

結果

ABCDの4完28位でアジア地区予選に進出しました！

奇しくも一昨年にチームharaharaとして出場したときと同じ順位です。

去年はほとんど自分のせいで落ちてしまい負い目を感じていました。今年はその雪辱を果たす形でしっかり解くべき問題を解けたので達成感があります。
今年も快く組んでくれたチームメイトの2人とコーチに感謝です。

さらに例年通りなら1問以上正答したチームのうち上位10%に対し表彰状が与えられるはずで、今回そのようなチームは283チームあるのでギリギリ表彰の対象に入っています。それも嬉しいです。

12月の横浜大会がとても楽しみです。オンサイトがいいな…

*1:助けて