AtCoder Regular Contest 106 + Codeforces Round #678 (Div. 2)

(nは自然数) @n_vip

E冷静になればマージテクやるだけ（たいへん）なんだけど、冷静じゃなかったのでライブラリ探しを開始してしまってすごく時間ロスした

kmjp @kmjp_pc

Fはいつも通り約数包除と1乗和2乗和をガリガリやったらどうにかなったけど、Eはなんなんだ…あるMEXを満たす極小な区間って実はあんまりないとかそういうのかな。

kmjp @kmjp_pc

Fはsum_k(k*C(n,k))=n*2^(n-1)になるっての、Wikipedia見ながら利用した。

laycrs @laycrs

Codeforces Round 678 (Div. 2)． 途中でメモリバカ食いするプログラム書いて1回PC落ちた． A，全部正味1回ずつ足すので和がMかどうか調べる． B，各行各列に1を2個，その他は0にする． pic.twitter.com/Da8qURrEZd

拡大

拡大

laycrs @laycrs

C，答えが求まるようにプログラムをシミュる．その際，ここはX未満，ここはX以上という制約ができるので適当に階乗使って数え上げ． pic.twitter.com/vZx8VdmGll

拡大

laycrs @laycrs

D，各部分木に対して ceil(総人数/葉の数) を求めてその最大値． F，GCD=1要る？それは包除原理．後は丁寧な数え上げ． pic.twitter.com/FXEIulxHIQ

拡大

拡大

tsutaj @tsutaj

A: ギャグすぎない？総和しか関係ない B: 構築は、難しい・・・ (対角成分にいい感じのものをおいてあとは全部 1) C: シミュレーション的なことをする (操作は log 回なのでメモ化不要) D: (総和, 葉の数, 最大値) を持って DP

こたつがめ @kotatsugame_t

こどふぉ678 E：MEX=xなる区間が存在するか探す。 a_i=xなるiそれぞれに対し、そこから右にある一番近い値bのindex id_bを計算し、forall b<x [id_b<id_x]を判定すればよい。これは左から見ていくとRmQのセグ木でできる。 答えが1になる場合だけ注意

(nは自然数) @n_vip

Aよく見るとただの総和 B対角成分以外1 Cシミュレーションして条件を逆算 D各部分木について、ceil(人の総和 / 葉の数) のmax E x以下からなる極大な区間それぞれのmexを求める

こたつがめ @kotatsugame_t

RMQだった（Range min QueryではなくRange Max Query）

(nは自然数) @n_vip

Fみたいなのできないのこどふぉが苦手という気持ちになる

tsutaj @tsutaj

E、mex=x の判定の時に 1 から x-1 までが区間内に存在するかを高速に判定する方法がわからなかった

laycrs @laycrs

@n_vip あまり良く分かってないんですが，Eって 6 1 4 2 5 3 1 に対してうまく答えられます？

こたつがめ @kotatsugame_t

めぐる式二分探索以外は全部カス

kmjp @kmjp_pc

Bは右端と最下段を1以外にしたせいで、右下角も考えないといけなかったけど、対角線に1以外置けばよかったのか。

hirokazu @hirokazu1020

PASTをやる体力がない

(nは自然数) @n_vip

@laycrs st = {1,2,3,6,} 4 だそうです

(nは自然数) @n_vip

@laycrs だめじゃん

laycrs @laycrs

@n_vip ですよね…（答え5ですよね…

ゴジラ＠競プロ @gojira_kyopro

Aの「02_beet_killer」とかいうテストケース気になるな

(nは自然数) @n_vip

Eで貼ろうとしていたデータ構造なんですが、うまく動かなくて断念したので、誰かよろしくおねがいします codeforces.com/blog/entry/788…

てんぷら @tempura_cpp

02_beet_killerだけ落ちるコードを書けた人はちょっとすごい

(nは自然数) @n_vip

日本語の記事を検索しようとするとAtCoderの問題がヒットしてかなりウザい（まあその問題の方が古いんですが）

(nは自然数) @n_vip

まあwriterがね、自分なのでね、マジで文句を言う相手が居ないんですが

ヘクト🐬 @osrehun

ようやくWA解法がTLE解法に直して、バグを突き止められて心がスッキリした。なので、コードを捨てるか。