yukicoder253のあれこれ
はじめに
ご参加ありがとうございました！！！！！！
ゆるふわ解説
A問題
長さ$N$の数列$A$があって、「$A$を(隣り合う要素の和の数列)で置き換える」を$N-1$回繰り返したときに、最後に残った数は？
$N \le 100$なので、やるだけです(低難易度問題なので)
一応$N \le 10^5$解法はあって、それぞれの$A_i$が答えに含まれる数を睨んでみると、二項係数が見えます。
これ原案がクソすぎました。原案↓
A君は数字$X,Y,Z$を持っている。A君はB君に$X+Y,Y+Z,Z+X$を投げる。B君は投げられた数字の総和を投げ返す。(←この数字なに)
さすがに$2(X+Y+Z)$はつまんなすぎるので、やめました。
B問題
数列$A$を自由に並び替えて、$B=(A$の隣り合う要素の$xor$の数列$)$をつくって、$X=(B$の全要素の$xor)$としたときの$X$の最大値は？
あなたは心の$xor$を知っていますか、みたいな問題です。$xor$の入門みたいなのを目指しました。
$(A xor B)xor B = A$は問題文に貼ったwikipediaに書いてあるし、$(A xor B)xor C = A xor (B xor C)$はとっても自明なので難易度低めです。
式変形フェーズがあるので、この問題とか考慮して☆2にしました。
C問題
整数$K$があって、数列$A$を自由に並び替えて、$X=K\ mod\ A_1\ mod\ A_2\ \dots\ mod\ A_N$としたときの$X$の最大値は？
数学に見せかけた全探索ゲーです。剰余関係の知識はあまりないのでこれくらいしか考察できませんでした。
$N \le 20$なので、お察しだと思いますがbit全探索です。愚直で$O(N!)$くらいかかるのをどうやって$O(2^N)$あたりにするか、っていう問題です。
本質は$x\ mod\ y < y$ と $x\ mod\ y = x(x < y)$です。当たり前だけどこれが効いてきます。
$X$を計算する過程でのお話なんですが、すでに$X < A_i$が確定していたら$X\ mod\ A_i$を計算する必要はありません。また、$A_{i+1}$以降で$A_i$より大きい数も計算する必要はありません。こう考えると計算量改善の余地が見えてきます。
解説めんどくさくなったのでdiscordはいズドーーーン！！
我ながらですが、かなりキレイにまとまった問題だと思います。自信作です。
D問題
数列$A$があって、任意の連続部分列の相乗のうち$10^9$未満のものの相乗は？
主客転倒！！！！！！！！！！
各$A_i$がどれだけ答えに寄与しているかを求めるテクです。一応$A_i$が寄与する回数を$P_i$としておきます。
なんとなく雰囲気を感じると思うんですけど、しゃくとりします。$l$を固定した時に$r$をどこまで右に伸ばせるかを求めます。
$l,r$が決まったら、なんかの配列の区間$[l,l]$に$+1$、$[l,l+1]$に$+1$、$\dots$、$[l,r]$に$+1$をしたくなります。($l$を左端とする相乗が$10^9$未満の連続部分列を求めているのとほぼおんなじ。うまく言語化できないから許して)
これはぱっと見$O(N^2)$かかりそうなんですけど、うまくフラグ管理とかをしてあげるとまとめて処理できます。(ところでimos法のお気持ちでやったwriter解みてみて)
低難易度典型がいろいろ重なっているので☆3にしました。(繰り返し二乗法は常識だよね)
物理好きさんの「数え上げの主客転倒テク」記事を見て作ったやつです。原案(当時水色下位)では$10^9$未満とかの制約はなく、単純に任意連続部分列の相乗の相乗を求めさせようとしていました。(☆2.5にしていた)
コンテスト5日前くらいに現在の問題に変更しました。忙しい中Tester業務増やしてごめんkichiくん！！
今見返したら$P_i$使ってなくて草
E問題
$N$の桁和の桁和......$N$が1桁になるまで($N$を$N$の桁和で置き換える)を繰り返したもの、とします。
一部の桁が確定していない数値が与えられる。桁和の桁和が$D$になる数値の通り数は？
ちなみにDPテーブルを眺めておくとF問題でいいことがあります。
F問題
省略
E問題でDPテーブルを眺めると、やけにきれいな数字が並ぶのでそこから察せたかもしれません。
いろいろ問題が複雑ですが、本質は「$f(N)=i$である桁数$ M $以下の整数$N$の個数は？」という問題です。(コーナーとかで落としたいお気持ちがあるので$O(1)$ではなく複雑にしました)
少し考えるとこれ↓が生えるので丁寧丁寧丁寧に実装するとACできます。
競プロっぽくはないですが、様々なジャンルの問題を出したかったので、これもいいかな～って思っています。(ギャグ問題ですか？)
G問題
行列$S$があって、$A=($行の転倒数の数列$)$、$B=($列の転倒数の数列$)$、としたときに$A$の転倒数と$B$の転倒数が$K$になる$S$を構築して？
行列関係のワードに疎いので誤用していると思います......
天才パズルになれたでしょうか。(この記事を書いているのはコンテストの前日なので、気になっています。)
問題を思いつくのに3分、解法(ゆきこ解説の解法1)を思いつくのに3日かかりました。
かなり解法がたくさんありそうな予感がしますので、難易度推定に困りました。(TesterのQCFiumさんに結局決めてもらいました。)(QCさんがACにやや苦戦していたのを見てニヤニヤしていたのは秘密です。)
解法1の本質だけ解説すると、$(1,0,\dots,0,0,0,1,0)$も$(1,0,\dots,0,0,1,1,0)$も$(1,0,\dots,0,1,1,1,0)$も$(1,0,\dots,1,1,1,1,0)$も転倒数は変わりません。こんな感じの性質をうまく使うと解法1が生えます。
ちゃんと解説してませんがゆるふわってことで許してください。
編集後記的な何か
最初に作った問題(D問題)は半年以上温めていましたが、ようやくこれらの問題を出すことができてホッとしています。
(お涙頂戴物語ですが、)writerとして右も左もわからない自分でもこう、あれができたのはyukicoderさんとtesterさんのおかげです......本当にありがとうございます。
ところで、これらの問題名はすべて○○の○○という形になっています。最近yukicoderに流行っているシリーズセットです。この縛りのおかげで生えた問題もいくつかあったので、作問しててとても楽しかったです。
あと、ボス問はスペシャルジャッジ問題(解が複数存在しうる問題)だったのですが、yukicoderの仕様がわからず困っていたところをmaspyさんのこの問題のジャッジコードに救われました......とてもわかりやすくmaspyさんがコードを書いていたのと、yukicoderさんがそれを一般公開していたのが本当にありがてえになりました。
ご参加ありがとうございました！(問題がfavされると喜びます)
