以下の内容はhttps://rian.hatenablog.jp/より取得しました。

JAG の 2024 年 (WIP)

ICPC

これはなに

備忘録です。特に公開しても問題なさそうな範囲で書いているつもりではありますが何かあればご連絡ください。

また、ほとんどを rian_tkb 視点で書いています。一応コンテスト責任者という立場で各種動き出しの部分や進捗管理やセット全体の品質管理などを担当しており、主に名前がついていないような細々した「それ以外全部」に該当する部分のタスクをやっています。 一部ほかの人に委譲しており、特に夏合宿予約周りは tsutaj に引き継いだ後記憶を失っているので薄いかも。

本当は一気に一年分書くつもりだったのですが時間がなかったのでいったん模擬国内まわりまで書いてあります。追記予定。

2023-09-18（夏合宿 2023 day 3）

オリセン予約

tsutaj 2023-09-18 11:47:53
来年の夏合宿の仮予約をしました。スタッフとして参加したい方は予定をあけておいてください！
• 日程：2024/09/14〜16
• 場所：オリンピックセンター
来年は 2 日目に懇親会を実施する方向で進んでいます

来年の夏合宿のためにオリセンを予約します。

nyc.niye.go.jp

オリセンは利用日の一年前から予約でき、ぼーっとしてるとわりと予約埋まりがちなのでこのタイミングでするのが安牌です。 特に大部屋の大きさは変えられないので、参加人数を見誤るとこまります。

2023 年分はこの施設予約周りも自分がやっていたんですが、2024 年分および 2025 年分は tsutaj に任せています。

2024-05-12

日程調整 (2024-05-01)

rian 2024-05-01 20:47:11
模擬国内予選に向けた日程決めおよび問題選定を目的とした会議を行いたいと考えています。
つきましては、以下のリンクから日程調整にご協力をお願いします。

問題案の不足が予想されますので、問題案の追加、推薦もよろしくお願いします。
問題案の追加方法に関しては以下のページを参考にしていただき、わからない部分等ありましたら slack にてお気軽にご質問ください。

rian 2024-05-01 20:52:34
上の会議は活動会議も兼ねるつもりです。具体的には年間計画についての共有、意見募集と役職の更新（やってくれる人がいれば）などを予定しています。

国内予選本番の日程が決まったあたりで動き出します。具体的にはまず会議の日程調整をします。

活動会議

年間計画

rian 2024-05-12 19:21:47
ではまずは 2024 年の活動会議から始めていこうと思います（見ながら引き続き問題案への投票等していただいて問題ありません）

rian 2024-05-12 19:23:06
JAG では毎年「模擬国内予選」「夏合宿（or 模擬地区予選）」という 2 つのコンテストを開催していて、今年も同様となることを予定しています

会議をします。

そういえばここで夏合宿と WF がかぶっていることが発覚しました。

rian 2024-05-12 19:25:52
昨年までと一つ異なる点としてプレーオフが存在するのですが、こちらの模擬コンテストに関しては以下の理由から開催しない方針で行こうかなと考えています。
• シンプルに準備が大変
• 模擬地区予選との差別化点がほとんどない（本番のシステム含め）

rian 2024-05-12 19:26:33
（めちゃくちゃやる気ある人がいれば開催しても良いかなとも思っているのでめちゃくちゃやる気ある人がいれば……）

プレーオフ（でいいんですかね、まだいまいち何と呼べばいいのかわかっていない）へのスタンスは現状これです。来年度以降どうなるかはわからないですが、少なくとも今年度は模擬プレーオフはやらないかな……

役職引継ぎ

rian 2024-05-12 19:31:08
じゃあ続いて役職引き継ぎに移ろうと思います

rian 2024-05-12 19:34:22
個人的には、いま自分がやっているプロジェクトリーダーに関して、誰か手伝ってもらえるとありがたいなぁと思っています。
今月が特に本業がかなり忙しくなりそうなので、JAG の模擬コンテストに関してある程度わかってる人に手を動かす部分をすこし肩代わりしてもらいたい気持ちがあります

（中略）

rian 2024-05-12 19:41:25
プロジェクトリーダーに関してはできそうな人に積極的にいろいろな仕事を振りまくることでなんとかしようと思います（みなさんご協力お願いします）

役職引継ぎに、失敗……

模擬国内会議①

日程決定

rian 2024-05-12 19:44:52
まず模擬国内の日程に関して

rian 2024-05-12 19:45:46
icpc 本番は 7/5 (金) だそうです
https://icpc.iisf.or.jp/2024-yokohama/domestic/

まず日程を決めます。国内予選本番は大体金曜なのでその 2 つ前の土日（今回だと 6/22, 23）を第一候補に、以下のイベントを調べてかぶらないようにしています。

  • TOEIC
  • 主要な大学の学祭
  • コンテスト（特にオンサイト、予選、本選など）

今回の場合は、以下のイベントが確認されたので、6/29（土）になりました。

  • 6/19 - 24：Universal Cup Summer Summit (Semifinals)
  • 6/23（日）：TOEIC
  • 6/29 - 30：ICFPC

ちなみに、特に AtCoder に対してはなにか非公開のイベント等とかぶってないかを確認しています。以前は知ってそうな人に DM で聞いていたんですが、やはり忙しいらしく最近はお問い合わせフォームから聞いています。

問題選定

rian 2024-05-12 19:01:36
さっき帰宅したばかりで準備が全然できてないのですこし準備させてください。

その間にやっていただきたいこととして「問題案の推薦（投票）」があります。
具体的には、模擬国内で使う問題について以下のスプレッドシートから推薦を行ってください
推薦方法に関してわからなければこちらのページを参照してください

問題選定をします。具体的には内部で管理されている問題原案を各人が推薦することで選定していきます。

特に国内予選形式の場合、以下の制約を受けるので採用できる問題に制限があります。

  • 実行時間制限を設けられない
  • 入力ファイルのサイズ制限
  • 出力ファイルのサイズ制限
rian 2024-05-12 20:33:19
とりあえずいまある問題案だとあまり（特に F, G に）適切そうな問題がないのと、まぁそれくらいの問題なら待てば案が出てくる気もするので、来週また会議してそのタイミングで残り 4 問決めましょうか

JAG では問題案が枯渇しており、この日は 4 問しか埋まらなかったそうです。残りは来週にもう一度会議を行うことで決定します。

ログを見ると最終的に D, F, G, I に割り当てられた問題がこの日に採用されたようです。

