yukicoderでコンテストを開催しました

3/1(金)21:20~23:50に、yukicoderでコンテストを開催しました。それに関するあれこれを書きました。
コンテスト： yukicoder contest 419 https://yukicoder.me/contests/485

開催までのいきさつ

3年前くらいから作問してみたいと思っていましたが、ちっともアイデアが浮かばずほとんど作れませんでした。 半年ほど前に初めて、自分でも面白い！と思える問題を作ることができ、 それをきっかけに… かどうか分かりませんが急にアイデアが湧いてくるようになりました。

風呂につかっている時間が作問時間になっていて、コンスタントに問題数が増えていき、 年末ごろに15問くらいたまったので、年末年始の休み中にyukicoderに登録しようと一念発起し、今回の開催に至ります。

作問作業は思っていたよりずっと大変でした。年末年始で6問登録しようと思っていたら1問しかできず、 以降週1問ペースでちょっとずつ作業していました。問題文と解説を書くのが特に大変でした…

しかし、testerさんに解いてもらえるだけでめちゃくちゃ嬉しいもので、頑張った甲斐があったなあと思いました。 この文はコンテスト開催前に書いてますが、コンテストでたくさんの人に解いてもらえたらもう大変なことになりそうです。

各問題について

A問題 Increasing Strides

問題ページ

tester: p-adicさん

風呂につかりながらふと、1メートルずつ増やしながら直角に曲がったら元に戻れるだろうかと思い浮かび、 うまいこと解けたのでほぼそのまま問題になりました。 当初はNが偶数限定でしたが、全体テスターのてんぷらさんに奇数でも解けると言われて急遽奇数もありにしました。 不可能の判定が、奇数集合と偶数集合で補い合ってて面白いなあと思っています。
個別テスターのp-adicさんには何度も相談させてもらい、大変お世話になりました。

B問題 XOR Slimes

問題ページ

tester: p-adicさん

XORは和より必ず小さいのがミソで、隣と合体するかどうかだけ考えれば良さそうな気がしつつ、ほんとにそれでいいのかすぐには分からない、 という問題です。考察部分面白いなと思い、6問のうちまずはじめに出題を決めた問題でした。

C問題 Falling Block Game

問題ページ

tester: AngrySadEightさん

この問題は3年前に原案を考えたもので、当時はスタート地点1カ所で、想定解は「答固定して下に到達できるか判定、にぶたん」でした。 最近その問題を久しぶりに思い出して、logが落とせそうだなあと考えているうちに、 多点スタートにすればそれを効果的に問えると気付いて完成しました。 にぶたん解法に誤誘導するために問題文に「最大値を最小化」の決まり文句を入れておきました。
ちなみに私は問題文のとおり本当に腱鞘炎で、3年前の時点でそれをネタにしようとしてました。そして未だに治らずです…

D問題 L-R Nim

問題ページ

tester: Nachiaさん

Nimで、自由に山を選んだらどうなるだろうというところからあれこれ設定を考えて、 かなり紆余曲折してできた問題です。最終的に「どこか一か所に±1」で出題しようとしてましたが、 それを±xにしてもそれほど候補が増えないことに気が付いて「これだー！」となりました。
当初N=1000にしていましたが、NachiaさんにきれいなO(N^2)解で通されてしまい、 それを落とすための制約調整＆テストケース作成が難しくてめちゃくちゃ大変でした。 普通にテストケースを作ると解なしか解だらけになってしまうので、工夫がいります。 テストケース生成関数のバージョンが18までいきました。

E問題 Manga App

問題ページ

tester: nok0さん

某漫画アプリそのものに近い設定の問題です。 実際、寝る時間と時短アイテムを使うタイミングの関係によく悩んでいたので、 これ問題にならないかなあと思って考え始めました。ただの貪欲かなと思っていたら、じわじわと反例が出てきて、思っていた以上に難しい問題になりました。
解説に書いた「O(N^3)のDP」が当初の解法で、それをO(N^2)だと思っていました。 解説を厳密に書いていくうちに、あれ、きっとO(N^2)だろうけど、なかなか絶対と言い切れないな…となり、 2日くらい考えた結果、逆にO(N^3)のテストケースができあがってしまいました。
しかし残念ながら、nok0さんにはマラソン解法で、 全体テスターのてんぷらさんには普通の高速化？でO(N^3)解を通されてしまっています。 マラソン解法は追加テストケースで防げましたが、てんぷらさんのは高速化なので防げなさそうです…

F問題 Sweep Cards (Easy)

問題ページ

tester: chineristACさん

