Intel Code Challenge Elimination Round (Div.1 + Div.2, combined)

有為 @uwitenpen

C, よくみかけるけどCSAcademyの最近のコンテストで出たと思う

(nは自然数) @n_vip

div2の2500のつもりでいたので死亡

sigma @sigma425

Dまでの最難はBです

とーらす🌸📦🌕✨🍀 @torus711

やったこと　D: 逆操作を考えると右シフトになる．各値について，右シフトで作れる値からは元の値を生成できる．最大値を小さくしたいので，各時点で最大な値を取って，右シフトで重複しないものを作れるなら置き換えることを繰り返す

pekempey @pekempey

Bはスペースで強制的に単語が切れるから "a a" と "aa" では作れるものが違うと解釈したけど合ってるのか

nico_shindannin（診断人） @nico_shindannin

【ニコ生放送中】 TopCoderでプログラムしてみた 第2292回(Codeforces Intel Code Challenge 直後放送) nico.ms/lv277692028#01… #co78570 pic.twitter.com/tx9mUBliMl

拡大

有為 @uwitenpen

@sigma425 障害物の個数が小さいのでそっちでやってける

btk @btk15049

DでN×log^3とかいうガバガバ実装したけど10^8ぐらいだし大丈夫だよね

競技プログラミング @LatteMalta

A、 12 61:00 とかで落ちるやつとかがあって、楽しかった

有為 @uwitenpen

視力がなかった

あんた @anta_prg

A：Div2の人は何故か間違えるらしい。B：読解合ってるかわからない…。D：にぶたん＆greedyしたけど。E：前に同じ問題を見たけどその時は3乗を許す制約だった記憶…。F：盛大に勘違いしていてWAで気づく…01:59で記念submitできたけど全く考えられてないので通ったら驚く

有為 @uwitenpen

@sigma425 重複とか気にせずにゴールまで踏んだ回数を持ってDPしたあと、k回踏んだ回数を、ans[k]=dp[k] - ans[k+1]*C(k+1,k)-ans[k+2]*C(k+2,k)...みたいにしたら一応いけた。多分これをもっと都合よく変換すればいけそう？

(nは自然数) @n_vip

そういえばEはたまに見る気がしていたけど制約が厳し目だったのか（絶対見たことあるのに全然解けなくて辛かった）

sigma @sigma425

レート激落ちくんナリ(チャレンジに文句をいうことも出来るが,まあEF解けないのが悪い)

koyumeishi @koyumeishi_

div1のchallenge/hackって「この(誤)方針でやってる人いそう」とか「ここでオーバーフローさせるやつおるやろ」って着眼点決めて投げるイメージだけど、div2 ABあたりってもっと異質な嘘コードが散らかってる印象で、div1とは違うスキルが要求されてそう

sigma @sigma425

@uwitenpen 冷静に考えるとk個固定 が求まるんだからその包除でいいですね・・・(頭ついてなかった)

sigma @sigma425

なんで気づかなかったんだこれ

有為 @uwitenpen

@sigma425 ただ問題はそのあとっすね、21個以上をいかにうまく端折るか

sigma @sigma425

幼稚園児

pekempey @pekempey

うーん、DがO(nlog^3n)がなってて更に定数倍重そうで危険な気がする

有為 @uwitenpen

@sigma425 あっこれちゃんとやるとO(n^3)か