意外かもしれないですが、最近は一部の人々の努力によりボス問がなくて困るということは比較的少なくなってきました。本当にありがたい限りです。一時期は毎回異常幾何を（自分が）用意してなんとかセットとしての体を保っていたのを思い出すと、圧倒的改善……。

2024-05-19

日程調整 (2024-05-14)

rian 2024-05-14 18:25:55
今週末に模擬国内予選に向けた会議を行いたいと思います。
つきましては、以下のリンクから日程調整にご協力をお願いいたします。

一部問題案が不足しておりますので、問題案の追加、推薦もよろしくお願いいたします。

します。

模擬国内会議②

残りの問題を埋めます。原案を出してくれそうな人に圧力をかけることで（＋自分でも多少出すことで）原案不足をなんとかします。

rian 2024-05-19 13:29:00
A 問題っぽい問題がおそらくないので、いまここで作れば高確率で採用されると思うのでぜひどうぞ
（wiki に清書するのはあとにしてここに適当に書き込むでも良いです）

意外かもしれないですが毎回序盤の問題案がなくて最後の最後にその場で提案されて決まることが多いので、レートが高くない人も A 問題や B 問題を提案すると高確率で採用されるのでおすすめです。

あとはログを見たら H 問題（物理実験）を TLE 解法で通されないようにどうすればいいか、という議論をしていました。結局は特に改題せず本番 1 AC になっていたので大丈夫だったっぽい？

rian 2024-05-19 14:42:09
そうしましたら議事録の方に転記しましたので、担当に入っていただける方は名前を入れてください

rian 2024-05-19 14:43:42
データセット担当の作成するもの： 入力データセット・入力検証器・（出力検証器）・解答プログラム
問題文担当の作成するもの： 問題文・入力検証器・解答プログラム

あくまでメインの担当になるだけで、他の人も generator の追加や問題文の校正などの補助には入ります

初めての人でも教えるのでぜひお願いします（A, B 問題あたりは準備が楽なはずなのでおすすめです）

問題が決まったら担当を決めます。

といっても会議中に半分以上決まったらいいほうで、誰も入らずに放置された担当箇所は後々にベテランに処理してもらってなんとかしています。

準備開始

この日にすでに準備を開始していたようです。えらい。

具体的には以下をしていました。

  • 内部ページ、各問題のチャンネル、github、google docs などの作業環境の整備
    • ログをよく見たら後半 2 つはもう少し後だったかも
  • スケジュール引き
    • 実際にはこの通り進むことは少なく、内部コンテスト時には全然未完成だったりコンテスト開始してから解説を書き始めたりしてします……。
〜 6/9 問題の仕様の整理、簡単なデータセット (サンプル、雑ランダム程度)、各種検証器の完成
〜 6/16 ジャッジ解、問題文仮完成、校正開始
〜 6/22 データセットの補強、校正担当者の校正とその修正が1度以上行われる
〜 6/22 or 23 内部コンテスト
〜 6/29 フィードバックを受けて修正、解説作成、本番
  • 日時確定、公開用ページ作成、Twitter での告知

～ 2024-06-23

模擬国内準備

ひとまず内部コンテスト（JAG 内部での test-run、模擬模擬コンテスト）までに最低限形になっていることが条件なので、それを目指して準備を始めます。

「最低限形になっている」の定義はおおまかに以下です。

  • だいたい正しく解釈できる問題文が用意されている
  • サンプルが一つ以上存在する
  • だいたい妥当な制約が設定されている
  • ランダムケースだけでも良いのでテストケースが存在する
  • 想定解のコードが存在する

これらを各問題の担当に入った人が各々の進め方で用意していきます。 JAG 内部での知見や使われているコードなどもないわけではないですがここでは割愛します。気になる人は JAG 内部で聞いてください。

rian 2024-05-25 16:36:05
まだ [github repo] が無なんですが、今日中に最低限整えて作業してもらえるようにする予定です

rian 2024-05-25 19:26:38
[github repo] を一応最低限整備しました，具体的には以下をしました
• 各問題のフォルダの作成
• statements-manager の設定
• H の問題文作成（statements-manager で問題文を書くのの参考に）
• README に statements-manager 周りの簡単な使い方記載
    ◦ rime 周りは力尽きて書けなかったんですが，わからない部分は聞いてください
このあと余力があれば参考になるように A か B のごく簡単なテストケースを作るかもしれないです

各問題に閉じないタスクもいくつかあるのでやっていきます。まずは各種設定や環境を用意する部分。色々手作業が多いので自動化していきたい……（年に数回しかやらないので毎回手作業に甘えてしまう）。

この辺で問題数や提出方式の変更についてのアナウンスがありました。びっくり。

rian 2024-06-21 18:43:44
マジで今週時間が取れずマジでやばいんですが、とりあえず一問追加はしたい気持ちがあります
とりあえず一問案を置いておきました
他に既存の問題案での推薦や新たな問題案の提案など募集中、今日中には少なくとも問題案は固めたい気持ちがあります

たまたま自分が仕事でこの時期ほとんど東京にいなかったのもありこの辺への対応が遅れて、追加の問題が決定したのは 6/21 あたりでした（ちなみにここで追加されたのは B 問題でした）。

icpc.iisf.or.jp

また、模擬国内では実行委員会から予選システムを借りてコンテストを行っているため、予選システムを借りていい感じにアクセスできるように設定するなどします。 この辺は JAG のサーバー周りを管理してくださっている shora さんにお任せしています。

rian 2024-06-23 01:33:08
諸々時間が取れておらずすみません、とりあえず内部コンに向けた校正や体裁を整える部分などを今から行います。
（すでに皆さんにかなりやっていただいていることは把握しています、ありがとうございます 🙇）
それとログを見た感じ入力サイズや想定解の実行時間についてはいくつか気になるところがあるので、内部コンには間に合わないかもしれないですが少し提案をしたりするかもしれません（議論はなんとなくは追っているのですでにかなり頑張って調整いただいていることは承知の上ではありますが…）

rian 2024-06-23 01:34:00
*Thread Reply:* 作業状況スレ

rian 2024-06-23 01:34:56
*Thread Reply:* • :funini_done: 手元で rime test 実行（全然おわんねえ…）
• :funini_done: 問題文の校正、提案の処理
    ◦ :funini_done: とりあえず一通り校正
    ◦ :funini_done: html 出力してみて確認，修正
        ▪︎ :funini_done: C 問題の数式が全然反映されておらず，困った（html の書式で再現してるだけで存在しないものがあるからかなぁ）→ 多分直った
