コンテストURL: https://yukicoder.me/contests/415
ここのところ体調不良で低浮上気味ですが、徐々に良くなってきている感じがします。元々夜はすごく眠い体質なのですが、今は１日中常に眠い状態です。寝ると少し体調が楽になるのでとにかくひたすら寝ています。
さて、１ヶ月ぶりの単著コンテストです。リアクティブコンテスト！ 2024年7月30日にコンテスト発案をして、2年近く経ってしまいました！
無事に開催できてとても嬉しいです。testerの皆様にたくさん助けていただき、本当に頭が上がりません。
前回の単著コンテストはtesterなしでの開催に初挑戦したのですが、大きな不備こそなかったとはいえやはり参加者には不満の残るコンテストになってしまったのではないかと思い、この経験を踏まえて更にtesterのありがたさが身にしみました。
著者もtesterとしてもっと精進をして、人々のコンテスト開催の役に立てたらとは思っているのですがまだまだ至らないところが多いです。testerのご依頼をくだされば難易度次第ではお引き受けいたしますので遠慮なくご依頼ください。
さて、F問題で問題文の修正が必要な不備がございまして申し訳ございませんでした。clarも9件と多く、全体的に問題文が分かりにくかったと反省しております。毎回反省点が多いですが、今回は特に「いかに問題文をシンプルで分かりやすくするか」への注力不足が浮き彫りになったので今後の作問ではそこにもっと気をつけていこうと思います。
ちなみにいつもは特殊ジャッジ問題があるとその問題への提出があるたびジャッジステータスがAC以外の場合はジャッジのエラー出力等を確認する作業をこまめに行うようにしているのですが、今回は全問特殊ジャッジだったのでコンテスト開催期間中ずっとジャッジのエラー出力を確認し続ける状態になり、ひいひい言っていました。
それでは参加者の方々、testerの方々、皆様ありがとうございました！
A: No.3518 座標当てゲーム ★☆ | ||
|---|---|---|
| 問題リンク：https://yukicoder.me/problems/no/3518 tester：loop0919さん | ||
| まずはリアクティブ形式に慣れるための問題です。質問回数が少ないのでやれることは限られており、考察部分で悩むことは少ないと思います。 隠されている値は$X$だけで、出力も$\lvert x - X \rvert$という非常にシンプルな値なので、デバッグ用にリアクティブの入出力を実装する練習にもなるんじゃないかなと思います。 | ||
B: No.3519 A/B問題 ★★ | ||
|---|---|---|
| 問題リンク：https://yukicoder.me/problems/no/3519 tester：loop0919さん | ||
| A問題のように隠された数値そのものを当てるのがリアクティブで最も典型な問題だと思いますが、今回はブラックボックス操作問題。隠された数値への操作をジャッジに指示することで目的の値を計算させる問題です。 各操作で隠された数値自体が変化していってしまうので、二分探索などで元の数値を特定することは困難です。 ブラックボックス操作全般に言えることですが、隠された数値が分かっている場合に目的の値を計算する方法を考えて、隠された数値を引数のように扱ってアルゴリズム化することでこの問題を解くことができます。 | ||
C: No.3520 L1等距離点 ★★☆ | ||
|---|---|---|
| 問題リンク：https://yukicoder.me/problems/no/3520 tester：binapさん | ||
| リアクティブのお供に頻出なアルゴリズムは二分探索です。ただし一言で二分探索と言っても様々な適用パターンがあります。 最もよく見るパターンは単調性が分かっている関数の閾値以下での最大値や閾値以上での最小値を求めるパターンだと思いますが、実は単調でない関数に対しても二分探索が適用可能な状況がちらほらあります。 この問題を通じて、単調じゃない場合の二分探索も身に付けていただければ幸いです。 | ||
D: No.3521 接線の傾き ★★☆ | ||
|---|---|---|
| 問題リンク：https://yukicoder.me/problems/no/3521 tester：t9unkubjさん | ||
| 数学の有名問題ですが、競技プログラミングでは有名ではないかもしれないと思い出題させていただきました。 質問回数に十分余裕を持たせておいたので様々な解法が想定されますが、リアクティブはデバッグが困難なのでいかに実装の楽な（実装でミスをしにくい）解法に絞り込むかが大事になってくると思います。 ミスをしやすい実装しか思いつかなかった場合はデバッグ用に入出力の関数を自分で用意するという選択肢も検討していきましょう。 | ||
E: No.3522 冪乗乗 ★★★ | ||
|---|---|---|
| 問題リンク：https://yukicoder.me/problems/no/3522 tester：binapさん | ||
| 競技プログラミングでたまに出くわす、繰り返し$M$乗法です。 繰り返し二乗法を原理から理解していれば問題なく実装できると思いますが、繰り返し$M$乗法に出会ったことがないと盲点になるかもしれません。 この手のリアクティブあるあるですが、頑張れば隠された数値$B$そのものが特定できてしまうというご愛嬌です。正攻法の解き方が分からなかったら特定を検討してみるのも良いですね。 | ||
F: No.3523 順路指定最近点 ★★★ | ||
|---|---|---|
| 問題リンク：https://yukicoder.me/problems/no/3523 tester：t9unkubjさん | ||
| 問題設定が難読になってしまいすみません。。やや複雑な設定なため、正確に意図を伝えるにはこれくらいしっかり書く必要があると思い、こうなりました。 それでもなお問題文に不備があり、誠に申し訳ございませんでした。そして同時に複数人から別々の問題へのclarを受け取っていたため対応に遅れが生じておりました。clarをしてくださった方々に多大なご迷惑をおかけしたことを深くお詫び申し上げます。 読解さえ乗り越えてしまえば実装自体は軽く、ダイクストラ法の理解を問う問題になる想定でした。 問題文の不備が悔やまれます。。 | ||
G: No.3524 二進範囲更新範囲和取得 ★★★★ | ||
|---|---|---|
| 問題リンク：https://yukicoder.me/problems/no/3524 tester：binapさん | ||
| コンテストの難易度勾配的に★3.5を作りたかったのですが、★3.5の作問が苦手でうまくいかず★4となってしまいました。 リアクティブ要素が何のためにあるのかパッと見で分かりにくいかもしれませんが、入力を先読みできなくすることでクエリ先読み系の解法を防ぐ役割があります。 クエリ先読みと言えば逆順処理やMoのアルゴリズム、そして座標圧縮ですね。座標圧縮を許さないことでメモリ制限を活かせて、非想定解の遅延セグメント木が工夫なしでは落ちてくれることを狙いました。 残念ながら本番0ACとなってしまいましたが、ぜひ挑戦していただけると嬉しいです。 | ||
H: No.3525 擬奇平方数 ★★★★☆ | ||
|---|---|---|
| 問題リンク：https://yukicoder.me/problems/no/3525 tester：binapさん、hotman78さん | ||
| 非常に作問に苦戦した問題です。testerさんのお二人にはとてもご尽力いただきました。 難易度は非常に高くなってしまいましたが、この問題を通じて整数論の楽しさをおすそ分けさせていただきたいと思います。 | ||