はじめに
昨日くらいから高3になったらしいです、Falcon_ と言います。
AtCoder は、現在 1541 、 highest 1618 です。青だったのは一週間だけです。（悲しい...)
中 1 で始めて、中 1 の間に水色になったのですが、そこから伸び悩んで中 3 くらいに引退したんですが、惰性で JOI に参加していたら高 1 でなんかよくわからないけど春合宿に行って、そこで再開したら？と言われて高 2 の 11 月くらいに復帰しました。
ちなみに今年の JOI は本選で 100-100-48-46-3 の 297 点でボーダーマイナス10点とかで落ちました。 C の満点解法は残り 30 分くらいで思いついたんですが普通に実装が間に合いませんでした。悲しい...
SpeedRunの話
今年パ研合宿に参加するのも最後だなー、ということで writer をやりたかったので SpeedRun と非競技 Freedom の writer をやりました。Freedom はオンサイトでしかできないものなので詳しくは話しませんが、簡単に言うと writer がやりたい放題やるコンテスト () です。writer 経験は yukicoder で新入生プログラミングコンテストで 2 問くらい出してた気がするのと、AtCoder では Polyomino Tiling を作問していました。後者は他の人に強化されていたのでまあほぼないようなものです。
SpeedRun の原案を考え始めたのは文化祭終わってからくらいで、合計 12,3 問くらい投げた気がします。 1 問はよく考えると NP-hard 、他は普通に面白くないとかの理由で没になりました。問題は思いついたらとりあえず同期にいる shiomusubi496 って人の DM に投げつけていました。
1 月くらいにサーバーに招待され、とりあえず問題案を投げまくれということであまり解法が詰まっていないような問題も何個か投げていました。
ここから解放言及があるのでまだ解いていない人は解いてみてもいいと思います。
C One Half
解法から考えました。
累積和と二分探索を使う問題とかどうかなーと思って投げて、ストーリーをつけようとしたんですがなくなりました。
テストケースとかも作るの楽で、自己完結した問題の一つです。 B がちょっと実装だるくて、 D がグラフに関する理解がある程度必要で、いい感じの難易度じゃないかなーと思っていたのですが、 D のほうが解かれていました。
H Buttons
これはピアノの鍵盤みたいなのが奥にもあったらおもろいなー、というところから思いつきました。
普通に DP で $O(N)$ の問題にするつもりだったのですが、漸化式に落ちて累乗 1 つで表すことができるらしく、 ytqm3 が $O(digit(N))$ に強化しました。
部分点で $O(N)$ 、 $O(log(N))$ を出しました。前者は DP 、後者は累乗を導く、満点解法はフェルマーの小定理を使います。
解かれ具合は割と想定通りかなーという感じです、G が想定より解かれていませんでした。数字の文字列で巨大数の管理をするのが割と面倒でテストケース生成、validation の生成に割と苦労しました。
が、こんなものは序の口です。
I ×2±1
これは実は弱体化されています。
元々の問題は、最小回数とその個数を求めさせていました。
実際に出題された問題は適当な考察でも割と通ってしまうのですが、個数まで求めさせるとそこそこ考察が必要です。
考察
これは 2 進数を考えるとかなり解きやすいです。
- $\times 2+1$ を前の数の 2 進数の末尾に $1$ を追加する。
- $\times 2-1$ を前の数の 2 進数の末尾から数えて最初にある $1$ を $0$ にし、それ以下を $1$ にした上で、末尾に $1$ を追加する。
と言い換えられます。しかし、$1$ 回以上の操作をすると必ず奇数になるため、2 回目以降の後者の操作は、
末尾の $1$ を $0$ に変えた上で末尾に $1$ を追加する。
となります。色々証明はさぼりますが、結局大きい方の数は高々 $1$ 回しか操作する必要がないことがわかります。また色々証明をさぼりますが、最小回数の個数は高々 $2$ 回だとわかります。これは自分の証明が割と微妙だったのと、実装が不快すぎるということで今回の問題になりました。
テストケースなど
数字 2 個だったので結構楽でした。だいぶましな方です。
実際これ元の問題で出してたら SpeedRun ではない気がします。
K Cube Construction
なんか天から降ってきました。元々は 3 方向から見て外の辺の部分に枠がついた穴が連結でない正方形、みたいにしていましたが、普通に解けなかったので弱体化されました。
考察は面倒なのでさぼりますが、ほぼ下界で構築可能です。
( 奇数 , 奇数 , 奇数 ) だけで構成した立方体で穴がない正方形と( 偶数 , 偶数 , 偶数 ) だけで構成した立方体で穴がない正方形を合体するだけで解けるという結構面白い問題だったと思います。
output checker を shiomusubi496 に書いてもらいましたが、それ以外のテストケースとかは何とかなりました。
この問題を 17 人しか解いてないの、さすがに順位表マジックだと思います。
M Strong String
題名から考えました。
割と既出っぽい見た目の問題です。これも普通に DP で解く問題のつもりでしたが、ytqm3 が強化しました。個人的には行列累乗で解くのが一番考察的には楽だと思います。
この問題はあんま思い入れがないです (え？)
N と AC 数が一緒なので、まあまあ場所と難易度は一致してたと思います。
P Bombard
Among Us の mod 役職、波動砲が元ネタです。
右方向にしか撃てないの、面白いなーと思ってみていたら問題になりました。直前に JOI の fortune_telling を解いていたのもあって、平面走査と遅延セグ木を使えば $O(N^2)$ になることには気づいたんですが、$N$ 個の一次式で表せそうだったので Convex Hull Trick をうまく使えないかなーと思って投げたら shiomusubi496 に Li-Chao Tree というものの存在を教えてもらいました。
テストケース
これ、本当に不可能です。
$10^9 \times 10^9$ のグリッド上にランダムに矩形領域を配置することを考えると、 AHC001 の AtCoder Ad を提示されました。
ここで shiomusubi496 の AC コードをパクってきて適当に実行したんですが、実行時間があまりにも長すぎて仕事を投げました。
最終的には $N$ 個の領域に分けた上で、その中にランダムな長方形を $1$ つ作ったらしいです。
validation
遅延セグ木書くのだるいなーと思っていたんですが、区間を set で持つテクというものがあるらしいです。
テストケースと validation を投げたのは若干申し訳ないなーと思いつつ、自分で持ってたらそれはそれで直前まで終わらなかった可能性が結構高いのでまあ許します。
ちなみに 2 人しか AC がでませんでした。というか、600 点問題が全体的に難しすぎる。SpeedRun とはなんだったのでしょうか。
没問 Rectangle Division
無限に広がるグリッドがあり、$i$ 行目 $j$ 列目のグリッドには $i \times j$ ($1 \leq i$, $1 \leq j$)が書かれている。
このとき、グリッドの直線に沿って長方形状にマス目をくり抜いたときの総和が $S$ になるくりぬき方は何通りあるか。
また算数です。これは時事で、2025 が九九表の総和というところからきています。
結論から言うと、$S$ を大きくするとボトルネックが素因数分解になり、小さくすると愚直が通るので、競プロ向きではないということで没になりました。
眠くて答えを書きたくないので、頑張って考えてください。
終わりに
作問、結構面白かったです。
高 3 になって受験勉強をまじめにやらないとまずい時期になってきたので受験終わるまで競プロをやることは極端に少なくなると思いますが、終わったら作問もまたやろうかなと思っています。