• :funini_done: 新 B 問題の問題文作成
• :funini_done: 問題 ID の振り直し

（中略）

rian 2024-06-23 06:39:36
新 B 問題をとりあえず形にして（darsein さんありがとうございます 🙏）問題 ID 振り直しました

rian 2024-06-23 06:40:32
現状の問題文はこの辺のファイルをブラウザで開くと見れます，何かおかしなところや直したいところなどあれば言ってもらえれば

セット全体の進捗管理、品質管理などを自分が担当しているんですが、たまたま仕事が忙しい時期とかぶってしまいこの辺が壊滅していました（一部 darsein さんなどに巻き取っていただきました）。 内部コン前日の深夜に無理矢理時間を作ってなんとかしていきます。

2024-06-23

内部コンテスト

JAG の内部でテストランをしてもらいます。 実際のコンテストサイト等を使うわけではなく、rime を使って自己採点をしてもらう方式を取っています。

ほぼ毎回 hos さんが参加してくださるんですが、毎回一人でちょうど本番 1 位相当くらいの完答数をたたき出してくださって大変助かっています。

～ 2024-06-28

模擬国内準備

内部コンテストでのフィードバックを受け、調整などをしていきます。

rian 2024-06-28 02:26:12
寝落ちから目覚めたので最終調整をします，主には以下
• I の制約調整
    ◦ 結局このままの制約にして，場合によってはデータセット公開時におすすめの TL 設定について但し書きしておく方向性を検討中
• G の制約調整
    ◦ n <= 1500 になっているのを確認しました，🙏
• 問題順の変更
    ◦ 👍 がいっぱいついているので ABGDCEFHI にしようかなと思います．意見あれば今なら調整可
• その他最終確認

rian 2024-06-28 02:59:44
*Thread Reply:* • :funini_done: CI を見て落ちてるの確認，調整

rian 2024-06-28 03:11:56
*Thread Reply:* • :funinidone: 問題順変更
• :funinidone: 問題文中の ID 変更

rian 2024-06-28 03:22:45
*Thread Reply:* • :funini_done: TODO: 問題文確認，提案受け入れ

rian 2024-06-28 05:11:41
*Thread Reply:* • :funini_done: 本番用（装飾のない）問題文生成

実は rime 上で問題ができていれば終わりでなく、問題文をコンテストシステムに合わせて組版したり、スペシャルジャッジの場合コンテストシステムに合わせた形式でジャッジが書かれている必要があったりするのでやります。

2024-06-28 ～ 2024-06-29

模擬国内 リハーサル

リハーサルを開始します。特に模擬国内に関してはリハーサル用のデータ等は使いまわしの部分がある程度多いので、特別な準備はそこまで多くないです。

mtsd 2024-06-28 22:49:50
解説の置き場ってすでに用意されてたりしますか？

rian 2024-06-28 22:50:23
用意されていません／今から用意します，5分くらい待ってください

mtsd 2024-06-28 22:50:55
急かしてすみません

rian 2024-06-28 22:53:27
解説を書いてくださる方は，
• [link] に名前を書く
• 解説スライドを作って [link] に置く
でお願いします

この辺で解説スライドを用意し始めます。

模擬国内本番

以前までは予選システムだけ借りて運用は JAG 側でやっていたのですが、今年は JAG では問題セットのデータを連携するところまでを担当し、ジャッジシステムの運用は実行委員会側に任せる形になっていました。

障害が発生しました。かなりアバウトに紹介すると、DB の初期化周りのミスだったようです。

模擬コンテストには選手側の練習機会だけでなく、こういうことが本番で起きないための運営側の予行演習という意義もあります。

コンテスト終了後、各種撤収して予選システムを返却、統計情報や解説のアップロード等をすると作業としては完了です。

つづきはごじつかきます……

編集距離を時間 O(|S| |T| / w)、空間 O(|S| + |T|) で復元までやる

以下の記事のおまけです。

rian.hatenablog.jp

おまけなので前回以上に内容が雑です。

編集距離 (Levenshtein distance) を時間計算量 $\Theta(|S| |T| / w)$、空間計算量 $\Theta(|S| + |T|)$ で復元までします（$w$ はワードサイズ）。

  • 諸注意
    • この記事では「復元なし」「復元あり」とはそれぞれ以下のような問題設定を指します。
      • 復元なし：編集距離を求める
      • 復元あり：編集距離が最小になるような編集操作列を実際に求める
    • 前回以上に理解していないのであくまで紹介記事と捉えていただけると嬉しいです。

時間 $\Theta(|S| |T| / w)$、空間 $\Theta(|S| + |T|)$、復元なし

ジャッジ

参考文献

triple-four.hatenablog.com

概要

上の参考文献をガン見します。

一部間違ってるところがある（Cp = Rn | ~(Rp & D0) とあるが正しくは Cp = Rn | ~(Rp | D0) のはず）ので気合いで直し、さらにこのあと Hirschberg's algorithm で復元することを考えて $\mathrm{Cp}, \mathrm{Cn}$ ではなく $\mathrm{Rp}, \mathrm{Rn}$ から編集距離を算出しておきます。

さらに、以下では式変形をすることで各ビット列の長さを $|S| + 1$ ではなく $|S|$ にしています。

コード

inline int idx(char c) {
  if (c <= '9') return c - '0';
  else if (c <= 'Z') return c - 'A' + 10;
  else return c - 'a' + 36;
}

int levenshtein(const string& s, const string& t) {
  int n = s.size();
  int w = (n + 63) >> 6;
  vector<vector<uint64_t>> m(62, vector<uint64_t>(w));
  for (int i = 0; i < n; ++i) {
    m[idx(s[i])][i >> 6] |= 1ULL << (i & 63);
  }
  vector<uint64_t> rp(w, uint64_t(-1)), rn(w);
  for (auto& c : t) {
    const auto& mc = m[idx(c)];
    for (int i = 0, carry = 0, cpc = 1, cnc = 0; i < w; ++i) {
      int nx = (mc[i] & rp[i]) > ~rp[i] || ((mc[i] & rp[i]) == ~rp[i] && carry);
      uint64_t d0 = (((mc[i] & rp[i]) + rp[i] + carry) ^ rp[i]) | mc[i] | rn[i];
      uint64_t cn = rp[i] & d0;
      uint64_t cp = rn[i] | ~(rp[i] | d0);
      rn[i] = (cp << 1 | cpc) & d0;
      rp[i] = cn << 1 | cnc | ~(cp << 1 | cpc | d0);
      carry = nx;
      cpc = cp >> 63;
      cnc = cn >> 63;
    }
  }
  int d = t.size();
  for (int i = 0; i < n; ++i) {
    d += (rp[i >> 6] >> (i & 63)) & 1;
    d -= (rn[i >> 6] >> (i & 63)) & 1;
  }
  return d;
}

