JOIでできるかもしれなかった悪いこと Part.1

フィクションです

実際にJOIでして怒られても僕は責任を取りません

あと今はできるとは限りません（年々対策が強化されており...）

好評なら次を書きます

今年の本選を解いていきましょう

A,B,Cは当然解けますね

しかしボーダーは300点では届きません（悲しい）

Ｄを見ると...？

うーん、1点もわかりません

うーん、、

うーん、、、、

制約21でワロタwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww

はい

では解いていきましょう

適当にhashを作って時間に書き出せるか確認するよ～

よさそう

こんな感じの100通りくらいの値を判別するHashを2つ提出すれば大体のケースのHashが一意に定まりそう

これをしながら1～21まで出力するとよさそう

最近のChatGPTって優秀なんですね～（Hashの衝突については確認してないけど...）

実は1~21まで聞く必要はなくて、1~20でいいですね（YesNoだと片方でいいみたいな話）

答えが6になるケースないんですね、おもろ

埋め込みを頑張ると...

は？？？

ChatGPTが途中から嘘ついてて草

直します

うーん、実装が多少悪いのも相まって、Hashを実行時間に書き出すのに20ms以上の誤差が出ていそうです？入出力高速化や25ms単位の出力にして検証しました

何回か試してみたんですがたまに少し遅くなることがありそうで、Hashの特定には少なくとも2回はやったほうがよさそうという気持ちにはなりました。

余談なんですが、少し遅くなるの話なんですが、ちょうど2倍時間かかっているのが2ケース見つかったので、僕のコードのバグかあるいはAtCoderのジャッジのなんかなのかなぁと思っています。

まだWAですねぇ...

よく見るとHashが衝突している（おい）

適当にHashを増やします

草

提出回数は31回でした。だいぶ無駄は多いですがJOIの提出回数制限に収まりますね。

一般に、各入力に対して入力から出力の候補をC個簡単に列挙できるとします。（例えばYesNoであればC = 2）

Hashの時間への書き出しと、入力と正しい出力の対応の確認は同時に行えるので、

max(2log(100, テストケース数), C) + 1回の提出でできそうです。

（2log(100, テストケース数)の部分は2回実行×1回で100通りの情報を送れることを仮定しているので、適当にやればよくも悪くもなりそうです。）

テストケースごとに実行時間が見れるコンテストなんてものはほぼなくなってしまった（JOI...）のでこれは使い道がなさそうです。（かなしい）

一応実行時間が最大値であるものから順にHashと正しい出力を確認していけばO(C*テストケースの数）回の提出ではできそうです。

追記：

提出リンク