TUPC2023 開催記

TUPC2023 を開催しました．

atcoder.jp

準備記録とか運営記録とかは他の運営の子たちが書いてくれてるのでさぼってそちらに譲ります．各問題について感想など．

A - Namboku / Tozai Line

Welcome 枠．

B - 012 Grid

LGV 公式を知らず解説 AC．結構面倒だと思って取り掛かったらシンプルになって感動．ABC 上位勢たちがたくさん通してくると予想してたがハズレ．

C - Topological Sort

Writer．設定がシンプルで考察もちょっとあってそこそこ面白枠だったんじゃないかなと．サンプルで人々をだまそうと思って答えが 2 べきになるケースしか置かなかったらみんなだまされててにこにこしてた．線形で解けるのが地味に推しポイント．

D - Shift Puzzle

Writer．去年 7 月の AGC063 で大敗した後に嫌になって作問してたら思いついた問題．3 点 rotate を利用して 2 点 swap が実現できるのがびっくり． N^3 回っていう制約が想定解だとちょうどぴったりになる．FA の zkou さんが想定で解いてくれたらしくうれしい．非想定解法もいくつかあるみたい．

E - And DNA

自分は実験・実験・OEIS で解いてしまったのでこの問題は面白ポイントがまだわかっていないが，ちゃんと解くと面白ポイントがあるらしく評判は良かったみたい．問題名の DNA が何なのかずっと分かってなかったが解説スライドを見て納得した．

F - Hotel

横から首出してコードを投げたらそれが想定解になってた．題材が無限ホテルだったので，だったら最初から長さ無限にしませんか？と提案したが厳密性が怪しくなると数学のプロたちに言われて却下されちゃった．

G - Min Nim

渡されて 2 分で解けたのでこれは簡単ですね～って言ってたが，他の人はすんなりはいかなかったみたい．

H - Count Pseudo-Palindromes

最初の提案時からわからず解説 AC．最初 O(N \log ^2 N) 解法が想定で，そのときは長さが良い擬回文の列挙に帰着して列挙に O(N \log ^2 N) かけるというものだった．その後まったく方針の違う O(N\sqrt{N}) やら O(N \log N) 解法がたくさんでてきたので改めて元の想定解の列挙パートを考えてみたところ，線形に落とせることに気が付いたのでそれを報告．なんやかんやあって今の形式に落ち着いた．K の満点を除けばこれが最難問だと思っていて，本番は正解者が出るかどうか怪しいと思っていたが実際は 1AC 出ていてすごい．線形で解けるのが地味に推しポイントその 2．

I - Maximize Array

Writer．簡単枠が足りてなかったみたいだったで適当に考えてたら案外よさげなのが生えたので提案．簡単だけどちゃんと考察をしないとペナしやすい問題になってよかった．

J - Colored Complete Graph

もともと N\leq 200 とかで，そのときは乱択で雑に通してしまった．ちゃんと想定解の考察を要求しましょうということで N\leq 50000 に．AtCoder のインタラクティブの問題で質問回数が 10^5 回以上ある問題が見つからなかったので心配だったが特に指摘されることはなかった．

K - (mod HW+1)

この問題が 100 点の部分点も含めて誰にも解かれない問題になってしまった．100 点の部分点はすごい難しいというわけではなく正解者も出るだろうと予想していたのでびっくり．101 点の存在にみんなビビっちゃったのかなあ．準備段階で，もともと W が H=W バージョン（部分点 100 点）の問題を提案していて，それはそこそこ時間はかかったが自力で解けた．お正月の帰省中に H\neq W バージョンをふと考えてみるとなんか解ける気がしたので，W/T に解けるかもしれないと報告．実査にはその後がめちゃくちゃ大変で，ひたすらコーナーケースつぶしをしていた．特に (H,W,R)=(11,13,0) が不可能なことの証明が大変で，この証明にかなりの時間を割くことになった．最終的に自分はプログラムを書いて枝刈り全探索をすることで証明した．

L - Random Mex

制約を無視すればいろんな解法がありそう．実際自分は各テストケースに対して O(M \log N) の解法が最初思いついていたし，他の準備陣からもいろんな解法が出ていた．しばらくして，答えがスターリング数を用いると簡潔な式で表現できることが分かったので，だったらそれを要求するような制約にしませんかと提案．結果的に今の制約になった．一応 OEIS を使えばエスパーすることができることは確認していたし，数え上げ得意な人多いからもうちょっと解かれると予想していた．

M - Vivid Colors

自分が問題を渡されたときは，題材に倣って r,g,b\lt 256 の制約だった．最初の式変形は wolfram alpha に投げるとやってくれて，あとは選ぶベクトルを乱択することで犯罪 AC をした．他のテスターも乱択で通していたので，しぶしぶ制約を強化して乱択を通りにくくするように．想定解は実装も含めてかなり難しいと思う．sotanishy 君の別解はすごい．

N - Do Not Turn Back

サークルの活動の後に問題を教えてもらい少し考えて分からず，すぐに解法を聞いてしまった．典型っぽさはあるが難しいと思う（自力では無理な気がする）．この問題を BMBM で解けちゃうのはびっくりした．

O - 0100 Insertion

判定問題を 5 時間位考えたが分からず解説 AC．必要十分条件がすっきりしていてすごい．その条件が前から見ていかないとダメだったので，じゃあ最初からひっくり返しておきませんかと提案した．結果 1AC になった．

P - Sub Brackets

この問題が参加者の中で一番評判が良かったんじゃないかなと思う．見た目（制約も含めて？）は区間 DP っぽさがあるが想定解はフローで，そのギャップに驚いている人たちがたくさんいた．自分も区間 DP にまんまとハマってしまったし，コンテスト中に実際にハマっていた人もいたようだった ． N の制約は何でもよかったが，区間 DP っぽさを出すために N\leq 500 ということに．

自分がやったこと

  • C：Writer
  • D：Writer
  • H： O(N) 解法の提案
  • I：Writer
  • K： H\neq W バージョンの提案
  • L： O(N^2) 解法を要求することを提案
  • M： r,g,b の制約を強化することを提案
  • O：0010 を 0100 に変更することを提案

その他

TUPC の前の ARC で無事 karinohito 君が入橙していた．これにより toam, sotanishy, karinohito 大学同期 3 人が揃って橙の状態で TUPC を迎えることができた．sotanishy 君が来月からいなくなってしまうので，その前に全員が揃う瞬間ができて本当に良かった．

以上，ご参加ありがとうございました．