時間 $\Theta(|S| |T| / w)$、空間 $\Theta(|S| + |T|)$、復元あり

ジャッジ

概要

bitset + Hirschberg's algorithm でできます。

韓国でもメジャーではないらしく、投稿時点ではこの計算量の提出はありませんでした（https://www.acmicpc.net/problem/status/17161 のスクリーンショット）。

コード

inline int idx(char c) {
  if (c <= '9') return c - '0';
  else if (c <= 'Z') return c - 'A' + 10;
  else return c - 'a' + 36;
}

pair<vector<uint64_t>, vector<uint64_t>> _levenshtein(const string& s, const string& t) {
  int n = s.size();
  int w = (n + 63) >> 6;
  vector<vector<uint64_t>> m(62, vector<uint64_t>(w));
  for (int i = 0; i < n; ++i) {
    m[idx(s[i])][i >> 6] |= 1ULL << (i & 63);
  }
  vector<uint64_t> rp(w, uint64_t(-1)), rn(w);
  for (auto& c : t) {
    const auto& mc = m[idx(c)];
    for (int i = 0, carry = 0, cpc = 1, cnc = 0; i < w; ++i) {
      int nx = (mc[i] & rp[i]) > ~rp[i] || ((mc[i] & rp[i]) == ~rp[i] && carry);
      uint64_t d0 = (((mc[i] & rp[i]) + rp[i] + carry) ^ rp[i]) | mc[i] | rn[i];
      uint64_t cn = rp[i] & d0;
      uint64_t cp = rn[i] | ~(rp[i] | d0);
      rn[i] = (cp << 1 | cpc) & d0;
      rp[i] = cn << 1 | cnc | ~(cp << 1 | cpc | d0);
      carry = nx;
      cpc = cp >> 63;
      cnc = cn >> 63;
    }
  }
  return { rp, rn };
}


void levenshtein(string s, string t, vector<pair<char, char>>& result) {
  if (s.size() <= 1 || t.size() <= 1) {
    int si = 0, tj = 0;
    for (int i = 0; i < (int)s.size(); ++i) {
      for (int j = 0; j < (int)t.size(); ++j) {
        if (s[i] == t[j]) {
          si = i;
          tj = j;
        }
      }
    }
    {
      int i = 0, j = 0;
      while (i < (int)s.size() || j < (int)t.size()) {
        if (j < tj || i >= (int)s.size()) {
          result.emplace_back('a', t[j]);
          ++j;
        }
        else if (i < si || j >= (int)t.size()) {
          result.emplace_back('d', s[i]);
          ++i;
        }
        else {
          assert(i == si && j == tj);
          if (s[i] == t[j]) {
            result.emplace_back('c', t[j]);
          }
          else {
            result.emplace_back('m', t[j]);
          }
          ++i;
          ++j;
        }
      }
    }
    return;
  }
  int n = s.size();
  int l1 = t.size() / 2;
  int l2 = (int)t.size() - l1;
  auto lef = _levenshtein(s, t.substr(0, l1));
  reverse(s.begin(), s.end());
  reverse(t.begin(), t.end());
  auto rig = _levenshtein(s, t.substr(0, l2));
  reverse(s.begin(), s.end());
  reverse(t.begin(), t.end());
  int val = 0;
  int min_val = val;
  int min_idx = 0;
  for (int i = 0; i < n; ++i) {
    val += (lef.first[i >> 6] >> (i & 63)) & 1;
    val -= (lef.second[i >> 6] >> (i & 63)) & 1;
    val -= (rig.first[(n - i - 1) >> 6] >> ((n - i - 1) & 63)) & 1;
    val += (rig.second[(n - i - 1) >> 6] >> ((n - i - 1) & 63)) & 1;
    if (min_val > val) {
      min_val = val;
      min_idx = i + 1;
    }
  }
  levenshtein(s.substr(0, min_idx), t.substr(0, l1), result);
  levenshtein(s.substr(min_idx), t.substr(l1), result);
}

あとがき

むずすぎる

LCS を時間 O(|S| |T| / w)、空間 O(|S| + |T|) で復元までやる

最長共通部分列 (Longest Common Subsequence; LCS) を時間計算量 $\Theta(|S| |T| / w)$、空間計算量 $\Theta(|S| + |T|)$ で復元までします（$w$ はワードサイズ）。

韓国語の記事はいくつか見つかるんですが日本語の記事は見つからないので韓国高度典型なのかも（なまじ音が近いせいか韓国語 → 日本語の機械翻訳精度が低いことが多くしんどい……）。

  • 諸注意
    • この記事では「復元なし」「復元あり」とはそれぞれ以下のような問題設定を指します。
    • 説明のためよく知られるアルゴリズムから順に触れていくので、適宜必要なところだけを読んでください。
    • 完全に理解しているわけではないので厳密な証明などは求めないでください。あくまで紹介記事と捉えていただけると嬉しいです。
    • 間違い（誤字等含む）を見つけたら気軽に教えてください。読まれていることが実感できて嬉しいまである。

時間 $\Theta(|S| |T|)$、空間 $\Theta(|S| |T|)$、復元なし

ジャッジ

概要

詳しく知りたい方は以下の記事などを参考にしてください。

コード

int lcs(const string &s, const string &t) {
  int n = s.size(), m = t.size();
  vector<vector<int>> dp(n + 1, vector<int>(m + 1));
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      dp[i + 1][j + 1] = max({ dp[i + 1][j + 1], dp[i + 1][j], dp[i][j + 1] });
      if (s[i] == t[j]) {
        dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1);
      }
    }
  }
  return dp[n][m];
}

時間 $\Theta(|S| |T|)$、空間 $\Theta(|S| |T|)$、復元あり

ジャッジ

概要

復元なしの方で作ったテーブルを逆順に辿るか、テーブル作成時にどこから遷移したかをメモすることなどで求まります。

コード

