yukicoder contest 235 解法

コンテストページ

解法

✔A - ミスターマックスバリュ

おしゃれ提出です。

if(MrMax)Console.Write("Mr");
if(MrMax&&MaxValu)Console.Write("Max");
else Console.Write(-1);
if(MaxValu)Console.Write("Valu");
Console.Write('\n');

✔B - 2 の 128 乗と M

2 倍して M で割るを 128 回繰り返しましょう。

✔C - アリス仕掛けの摩天楼

writer でした。

✔D - Fibonacci Convolution Easy

マス目に数字を書いていくと、等号付斜め上を足す感じになります。そこで、全体を足して対角線を引いて 2 で割りましょう。

✔E - Longest Divisor Sequence

writer でした。

✔F - Fibonacci Convolution Hard

もとの数列の母関数は 1 / (1 - pX -X²) ですから、それを二乗すればよいです。二乗をすると 1 / (1 - 2pX + (p² - 2)X² + 2pX³ + X⁴) になりますから、漸化式は係数を順番に読んで、a_4 = 2p a_3 - (p² - 2)a_2 - 2pa_1 - a_0 のようになります。

writer の keymoon さん「コンテスト中にACした人の大半が畳込みでした。現代の技術、すげー。」

ツイッターの様子

B について

Bで「Mデカいから繰り返し二乗法出来ないやん！せや！__int_128使ったろ！」とか言ってたんですが、128乗しかしないので愚直にやれば良かった...
— 卒論に内容はいらない！ (@kyort0n) January 31, 2020

これ絶対やる人いると思いました。

C について

A プログラミングをします
B BigIntくん、よろしく(丸投げ)
C 問題文でクソ笑っていたらコーナー(サイクル,1)を見落としました策士か?
E DPをします
— keymoon (@kymn_) January 31, 2020

ゆきこ、Cはかなり好き
Fは難易度過大評価な気もする
— さかな (@Enjapma_kyopro) January 31, 2020

えへへ

Cみたいなのはアレだよね SRMでやりたい
— 卒論に内容はいらない！ (@kyort0n) January 31, 2020

SRM をよく知らないのですが、悪い意味でしょうか。

E について

yukicoder 235
E:
tester 解は Θ(N+log(N)Alog(log(A))) だったんですが、多分約数全列挙するのが楽で泣いた
F:
10^18, p, q 全部クエリでも良かったんじゃないだろうか
— 熨斗袋 (@noshi91) January 31, 2020

これです。tester 解を読んで、ほえーーとなっていました。

F について

F、解説のやりかた割と好きなので見てほしい
— keymoon (@kymn_) January 31, 2020

ゆきこFは10^18&クエリ形式でも解けるね
— heno (@heno_code) January 31, 2020

4 x 4 の行列累乗でしょうか。

Writerでした。
D a_1～a_nが幅のグリッドを考えると良いです。
F 式をいじっていたら出てきたので置きました with 畳込み絶対殺すマン(n=10^6) ちゃんとボスとして保ってくれたように見えて、かなり畳込みで通されてしまっているので敗北…
畳み込み勢は、人間的な解法も考えてあげてください…(血涙)
— keymoon (@kymn_) January 31, 2020

畳込み絶対殺すマン好きです。

F：
a_i はf(x) = x / (1 - px - x^2) の係数。よって、計算対象は、

x^2 / (1 - px - x^2)^2

の係数。分母を 1-ax-bx^2+cx^3+dx^4 とすると、答 f_n は、漸化式 f_{n+4} = af_{n+3}+bf_{n+2}+cf_{n+1}+df_n を満たすので解けました。
— maspy (@maspy_stars) January 31, 2020

mapsy さんは絶対これで解くと思っていました！

F、想定が行列を転置すると楽しい!で、多分これで解いている人は一人としていない pic.twitter.com/ZRWGecVdx5
— keymoon (@kymn_) January 31, 2020

そして想定解が最高すぎるんですよね。

ブログ名

競技プログラミングやお歌のお話をする高菜です。