Codeforces エイプリルフール 2023 解法 - でも今日はSRMあるから

Codeforces April Fools Day Contest 2023 の感想
CF のエイプリルフールコンテストの特徴は

タイトルやサンプル入出力がヒント
プログラミングコンテストのローカルネタ
ミステリーランゲージ（マイナー言語、エソラング）

理不尽に難しいが解けなくもない問題が多い。

A : Are You a Robot?

題：あなたはロボットですか？
答：画像の文字を出力する。YES も NO も間違い

B : Was it Rated?

題：n は rated ですか？
入力：1 ≦ n ≦ 25
答：Codeforces のコンテストのURL通し番号 1 ~ 25 をratedかどうか確認する。15, 20, 21 が unrated。
昨年はAtCoderのコンテスト名前の問題が出題されたのでコンテストの番号は予想できるが、25 がヒントでも何でもないので難しい。

C : Digits

入力：1行目はテストケース数 t。各テストケースは n 個の整数。ただし n は与えられない

input	output
3 2 1 4 7 1 2 3 5	8 7 30

答：サンプル入出力を見ると入力の積になっていると気が付くことができる。要素を3個、1個、4個に分割するとうまくいくので円周率の数字毎に区切ればよいと予想できる

D : Trivial Conjecture

問：コラッツの関数 f(n) が書かれている。この関数に k 回繰り返し適用しても1が現れないような整数 n を求めよ。つまり、k項について n, f(n), f(f(n)), ... ≠ 1 となる整数 n を求めよ。
ただし k の上限は秘密
答：現在見つかっているコラッツ関数のチェーンの長さよりはるかに大きな k が来るとどうしようもない。
問題をよく読むと "整数" n を求めるというので、0以下の数を出力するだけ。

E : Not a Geometry Problem

入力：数 x, y, z が与えられる
出力：実数を出力せよ。ただし、相対誤差・もしくは絶対誤差は $10^6$ 以下でなければならない。つまり参加者のプログラムの出力を $a$ 、審判の出力を $b$ としたとき、 $\frac{|a-b|}{\max(1, |b|)} \le 10^6$
答：普通の問題は誤差 $10^{-6}$ で求めるが、本題は $10^6$ である。 a = 0 のとき、誤差は必ず 1 以下なので 0 を出力すればよい。

F : Factorization

問：入力の n の最大の素因数を求めよ。
入力は2通りあり、問題文で書かれているので実質 output only

入力1 n = 4167792762229302596005813
入力2 n = 502326648535222453054166634657971818804572580255694785590270206376893052666523759828749572821869200397402455443130219791674914146276480544216264509037323019703862145022909043607926185591029614599889902115472391135622402044979347133959392884686037208893694733655782993294168167973855585231709683012084723677082273198866111120369101303677409522966567521782715484001992772768993119841291702786496058775824381444079748162416745495656333618343487208147794874337933873576016717726298883519261055062303842274145012056670644839715140659887936321934474824687778512706909988484451300384818197143498259061041

答：どちらも2つの素数の積である。一般にこんなに大きな素因数分解ができるはずもない。
入力1は素因数分解できるサイズである。

$ factor 4167792762229302596005813
4167792762229302596005813: 991999999999 4201403994187

ここで小さいほうの素数 991999999999 が見た目が特徴的な数であり、入力2も同じ傾向があると予想できる（できない）。
1 が一つと 9 だけでできる素数で試割りすると解ける。
2種の数字で、一方が1回だけ使われる素数を glitch prime と呼ぶらしい（glitch = 1文字だけエラーで置き換わったという意味？）。

G : Colour Vision

問題文はなく、画像だけ

答：単色になったサイトロゴ。カラーコードを16進数で取ると #01722B。1000番台の数を見ると CF のURLと予想できる。しかもコンテスト通し番号 1722 の問Bはcolorに関する問題で、その問題の解をそのまま提出すればよい。

ブラウザ上でカラーコードを取ると必ずしも同じ値にならないのでダウンロードしてから取得する必要がある。

H : Expected Twist

問：インタラクティブ問題。
オラクルは長さ $n$ の数列 $a_1 ... a_n$ を隠し持っている。参加者は次の質問をすることができる：

区間 $l, r$ の最大値は何か

オラクルは $\max( a_l, ..., a_r )$ を返答する。
624 回以内の質問をして数列の最小値を求めよ。
ただし数列の要素はランダムに生成された $0$ 以上 $2^{32} - 1$ 以下の数。

答：最大値のクエリで最小値を求めるのは無理そう。
題名のTwist、数列は乱数、そして 624 からメルセンヌツイスターを想起できる。メルセンヌツイスターは連続 624 項を見ると内部状態がわかり、次の値が予測できるらしい。よって、最初の 624 項を取得して数列を復元する

I : Mountain Climber

入力：各テストケースは一つの文字列が与えられる。
出力：YES NO で答えよ
入力例：たくさん
答：アルファベットの見た目に関係する問題。
アルファベット（のフォント）は上に大きい文字 Ascender と下に大きい文字 Descender がある。Ascender を開き括弧、Descender と閉じ括弧、それ以外の文字を無視して括弧の対応が取れていれば YES

これを解くのは不可能では？？

J : Unmysterious Language

問：Unmysterious language （謎ではない言語）。ジャッジは参加者の提出をみて、正当かどうか判定する。
答：CFはコンパイルエラーメッセージが見えるので適当に提出してエラーを検索するのが Mysterious Language の定跡。試しに出すと

Checker comment
wrong answer I'm sorry, but I'm not sure what you are asking. If you have any question or need any assistance, feel free to ask and I'll do my best to help you.

そういえば最近 ChatGPT が話題になっている。英語で「 accepted をください」と書けばよい。