string lcs(const string &s, const string &t) {
  int n = s.size(), m = t.size();
  vector<vector<int>> dp(n + 1, vector<int>(m + 1));
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      dp[i + 1][j + 1] = max({ dp[i + 1][j + 1], dp[i + 1][j], dp[i][j + 1] });
      if (s[i] == t[j]) {
        dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1);
      }
    }
  }
  string res = "";
  int i = n, j = m;
  while (i > 0 && j > 0) {
    if (s[i - 1] == t[j - 1]) {
      res += s[i - 1];
      --i;
      --j;
    }
    else if (dp[i][j] == dp[i - 1][j]) {
      --i;
    }
    else {
      --j;
    }
  }
  reverse(res.begin(), res.end());
  return res;
}

時間 $\Theta(|S| |T|)$、空間 $\Theta(|S| + |T|)$、復元なし

ジャッジ

  • なし
    • 時間 $\Theta(|S| |T|)$、復元なしで空間 $\Theta(|S| + |T|)$ と $\Theta(|S| |T|)$ を区別する問題は見つかりませんでした。あれば教えてください。

概要

テーブルを作成するときに一行前の結果しか使っていないので全部持つ必要はありません。
後々の都合上、s に対するループと t に対するループの順番を逆にしています。

コード

int lcs(const string &s, const string &t) {
  int n = s.size(), m = t.size();
  vector<int> dp(n + 1);
  for (int i = 0; i < m; ++i) {
    vector<int> nx = dp;
    for (int j = 0; j < n; ++j) {
      nx[j + 1] = max(nx[j + 1], nx[j]);
      if (t[i] == s[j]) {
        nx[j + 1] = max(nx[j + 1], dp[j] + 1);
      }
    }
    dp = nx;
  }
  return dp[n];
}

時間 $\Theta(|S| |T|)$、空間 $\Theta(|S| + |T|)$、復元あり

ジャッジ

概要

Hirschberg's algorithm というものが存在します。
以下がかなりわかりやすいです。

お気持ちとしては分割統治で、$T$ を $T_1, T_2$ と前後半分に切り、$\mathrm{dp_1}[i] := S[:i]$ と $T_1$ の LCS の長さ、$\mathrm{dp_2}[i] := \mathrm{rev}(S)[:i]$ と $\mathrm{rev}(T_2)$ の LCS の長さ、という 2 つを求めることで通過すべき位置が求まり、サイズが半分の問題に帰着できます。

コード

vector<int> _lcs(const string &s, const string &t) {
  int n = s.size(), m = t.size();
  vector<int> dp(n + 1);
  for (int i = 0; i < m; ++i) {
    vector<int> nx = dp;
    for (int j = 0; j < n; ++j) {
      nx[j + 1] = max(nx[j + 1], nx[j]);
      if (t[i] == s[j]) {
        nx[j + 1] = max(nx[j + 1], dp[j] + 1);
      }
    }
    dp = nx;
  }
  return dp;
}

void lcs(string s, string t, string &result) {
  if (s.size() <= 1 || t.size() <= 1) {
    for (auto &i : s) {
      for (auto &j : t) {
        if (i == j) {
          result += i;
          return;
        }
      }
    }
    return;
  }
  int n = s.size();
  int l1 = t.size() / 2;
  int l2 = (int)t.size() - l1;
  auto lef = _lcs(s, t.substr(0, l1));
  reverse(s.begin(), s.end());
  reverse(t.begin(), t.end());
  auto rig = _lcs(s, t.substr(0, l2));
  reverse(s.begin(), s.end());
  reverse(t.begin(), t.end());
  int max_val = -1, max_idx = -1;
  for (int i = 0; i < n + 1; ++i) {
    if (max_val < lef[i] + rig[n - i]) {
      max_val = lef[i] + rig[n - i];
      max_idx = i;
    }
  }
  if (max_val <= 0) {
    return;
  }
  lcs(s.substr(0, max_idx), t.substr(0, l1), result);
  lcs(s.substr(max_idx), t.substr(l1), result);
}

時間 $\Theta(|S| |T| / w)$、空間 $\Theta(|S| + |T|)$、復元なし

ジャッジ

参考文献

概要

$\mathrm{dp}(S, T)[i] := S[:i]$ と $T$ の LCS の長さ、というテーブルを高速に求めたいです。
ここで、$\mathrm{dp}$ の階差を考えると、$\mathrm{dp}[i] \le \mathrm{dp}[i+1] \le \mathrm{dp}[i] + 1$ であることからこれは各要素が $0$ または $1$ の数列になっています。
階差から $\mathrm{dp}$ の復元は容易なので、階差がビット演算で効率的に求まれば良いです。
より具体的には、$B[j] := \mathrm{dp}(S, T[:j])$ の階差数列、としたとき、$B[j+1]$ が $B[j]$ から効率的に求まれば良いです。

……自分が自信を持って解説できるのはここまでで（短すぎる）、

結論だけ言うと、これは以下のように更新できます。

B[j+1] = (B[j] | m) ^ ((B[j] | m) & ((B[j] | m) - (B[j] << 1 | 1)))
（m は S[i] == T[j] を満たす i にビットが立ったビット列）

お気持ちをなんとなくは理解しているんですが説明できるほどではないです。 誰か完全理解したら正しいお気持ちを教えてください。 （上の参考文献にはもう少しまともな説明が書かれています）

ビット列同士の減算を行う必要があるので通常の bitset ではできず自作する必要はありますが、これで効率的に更新することができます。

……というのが韓国で知られている典型っぽいんですが、上のビット演算は少し式変形できて、（自分の実装だと）さらに少しだけ速くなります。

B[j+1] = (B[j] | m) ^ ((B[j] | m) & ((B[j] | m) - (B[j] << 1 | 1)))
       = (B[j] | m) ^ ((B[j] | m) & ((B[j] | m) - (B[j] << 1) - 1))
       = (B[j] | m) ^ ((B[j] | m) & ~((B[j] << 1) - (B[j] | m)))
       = (B[j] | m) ^ ((B[j] | m) & ~(B[j] + B[j] - (B[j] | m)))
       = (B[j] | m) ^ ((B[j] | m) & ~(B[j] - (m & ~B[j])))
       = (B[j] | m) ^ ((B[j] | m) & ((B[j] | m) ^ (B[j] - (m & ~B[j]))))
       = (B[j] | m) & ((B[j] | m) ^ (B[j] | m) ^ (B[j] - (m & ~B[j])))
       = (B[j] | m) & (B[j] - (m & ~B[j]))

コード