当初は、Nマスのマス目にカードの山が置かれる問題でした。つまり空いたマスもあって、空き方も数える問題でした。 解き方も、解説で触れたO(N^2)のDPでした。
ふと、昔noya2さんのtesterをしたときの鬼ムズ問題（https://yukicoder.me/problems/no/1939） と雰囲気が似ていることに気付き、ラグランジュ反転で解けることに気付いて飛び上がりました。
更にびっくりなことに、マス目をなくして空いたら詰めるような問題設定にすると、 最近勉強したラグランジュ反転のk乗のついたやつまで適用出来て直接解が求まってしまうことが分かり、脳汁ドバドバになりました。
そのときのツイート：https://x.com/hamamu_kyopro/status/1745437789553086882?s=20
控え目に書いてますが、実際はもう、手が震えたりして興奮すごかったです。
だいぶ背伸びした問題だったので、 テスターのchineristACさんにとてもお世話になって何とか形になりました。 畳込むとO(NlogN)になる式がOEISに載っているのを教えてもらい、Nの上限を10^7にしました。O(N)にする高速化を想定にするのはマニアックすぎるかなとはじめ思いましたが、既にラグランジュ反転を要求してるし、ゆきこだし、OEISを避けるという大義名分もあるし(?)でまあいいかなとなりました。

G問題 Sweep Cards (Hard)

問題ページ

tester: いやもはや writer: chineristACさん

chineristACさんより、F問題のOEIS回避にこうするのはどうでしょうと提案された問題です。 軽い感じで書いてあったのでちょっとした変更なのかなと思っていたら、 じっくり見れば見るほど意味不明（式は追えるが何でそんな事するのか分からないの意）で、 でも何か解けていて、鳩に豆鉄砲状態でした。 何故この式変形をしようと思ったのか質問したら、 「僕もびっくりしました」とのことだったので、きっと神が降臨しているのだと思います。 （すみません、ちょっとおもしろおかしく切り取りしました）
だいぶ元の問題と違う解き方になるので、別問題に分けることにして、G問題が生まれました。 ぜひ数え上げ達人の方々に考えてみて欲しい問題です。

おわりに

準備が大変だったのでしばらく休みたいですが、 問題はだいぶたまっているのでそのうちまたやりたいなと思っています。

AtCoder Regular Contest 116 D - I Wanna Win The Game FPS解法

AtCoder Regular Contest 116 D - I Wanna Win The Game

https://atcoder.jp/contests/arc116/tasks/arc116_d

 

問題概要

長さ Nの整数列 Aであり、以下の条件を満たすものの個数は？

- 0 \le A_i (i=1, 2, \dots , N)

- \sum_{i=1}^N A_i=M

- A_1 xor A_2 xor \cdots xor A_N = 0

 

FPSを使った解法

3つ目のxorの条件より、 A_1~ A_Nの第 bビット (b=0,1,\dots)の N個のうち、 1であるものは偶数個。また、第 bビットの和への寄与は 2^bである。

次数が和、係数がその個数となる多項式を考える。第 bビットに関する多項式 f_b(x)は、 1が 2i個の時に対応する項が {}_N C_{2i} x^{2i*2^b}なので、
f_b(x) = \sum_i {}_N C_{2i} x^{2i*2^b}
である。
よって、全ビット合わせた多項式は
f(x)=\prod_b f_b(x)
と表せる。 [x^M]f(x)が答。

 

考察メモ AtCoder Regular Contest 139 B - Make N

AtCoder Regular Contest 139 B - Make N
https://atcoder.jp/contests/arc139/tasks/arc139_b

 

問題概要
1\le N,A,B,X,Y,Z\le 10^9が与えられる。
P=0 の状態から、
操作1:コストXでPを1増やす
操作2:コストYでPをA増やす
操作3:コストZでPをB増やす
の3種類のどの操作も任意の回数行える。P=Nにするためのコストの最小値を求めよ。

 

自分の失敗考察
操作2の単位増加あたりのコスト(つまりY/A)がXより大きいなら、操作2は不要。
その時はO(1)で解ける。操作3についても同様。
難しいのはそれ以外の時、操作2と3をできるだけ使って、余った分だけ操作1を使う時。
Y/AとB/Zの小さい方の操作…★ が多い方が良さそうだが、
余りが大きくなって操作1が増えると逆転がある。
★を貪欲に使えるだけ使った時を考え、
そこから操作数を1ずつ減らしていって試していくと、そのうち最適解に辿り着く？
考えてみると、AとBの最小公倍数分だけAが減ると、
余りの量が元に戻るので、周期的になる。
ということは、A,Bが大きいと間に合わないからだめ。

