今日の競プロ(2020/4/17)

JOI 1問

Codeforces 6問

JOI2008春合宿 Day3 Fraction: 分数

問題

解説AC。ファレイ数列っていうらしい。

提出

Codeforces Round #632 (Div. 2) E - Road to 1600

問題

結構きれいにいけた。基本的には蛇腹に埋めて、左下(or 右下)の4マスだけ適切に入れ替える。 $n=5$ だと

f:id:gyouzasushi:20200417203924p:plain

みたいな。ルークは 19 → 22 → 20 → 21 → 23 → 24… と $0$ vun で動ける。一方クイーンは 19 → 20 → 21 → 23 → 22 → 24…と動くことになり、22 → 24 のワープに $1$ vun かかる。 $n=1,2,3$ は例外。

提出

Codeforces Round #615 (Div. 3) A - Collecting Coins

問題

提出

Codeforces Round #615 (Div. 3) B - Collecting Packages

問題

なんかめっちゃ詰まっちゃった。( x座標, y座標 )の pair をソート。

提出

Codeforces Round #615 (Div. 3) C - Product of Three Numbers

問題

素因数分解する。

提出

Codeforces Round #615 (Div. 3) D - MEX maximizing

問題

$cnt_i$ を $y_1,y_2,...,y_{j-1}$ のうち $x$ で割った余りが $i$ となるものの個数とする。 $y_j$ を追加するかわりに $cnt_{y_j\%x}*x+y_j\%x$ を追加することにすると、クエリごとに MEX を求めていくだけの問題になる。例えば $x=3$ のもとで