int lcs(const string &s, const string &t) {
  int n = s.size();
  int w = (n + 63) >> 6;
  vector<vector<uint64_t>> m(26, vector<uint64_t>(w));
  for (int i = 0; i < n; ++i) {
    m[s[i] - 'A'][i >> 6] |= 1ULL << (i & 63);
  }
  vector<uint64_t> b(w);
  for (auto &c : t) {
    const auto &mc = m[c - 'A'];
    // b = (b - (mc & ~b)) & (mc | b)
    for (int i = 0, borrow = 0; i < w; ++i) {
      uint64_t x = mc[i] & ~b[i];
      int nx = b[i] < x || (b[i] == x && borrow);
      b[i] = (b[i] - x - borrow) & (mc[i] | b[i]);
      borrow = nx;
    }
  }
  int res = 0;
  for (auto &i : b) {
    res += __builtin_popcountll(i);
  }
  return res;
}

時間 $\Theta(|S| |T| / w)$、空間 $\Theta(|S| + |T|)$、復元あり

ジャッジ

概要

bitset + Hirschberg's algorithm でできます。

コード

vector<uint64_t> _lcs(const string &s, const string &t) {
  int n = s.size();
  int w = (n + 63) >> 6;
  vector<vector<uint64_t>> m(26, vector<uint64_t>(w));
  for (int i = 0; i < n; ++i) {
    m[s[i] - 'A'][i >> 6] |= 1ULL << (i & 63);
  }
  vector<uint64_t> b(w);
  for (auto &c : t) {
    const auto &mc = m[c - 'A'];
    // b = (b - (mc & ~b)) & (mc | b)
    for (int i = 0, borrow = 0; i < w; ++i) {
      uint64_t x = mc[i] & ~b[i];
      int nx = b[i] < x || (b[i] == x && borrow);
      b[i] = (b[i] - x - borrow) & (mc[i] | b[i]);
      borrow = nx;
    }
  }
  return b;
}

void lcs(string s, string t, string &result) {
  if (s.size() <= 1 || t.size() <= 1) {
    for (auto &i : s) {
      for (auto &j : t) {
        if (i == j) {
          result += i;
          return;
        }
      }
    }
    return;
  }
  int n = s.size();
  int l1 = t.size() / 2;
  int l2 = (int)t.size() - l1;
  auto lef = _lcs(s, t.substr(0, l1));
  reverse(s.begin(), s.end());
  reverse(t.begin(), t.end());
  auto rig = _lcs(s, t.substr(0, l2));
  reverse(s.begin(), s.end());
  reverse(t.begin(), t.end());
  int lc = 0, rc = 0;
  for (auto &i : rig) {
    rc += __builtin_popcountll(i);
  }
  int max_val = lc + rc;
  int max_idx = 0;
  for (int i = 0; i < n; ++i) {
    lc += (lef[i >> 6] >> (i & 63)) & 1;
    rc -= (rig[(n - i - 1) >> 6] >> ((n - i - 1) & 63)) & 1;
    if (max_val < lc + rc) {
      max_val = lc + rc;
      max_idx = i + 1;
    }
  }
  if (max_val == 0) {
    return;
  }
  lcs(s.substr(0, max_idx), t.substr(0, l1), result);
  lcs(s.substr(max_idx), t.substr(l1), result);
}

あとがき

LCS とかいうド典型問題なのに全然知らなかった。

ネタバレにもなるのでここでは挙げてないですが、賢くやって $\Theta(|S| |T|)$ が想定解な問題を $\Theta(|S|^2 |T| / w)$ とかでわりと余裕もって殴れたりしてすごいです（$|S|, |T| \le 3000$ くらいまでは行けることがある雰囲気）。

最近は solved.ac を埋めるのにハマっています。よければぜひ。

ICPC模擬地区予選 2022　準備記

ICPC

ICPC模擬地区予選 2022 参加者の皆さま、お疲れ様でした。ご参加いただきありがとうございました。

以下、各問題に対する貢献（あれば）と個人的な感想などです。

以下、問題のネタバレを含みます

A: Stop & Go

準備されたものを見たら赤になった瞬間に信号に突っ込むケースがなかったので追加しました。
ついでに青になった瞬間に信号に突っ込むケースも追加しました。こっちはいらないかも。

B: 1-Player Concentration

ほとんど何も関わってないです。
難読なのかなと思っていましたがわりとサクサク通されていたのでよかったです。

D: 2-LIS

原案時には {O(N^3)} だったのを {O(N^2)} に落としました。
あとは少しだけテストケース生成をしました。
解説には違う DP が書かれていましたが、自分の解法は

dp[x][y] := (b_{k-2} < x) and (b_{k-1} = y) を満たすような k の最大値

というちょっと変な DP テーブルがうまく更新できることを使っています。これちょっと面白くない？
AtCoder で言うとこの問題が少し近いかもしれません：https://atcoder.jp/contests/abc176/tasks/abc176_f

H: Sloppy city planning

ほとんど何も関わってないです。2
けっこう難しいんじゃないかと思ってましたがかなり通されていました。まぁこのセットの中だとこの位置になるのはそれはそう。
入力サイズが大きすぎて domjudge にアップロードしようとすると 500 が返ってきて困っていたんですが、システム担当者の方がなんとかしてくださいました。本当にありがとうございます。

C: Track Train Trail

データセットを担当しました。
ただ、急遽入った形だったので自分は解いていません。

内部コンテストでの一幕
区間が交わらないマッチングが区間 DP になるのは典型 90 問にもあったはずなのでわりと一直線かなと思ってたんですが、そもそも中国人郵便配達問題の考え方が「次数が奇数の頂点の最小重み完全マッチングを考える」なのを知っているかどうかがかなり大きかったかもしれません。

I: N-1 Truths and a Lie

ほとんど何もしていないですが、一応 {\bmod 2^{32}} で見ると（32 bit 整数型を使っていると）嘘つきが一人もいなくて困る、というケースだけ追加しました。引っかかった人いるんでしょうか。
あとは制約を満たす（嘘つきがちょうど 1 人いる）入力のランダムな生成方法を提案したりしました。
これは、K 頂点 N-1 辺の矛盾ないグラフ（これは各頂点に適当な値を割り振ればできる）に 1 本間違った辺を足すとき、2 頂点の間に直接の辺がないかつ辺素パスが 2 つ以上あること（＝連結かつ間に橋がないこと）が辺を足せる必要十分になるので、二重辺連結成分分解をしたあと成分内で繋げばよいです。
前日の 27 時までテストケースに橋のあるケースが入っておらず、慌てて追加したりしました。翌日の起床時間 8 時。
実は原案時にはこの問題設定の前にもう一つステップがあったんですが、本番 5 日ほど前に改題されて今の問題になったりしています。