他、余りの量を0から順に増やしていって、
各試行で拡張ユークリッドの互除法をすることを考えて、
うまい性質があったりしないか考えたがだめ。

 

正解方針
自分の考察でも半分はOK。
A,Bが大きい時は、単に操作2の回数を全探索すればよい。
Aが \sqrt{N}以上なら全探索、 \sqrt{N}未満なら自分の考察の方法、と切り替えれば、O( \sqrt{N})で解ける。

 

考察典型化
「最小の時も最大の時もO(1)ならO( \sqrt{N})を疑う」
\sqrt{N}を境に解法を切り替えればよいパターンを疑う。

 

自分の思考の癖の補正
「○○が小さい時は解けるけど…」等と思った時に、
その解法を諦めて別の解法を探して迷走することが多い。
「小さい時はこれで解決、後は大きい時を解けばよい」と考えるようにすれば、
2つ以上の解法を切り替えるタイプの問題で迷走はしなくなる。

考察メモ yukicoder contest 340 C No.1910 High Element on Grid

yukicoder contest 340 C
No.1910 High Element on Grid
https://yukicoder.me/problems/no/1910

 

自分の失敗方針
A_{ij}を頂点とみなし、大小関係を決めた2頂点間に有向辺を張ることを考えた。
R_i, C_jを満たすように、かつループができないように有向辺を張ることができれば、
トポロジカルソートすることで全ての大小関係を満たす数値を振ることができて、解ける。
しかし、ループができないような張り方を思いつくことができず。

 

正解方針
R_1=C_1=1を満たすには、左上( A_{11})を \inftyにしさえすればよく、
残りの上辺と左辺( A_{12}~ A_{1W}、 A_{21}~ A_{H1})は自由にできる。
つまり、例えば A_{1j}なら、縦一列( A_{1j}~ A_{Hj})に対する条件である C_jを満たすことに全力投球できる。
そこで、 A_{1j}以外( A_{2j}~ A_{Hj})を特定の状態にしておいて、 A_{1j}だけ調整することで C_jを満たせないか考えてみる。
これは可能で、 A_{2j}~ A_{Hj}を昇順にしておけば、 A_{1j}の調整だけで「高い項」の個数を1~Hまで任意に実現できる。
横一列も同様に実現できるのでこれで解ける。


無理やり考察典型化
「構築問題で自由度が高いところを見つけたら、そこだけ調節して条件を満たせないか考えてみる」
今回、左上を \inftyにすること、更にそれにより上辺と左辺は自由な値を取れることまで気が付いていた。
それを生かすことができなかった。もう少し生かそうと考えていれば思いつけていたような気がする。

考察メモ Codeforces Round #782 (Div. 2) D. GCD Guess

Codeforces Round #782 (Div. 2) D. GCD Guess

https://codeforces.com/contest/1665/problem/D

 

問題概要：

インタラクティブ問題。

1≦x≦10^9なるxを当てる。

1以上2*10^9以下の2整数a,bをクエリ出力すると、gcd(x+a,x+b)が返ってくる。

30クエリ以内にxを当てよ。

 

自分の失敗方針：

以下、自分の考えた失敗方針。
xが2で何回割れるかを知ることを繰り返す作戦を考えた。
つまり、x=2^y*x'のyを求める。
これはa=2^29,b=2^30とすれば分かる。x'は奇数。
次に、x'に1を足して偶数にし、それが2で何回割れるか調べる。
a=2^y,b=2^y+2^29とすればよい。
これを繰り返す。

しかしこれだとあと一歩のところで求まらない、2^30を足さなければならない。
しかし2^30をたすと制約b≦2*10^9を超えてしまう。

 

正解方針：

正解方針は、xの各bitを調べるように考えること。
下のbitから決定することが可能。
第(i-1)bit(0-index)まで判明したら、それらを引いてから第ibitを調べる、と考える。
引く値をrとすると、負が許されるならa=-r,b=-r+2^(i+1)とすればよい。
返ってきた値が2^iなら第ibitは1と分かる。

しかし引き算はできないので、2^iを足してから引き算し、求めたbitを反転する。
すなわち、a=2^i-r,b=2^i-r+2^(i+1)とする。

 

自分の思考の癖を直すための、無理やり考察典型化：

「2進数で考える」
2で何度も割りたくなったら、無理やりにでも2進数のビットで考えられないか検討する、うまくいけば見通しが良くなる。

 

「一気に決められそうな時でも、1つずつ決めると簡単になることあり」
一気に割れる時でも(2^yのように)、一歩ずつにして考えることで単純化できないか確認する。