Codechef - Starters 173
https://www.codechef.com/START173
参加してみた。<2700 ratedらしいが、あんまり出てないからratedだった。
簡単枠はともかく、後半の問題はおおむね良質だった。サンプルの説明は不親切がち?
ラスト1分で全完出来た。
大体残り1分とかになると冷静にデバッグできなくて終わりがちなんだけど、レートも何も気にしてなかったからか冷静さを保てた。大事なコンテストでもこうありたいね。
ん?今気づいたけど賞金もらえるっぽい?やったー。
COOLCHECK
面白い。twitterでも好評っぽい。
Aが1種類:簡単
2種類以上
x != y を取ってくると、x,y mod 2~17 はどれかが異なる(LCM>=1e7なため)
18 個以上あれば、x,y以外とxまたはyでどっちかが平均が整数でなくなる
17 個以下なら全探索
(LCMちゃんと見積もらず適当に 16 にして 1 WA、雑見積もりで19にしてさらに雑実装により 1 TLE、え?)
1...x の LCM を最も速く調べる方法募集中
OEISに1,2,6,12 と打ち込み、https://oeis.org/A003418/list を見るとか?
寄せられた回答:https://www.wolframalpha.com/input?i=LCM%40%40Table[i%2C{i%2C1%2C17}]
ところで、こういうのもあるのか https://www.wolframcloud.com/
POSTLLM
問題文長い・・・
昇順に連続 M 個だけ考えれば良い
詰めることで期待値を減らせる
同じ値があるときの数え上げがやや面倒(この要素要る?)
期待値の式を整理
$ \sum (d_{i+1}-d_i)*i*(M-i) みたいな式になる(これの2倍かも)
展開すると $ 2(\sum d_i*i) - (M-1)(\sum d_i) みたいになって簡単にスライドできる
上の式のままやってる人twitterで複数観測した。はえー。
たしかに差分列と係数を畳み込めばいいね。そっちの方が手っ取り早いかも?
TERMIN
AC数逆転してた。たしかに最難はこっちだと思う。
累積和にしておくと見通しが良くなる。
頂点に 0,1,2 が書かれた N+1 頂点のグラフで l から r までのパスを作る、みたいに捉える。
辞書順最小化:
$ S_r = 0 なら r に直接飛んで "0" にするのが最小
そうでないなら前から貪欲
($ S_r と同じ値の頂点に到着したら終わりとして良い)
今の頂点と同じ値が書いてある頂点のうち最も近い頂点に飛ぶ
ないなら、+1 のうち最も近いもの
ないなら、+2 のうち最も近いもの
適当にdpできる。
MNMXPRPAR
B をソートしておく。
S の min と T の max の index を si,ti とする。
数えるべきもの:
$ si \lt tiについての$ B_{si}B_{ti}2^{ti-si-1}
$ si = ti+1についての$ B_{si}B_{ti}
クエリ先読みして座圧しておいて、segtreeに乗せる。
以下、簡単枠
WAPEN
1問目ってこんな簡単なんだ。
COOLSUB
よくわからんギャグ、英文読解コンテスト
MINOVER
貪欲に前から。末尾だけ置き換えるかどうかを両方試した。
INTROVERTS
問題の内容に対して問題文が複雑。最初の人以外はSecondary Goal関係ない。
なんとなく全問題について書いてしまった。まあいいか。
#codechef #コンテスト #競プロ