つちのこの日記

競プロと音ゲーがメインです。

ARC 145 作りました

はじめに

AtCoder Regular Contest 145 で writer をした nok0 です!参加していただいたみなさん、どうもありがとうございました!

楽しんでいただけたら writer 冥利に尽きます。

ぼくが人の作問記を読むのが大好きなので、折角なのでセットのコンセプトや各問題の一言作問経緯などをコメントしていきます。ネタバレが盛大に含まれるので注意してください。

ARC145 セットのコンセプト

前半(A-D)を考察一発の軽実装問で固めて、考察も実装も重い EF 問題を存分に楽しんでもらおうという感じのセットでした。なんと、writer の想定解では A-D の実装の合計が 30 行しかありません。

前半の意図はある程度上手くいったとおもうのですが、後半(特に E 問題)が想定より遥かに難しかったようで、ここは反省ポイントです…

前半は本当にアルゴリズム/データ構造の知識は不要で頭だけで解けますし、後半も ACL よりむずかしい高度な知識は不要なので、是非遊んでみてください!

ARC145 問題別一言コメント

A 問題 AB Palindrome

シンプルな設定ながら自然なコーナーケースもあり、かなりお気に入りの問題です。

この問題は ARC 131-F ARC Stamp が元ネタです。(元ネタの問題はまだ通せていないのですが…)低難易度は文字列を使うと生やしやすいことを前回学んで、

文字列の問題を作ろう→そういえば Stamp 押す問題あったな→文字を二種類にしたら簡単?→回文とセットにするといい感じ!

って感じで散歩しているときに生えました。

コーナーケースが 1 種類なこともあり、こるとん式(同じテストケースを何個も入れる)やマルチテストケースにするなども考えてたのですが、邪悪すぎて admin に止められました。

300 点を主張してたのですが、maspy さんが 400 点主張していて 400 点にしました。本当に変えてよかったです。  

B 問題 AB Game

簡単なゲームを数えさせる問題です。丁寧にやる力が大切?

これは特に元ネタもなくて、適当に生えた気がします。問題セットを組み終わった後に、問題名を A 問題と似た感じにしました(ARC140 もそうですが、ぼくは問題名で遊ぶのが割と好きです)。

C 問題 Split and Maximize

簡単な数え上げ問題です。実験するとすぐにわかったり?困ったら実験するの、大事です。

元ネタは UTPC 2021 Swap and Maximize (自作問) です。問題名を適当に変えて問題を作ろうとして、S から始まる単語を探してたら Split が出てきて、設定もそこから生えていい感じだったので採用しました。

D 問題 Non Arithmetic Progression Set

割となんでも通るタイプの構築問題です。想定解みたいなきれいな感じ以外にも、貪欲、乱択、なんでもあります。

元ネタは勿論(?)chinerist さんの良問、ARC 141-D Non-divisible Set です。とても綺麗な問題だったので、適当に設定を変えて出題してみました。

E 問題 Adjacent XOR

非自明な構築問題です。設定も割ときれいだし、解法も少し非自明で面白く、かなりお気に入りの問題です。少しだけ実装が重い点が玉に傷。

難易度推定を完全にやらかしました。非自明パートが 2 つあるものの、操作回数とかからやること直ぐわかりそうだし、行けるよね?って思っちゃいました。ごめんなさい。(admin さんがこれは D or E と言っていたのもあります) もともと D と E 逆だったんですが、maspy さんの指摘で E に移動しました(本当に移動してよかったです)。

元ネタは ARC 137-D Prefix XORs です。設定をめちゃくちゃパクり、数え上げから構築にしたら何故か解けちゃってびっくりしてました。逆から見るとより難しいことを maspy さんに指摘されて、逆から出題することにしました。

F 問題 Modulo Sum of Increasing Sequences

大ボスの数え上げ問題です。 コンテスト中単独 AC の leukocyte さん、本当におめでとうございます!!(何者?)

もともとはもう少し簡単だったんですが、admin さんとの議論でどんどん難しくなり、1200 点になりました。

やばそうな見た目ですが、形式的冪級数とか怖いものは出てきません。MOD の 3 乗が間に合うことがヒントです、是非挑戦してみてください!

おわりに

初めて単独 writer を出来てとても楽しかったです!たくさんの方に問題を見てもらえて、6 問全部自分の問題なのは本当嬉しいですね。

今回の ARC で温まった方、是非作問して Rated 増やしてください!!!お願いします