チーム練(2012 UTPC)

チーム練

こどふぉが壊れてたのでAtCoder上の5時間セット

A (Md, 8:04)
B (Md, 11:40)
C (Md, 58:57)
D (Md, 151:20)
E (番兵, 191:31+3)
F2点 (番兵, 259:52)
H (のん, 113:43+2)
J (Md, 277:55+2)
の7完+2点

A
hai

B
うしろから

C
n*(n-1) - m > n-1かどうかで分けると閉路があるかどうかチェックするべきクエリの数は意外と少ない

D
同じ変換を繰り返すと不動点に収束する

EH
気づいたら通ってた

J
釣り上げるのが得な場合は必ず無限大なので容量で制約をつけるとフローに落ちる

チーム練(2018 nakhon pathom)

チーム練

8完。悪くはないけど後一問通したかった

D(Md, 00:19)
G(番兵, 00:58)
C(Md, 01:29)
H(のん, 01:43)
E(Md, 02:26)
K(のん, 03:05)
J(Md, 03:31)
F(のん, 04:26)

全体的にTLが厳しかった
Jを通した後は、Aを詰めたら解けるけど実装クソ重いしキューが詰まってるからやることがないなあとなってデバッグを手伝ったりしてた
ノーペナで通せた問題がCしかない...

軽く解説
A
柱が高い順に見ると木が生やせて、木のパス長をLCA使ってlogで答える問題に落ちる。
同じ高さの柱をどう扱うべきかあんまりわかってない

B
わからん

C
遷移出来るところに辺を生やすとDAGができる
最大長のパスをDP

D
貪欲

E
ソートしておいて
dp[i][j][k]: i番目までみてj回変更して、i番目の要素に+(k-1)したときの最大長

F
ゆきのんが実験したらフラクタルが生えた　すごい

G
SCC

H
CRT

I
わからん

J
各項を10^-15で割るとx^(1/3)の微分になるので、微分を足してから10^-15を掛ける
出力だるすぎる

K
endlforces
詳しくは知らないけどセグ木にのせてセグ木上のにぶたんを使いつついい感じに管理するっぽい

L
TLが鬼
線形でdp出来るけど実は普通に1辺の長さをにぶたんしたほうが早い？
二次元累積和を作っておいてにぶたんで解ける
（追記: 入力が遅かったらしい　ただそれでもTLはカツカツ。どうして.....）

チーム練 (2019 Asia Taipei-Hsinchu Regional)

チーム練

Discordを使ってオンラインチーム練
2019 台北 - Google スプレッドシート

まず適当にわかれて問題を読む。
Aが全探索するだけっぽいので自分が書き始めるが、メモ化などを忘れてTLE。
ゆきのんがJを解けそうとのことなので書いてもらう AC(0:59)
読んでなかったCとDがめちゃくちゃ簡単なことに気づき自分がAC(01:05, 01:10)
ゆきのんがKを誤読してたらしく、簡単な問題になったので書いてAC(01:29)
番兵がHのいい感じ探索を思いついてAC(02:01)
詰まっていたAを、メモ化したりmapからvectorに変えたりしてなんとかAC(03:04)
番兵がEをAC(03:52)
ゆきのんと話をしてLがいい感じにしゃくとり出来そうということになったのでゆきのんが書くが通らず。

7完。本番のスコアボードを見ると台北のレベルがめちゃくちゃ高くて震えた
精進します

チーム練 (2018 Jakarta)

チーム練

https://codeforces.com/gym/270601

ゆきのんと二人で。
めちゃくちゃ久しぶりに5時間セットをやったらかなり失敗した...

まず二人がかりで問題を全部読む。
ゆきのんがI解けると言ってたので任せる、AC(0:26)

DやKを考えるが解けない
Aを考えていたら解けたので投げる。AC(1:34)

ゆきのんがLの解法を思いつく。聞いたら正しそうなので任せる、がWAがいっぱい生える。
自分も同じ方針で書いてみるがWA
かなり詰まっていそうなので自分はGを、ゆきのんはDを考える。
ゆきのんがDをAC(2:53)

Gが一生解けないのでJを見たら制約にDPと書いていた
実装してAC(3:26)
直後に、Lのミスを発見していたゆきのんがAC(3:29)
Gで二分探索したら間に合うはずが無いと思い込み、貪欲を書くがWA

5完はしぶい。 帰ってからGを考えたらkが決まっている時の方法が少し高速化できることに気づく。 書いたらACした

最初にすべての問題に目を通す方針、どうなんだろう。

ABC125C - GCD on Blackboard

C - GCD on Blackboard

Problem summary

There is N numbers A_1, A_2, \ldots , A_n.
You can change a number between 1 and 10^9 or do nothing.
Calculate maximum GCD of N numbers after rewriting.

Constraints

・Time limit: 2 sec
・Memory limit: 1024 MB
・Each input is an integer number.
・ 2 \leq N \leq 10^5
・ 1 \leq A_i \leq 10^9

Answer

You should calculate maximum GCD of N-1 numbers which have N choices.

blute-force

You can remove A_i ( 1 \leq i \leq N) and simulate. This solution is O(N^2)

optimize

Prepare two sequences l and r such that
l[i] = GCD(A_1, A_2, \ldots, A_i)
r[i] = GCD(A_n, A_{n-1}, \ldots, A_i)
and calculate
MAX(MAX_{i=2}^{n-1}{(GCD(l[i-1], r[i+1]))}, l[n-1], r[2]).
This solution takes O(N)

ABC141C Attack Survival

C - Attack Survival

Problem summary

You have an integer vector v whose length is N and whose initial element is K.
Now we have Q queries for updating v.
In query q_i ( 1 \le i \le Q), you give an integer A_i and should decrement all other elements without A_i-th element of v (1-indexed). After executing Q queries, determine whether each elements are larger than 0 or not and print the result.

Constraints

・Time Limit: 2sec
・Memory Limit: 1024MB
・All values in input are integers
・ 2 \le N \le 10^5
・ 1 \le K \le 10^9
・ 1 \le Q \le 10^5
・ 1 \le A_i \le N (1 \le i \le Q)

Answer

blute-force

We simulate each queries in a row.
this takes O(N) per query so entire solution is O(NQ).

optimized

The answer is not depend on the order of queries so we can think only how many times i-th element of v is decremented ( 1 \le i \le N). the result of i-th element of v is (k - q + cnt[i] > 0 ? "Yes" : "No")
This takes O(N + Q) and It's satisfy the time limit.