L: Tree Automorphism

データセットを担当しました。
木のハッシュについては前回の模擬地区でも出題されていたのでボーナス枠かなと思っていたのですが、思ったより解かれませんでした。
でも確かに子に同じ部分木があったときに具体的に何倍になるのかパッとはよくわからない気もするので難しいかも。
もし根つき木のハッシュはわかるけど根なし木のハッシュはわからない、という方がいたらあとで調べていただけると……。

F: Seimei Handan 999.0

ほとんど何も関わってないです。3
そんな状態で言うことではないですが、もっと解かれると思っていました。
実際に何の文字であるかはかなりどうでもよくて、どの文字とどの文字が同じかという情報だけ欲しいので、「何文字前と同じか」という情報にしてしまいたいのはかなり自然で、そういう情報が一致することと元のパターンが一致することが同値なのもわりと自然なので、あとはウィンドウをずらしながらロリハを更新していけば良い、とかなり一直線だと思っていました（考察だけして実装してないですが……）。

E: Sharp 2-SAT

ほとんど何も関わってないです。4
本当に考察もしていないので何もわからないですが、とりあえず TLE 解を出す、というチームがもっと出てくると思っていました（まぁ FFT の写経が必要になるのでその方針が正しいかは微妙ですが……）。

K: Sort Compressed Strings

データセットを担当しました。
原案時点ではまぁそこまで難しくないでしょ、というような雰囲気だったんですが、実際に実装してみたらかなり面倒でびっくりしました。
その上で、うまく実装すると log が落ちたりかなり高速になったりするのでそれに合わせた制約、実行時間制限にしたら大変なことに……。
これでも展開後の文字列長の最大値が {10^{18}} から {10^{10}} に変更になっていたり（これは実行時間の問題ではなくハッシュの衝突確率が十分に低い証明ができないことが原因ではありますが）、本番 2 日前に TL を 2 sec から 4 sec に変更していたんですがまだ足りなかったようです。
適当なメモ化で現実的にかなり高速になるのでそういうことをした結果通る、というチームが多いだろうという予想をしていたのですが、コンテスタントから見るとどれくらい惜しい TLE なのかはわからないので難しいですね……。
コンテスト中に、1 ケースだけ 4.2 sec かかって TLE、という惜しいチームがありました。
結果的に 0 AC になってしまったのは調整ミスだと思うのでかなり悔しさがあります。

J: Most distant point from the stations

最初は {N \le 100} くらいで準備されていたと思うのですが、いつの間にか {O(N^2 \log N)} の解法が実装されて {N \le 2{,}000} になっており、泣きながら自分も {O(N^2 \log N)} を実装しました。complex<double>.arg() でソートしたら遅かったので泣きながら整数で比較したりもしました。
どうやらまともなボロノイ図のライブラリを持ち込んでいたチームはいなかったようで、0 AC でした。これ {N \le 100} でもよかったんじゃない？ だめ？

G: Avoid bombings

原案、データセットを担当しました。
問題案がなかなか集まらず、ボス問もない（これはいくつかの問題に対する難易度の過小評価もあった）という状態で、問題選定会議の司会をしながら無理矢理捻り出した問題でした。
一週間くらいかけて泣きながら想定解を実装したはいいが他に誰も実装してくれなかったのでこれは出せなさそうかな……、と思っていたのですが、climpet さんが実装してくださり出せる形になりました。
結局提出数 0 だったので我々の努力が報われることはありませんでした。
ちなみに解説スライドにあたかも元ネタかのように置かれている画像は実は元ネタではなく、原案を出したあとにそういえばこんなミニゲームあったな……、となっただけでした。

その他

前回の模擬地区予選（模擬地区予選 2021）から、自分がコンテスト運営責任者を not さんから引き継いでいました（JAG のページ更新してない気がする……）。自分がまとめ役をするようになってからこれで 3 回目のコンテストでした。まだ not さんなどベテランの方々に頼っている部分もかなり大きいですが。
主な仕事としては、コンテストを企画したり、会議を開いたり、スケジュールを管理したり、セット全体の品質を管理したりなどです。その上で他の人と同じように各問題の担当者に入ったりもしています（手を加えた方が良さそうな部分のヘルプに入るのを中心にしたいため、可能な限り入らないようにしてはいますが）。模擬地区特有のことを言うと、icpcsec に連絡してジャッジを貸してもらったり、貸してもらったジャッジにデータをアップロードする、あたりもしていました。そういえば参加者への連絡も（アカウント通達以外は）自分がやっていましたが、それくらいは他の人にお願いすべきだった気もします。
また、今回は久々のオンサイト開催ということもあり、その辺の調整も自分がやっていました。調整、と言っても会場やスポンサーとちょっと連絡取るだけだろ、と思えるんですが、実際には今回はここに書けないような大変なことがたくさん起こり、心が 5 回くらい折れました。
特にオンサイト周りなどで慣れないところが多かったり JAG の人々の時間的余裕ややる気の度合いがわからなかったりで、他の人に責任やタスクを分散できなかったのがかなりよくなくて、特に問題セットのバランスや品質に影響したような気もしていてそこが反省点ですね……。
特に実装量がちょっと多いとかハッシュを取る問題がちょっと多いとかは準備時に気づいていたので何らかのアクションは取られるべきだったかもしれません。
あとどうでも良い寄りのところだと、思ったよりおにぎりの消費が早かったのでおにぎりとサンドイッチが同じくらいの量でもよかったなとなりました。あとお茶多めにする必要もなかったかも。みんな学生なのでジュース飲むっぽい。

おわりに

改めて、模擬地区予選にご参加いただき本当にありがとうございました。
JAG の問題セットは、数少ないまともな問題案の中からなんとか絞り出しているような感じで、バランス等も安定しているとは到底言えない状況です。そもそも問題案が枯渇しかけていて、来年以降問題セットを作れるかどうかすらわかりません。ICPC 引退した人が JAG に加入して問題をドシドシ提案してくれると、とても助かります。ご検討のほど、よろしくお願いいたします。（コピペ）*1

jag-icpc.org

また、JAG のコンテスト運営責任者に興味のある方も募集しています。一応まだ投げ出す気はないですが、興味のある方がいたらお手伝いいただく（もしくは自分がお手伝いする）のもいいかなと思っています。

最近は特に、作問能力の高い人、モチベーションの高い人が他のコンテストサイトなどに吸われてしまっていてどうしても JAG の作問能力が落ちていてこまっています。まぁうちが完全無償のボランティアなのに対しちゃんと正当な対価が支払われるような場所もあるのでしかたないね。

