OUPC β 解説

fine @refine_P

裏話をすると、writerの僕の最初の解法は筋肉で700点くらいつけるつもりでした。 最初にチェックしてくれたくるさんも筋肉だったし、何ならふるやん君も筋肉だった。 僕が途中で想定解に気づいて死ぬほど恥ずかしくなったので、βで供養しました。 思ったより良い仕事をしてくれたので嬉しいです。

Badlylucky @small_rakkyoes

a8pfactory.hatenablog.com/entry/2020/03/… 解説記事はこちらにまとめておきました。中時間お疲れさまでした。

のいみ @noimi_kyopro

F、積の微分を一切使わなくても、 (ax + b)(cx + d) = ( (ad + bc) x + bd)) (mod x^2) のようなことをすると単純に積を求めて x の係数を出すだけになります

fine @refine_P

「a_i / b_iの総和」だった

Mister @mistterpp

F. 答えは基本(bの総積)*(a/bの総和)なのでセグ木を2本持てばいい ただb=0が「ちょうど1つ」含まれる場合が例外で，特別な処理が要る(結局セグ木がもう2本増えた)

ふるやん @furuya1223

OUPC β 終了しました！　ご参加ありがとうございました！ 僕が作問を担当した「Increasing Path」の解説はこちらです→ creativ.xyz/oupc-beta-edit…

Badlylucky @small_rakkyoes

はてなブログに投稿しました #はてなブログ 【OUPC β C】Power Number 解説 - BsBsこうしょう a8pfactory.hatenablog.com/entry/2020/03/…

くる @ningenMe

OUPC β 参加した人ありがとうございました！ A,B,Dのwriterでした。解説です。 ningenme.hatenablog.com/entry/2020/03/…

fine @refine_P

コメント: ギャグです。 2次以上の項を無視できることに気づくと、セグ木で殴るだけになります。 「b_iの総積」と「b_i / a_i の総和」の積を使って計算しようとすると、b_i=0がコーナーケースになって面倒なので、 そういう風に解こうとした人は少し反省しましょう。

titia @titia_til

あれ、今読み返したら「各原石を任意の個数使うことができるとき、」って書いてある……。 コンテスト中気付かなかったのかな。（すみません）

Mister @mistterpp

C. 10^9を通す犯罪者ムーブをしてしまった D. KはLCM 素因数分解すると，各素因数が各列にあといくつ置かれるかが分かる これをそのままやると素因数の個数が多くてマズいので，各列について差分だけ計算する E. DPの状態として「直前にどのコストの辺を使ったか」を座圧して持つ 実装に筋肉が要る

titia @titia_til

OUPC β Fが解けず。Cが難読な気がしました。（各原石を何回でも使って良いことは書いて欲しい） B DP C まず、各原石から取れる文字とコストを列挙 D a=1のときの値を求めて差分計算 E 最後に通った距離が小さい方から、ダイクストラ風に。 F a/bをBITでbの累積積をセグ木で持てばサンプルは合った。

fine @refine_P

OUPC β 終了しました！ 参加してくれた方ありがとうございました！！ 僕が作問したFのビブンケイスウの解説です refine-p.hatenablog.com/entry/2020/03/…