*1:https://climpet.hatenablog.com/entry/2022/11/27/230943#%E3%81%8A%E3%82%8F%E3%82%8A%E3%81%AB

もぎちく2021非公式コメンタリ

ICPC

（この記事に書かれた内容は全て個人の見解であり、所属する組織の公式見解ではありません）

問題文、順位、解説等は以下のページで公開されています。 jag-icpc.org

注意：以下には問題のネタバレが含まれます

自分の想定していた難易度順に問題を見ていきます

A: Harvest（AC チーム数：35）

データセットを担当していました。最も簡単な問題ということもあり境界値データとか用意するの忘れていたんですが、ちゃんと WA や TLE が出ていて（かつ全チーム AC していて）良かったです。

B: Parse the Syntax Tree（AC チーム数：34）

びっくり簡単枠です。最近の ICPC 横浜では A とか B とかに見た目やばいけど実は簡単な問題が出る印象があった（個人の見解です）ので B に置きました。
問題文中に書いてある構文に沿って再帰関数で計算してもいいですが、実は . を全て無視して左下から Queue とかを使って適当に計算してもできます（詳しくは解説 pdf を）。

H: include（AC チーム数：34）

SCC 貼るだけ枠です。意図的に（？）入次数 0 の頂点のみを選択してもサンプルが合うようにしていたらしく、そんな感じの提出が何件か来ていた気がします。

G: Pizza delivery（AC チーム数：29）

隣接した 2 つを swap した方が嬉しい条件を見つけるいつものです。データセットを担当していました。もしかしたら {t_i, a_i \le 1{,}000} という制約に戸惑わされた人がいるかもしれないですが、答えを 64bit 整数に収めるための処置でした。データセット作成係としては何も考えずにランダムに作ってもいい感じの入力が作れて嬉しい。

I: (N+1)-legged race（AC チーム数：32）

すでに AC 数と想定難易度順に逆転が起きていますね…。当初 DP 解が発見されておらず、そこそこの考察をしたのち set を使う解法が想定だったんですが、実はもっと単純な DP 解が存在していました。本番で解いたチームもほとんどが DP だったのではないでしょうか。

K: Zombie Land 2（AC チーム数：20）

ん……？ ちょっと幾何の要素が入った普通枠のつもりでした。ある二人が距離 D 以下になる区間さえ求まれば、あとは {O(V^2)} ダイクストラみたいな要領で各人がいつゾンビになるかわかります。誤差の評価にそこまで自信がないので、もし誤差のみが原因で落ちている人がいたらかなり申し訳ないです。
ところで問題文を担当していました。読み比べればわかるんですが、ほぼ過去の JAG 夏合宿の問題 Zombie Land の丸パクリです。まぁ解法全然違うしセーフということで…。 onlinejudge.u-aizu.ac.jp

あと、コンテスト中に既出？が発覚しました。 onlinejudge.u-aizu.ac.jp

C: Permutation Magic（AC チーム数：24）

最小費用流を流す問題でした。おそらく辞書順最小を求めるところが問題になる気はしますが、そこで {O(M^2)} 回最小費用流を流すのが通ってしまったようです。まぁおそらく遅いフローの {O(M^4 \log M)} と速いフローの {O(M^5 \log M)} を区別するのは困難なため……。

J: Isomorphic?（AC チーム数：25）

データセットを担当していました。輪っかにくっついてる木の hash を求めて、そうしてできた 2 つの hash 列が反転、rotate によって一致するか調べる問題でした。前半部分は「根付き木　ハッシュ」とか調べるといくらでも出てきて、後半部分は Z-Algorithm や Rolling-Hash でできます。
YesNo だと簡単に嘘解法が通りそうだったので実は対応関係を復元する問題にするつもりだったのですが、自分の対応が遅れてしまい結局 YesNo のまま出しました。終わってみれば復元を要求しなくて正解だったかもしれません。
代わりにテストケース生成はちょっと頑張って、最低限適当すぎるコードは通らないようにしたつもりです。本番でも結構な提出を落とせていて良かった（ただ一つ問題があって、問題の性質上木のハッシュが衝突しまくり、みたいな嘘は基本的に落とせない）。

D: MFP: Most Fluctuated Player（AC チーム数：22）

最初に出うる得点を座圧しておいて、自分以外のせいで起こった変動を上手く遅延するといい感じになるやつです（最初に出うる得点を座圧しておいて、自分以外のせいで起こった変動を上手く遅延するといい感じになるやつとは？）。

F: qarentheziz zepuence（AC チーム数：4）

原案と問題文を担当しました。どうやらセグ木とか平方分割に変なものを乗せるのが人よりちょっと得意らしい。
当初想定解が {O(N \log N + Q \sqrt N \log N)} で {N, Q \le 10^5} だったのですが、{\Theta(NQ)} を確実に落とすのが難しく、かつ {O(N + Q \sqrt N)} になったので少し制約が大きくなりました（すまん！）。それでも 3 並列だし 10 チームくらい通すと思っていたので、ちょっと意外ではありました。

準備をしながら、この辺の問題に似てるな思いを馳せていました。 atcoder.jp onlinejudge.u-aizu.ac.jp

自分のジャッジ解を置いておきます（もしどこかバグっていても責任を負いません） jag_regional_2021_F_riantkb.cpp · GitHub

E: Underground's SUNDAY（AC チーム数：4）

問題文を担当しました。原案では日食みたいな問題設定だったんですが、空に浮いたあの多角形はなんだ……？ となって今回の問題文になりました。ちょっとだけ Undertale をイメージしています。
ところで、原案では凸多角形だったり円の中心が通る直線と平行な辺が存在しなかったりしました。どうしてこんなことに。準備段階でも y 軸に平行な辺とかではちゃめちゃバグらせたので、5 時間の間で冷静にデバッグができるかゲーかなと思っています。

自分のジャッジ解を置いておきます（もしどこかバグっていても責任を負いません） jag_regional_2021_E_riantkb.cpp · GitHub

ところで

JAG ではメンバーを募集しています。 やる気がある人やボス問を作れる人や問題準備を手伝ってくれる人やテスターをしてくれる人ややる気以外何もない人などの加入を心よりお待ちしています。 jag-icpc.org



以上の内容はhttps://rian.hatenablog.jp/より取得しました。
このページはhttp://font.textar.tv/のウェブフォントを使用してます
不具合報告/要望等はこちらへお願いします。
モバイルやる夫Viewer Ver0.14