gyouzasushi’s diary

競プロとか

今日の競プロ(2020/4/8) + Codeforces Round #632 (Div. 2)

JOI 8問

Codeforces 4問 rating : 1900→1940 (+40)

JOI2014本選 A - JOI紋章（JOI Emblem）

縦2 $2$ 行、横2列の領域は全部で $(H-1)\times(W-1)$ 個あるが、そのうち変更の影響を受けるのは高々4つ。よって、どの箇所をどの文字に変更するか全通り試せる。

JOI2014本選 B - IOI饅頭（IOI Manju）

$k$ 個の饅頭を売るときの利益の最大値は、(饅頭を $k$ 個選んだときの饅頭の価格の最大値) $-$ (饅頭が $k$ 個以上詰められるように箱を選んだときの箱の価格の最小値)。前者は貪欲、後者はナップザックみたいなDPで求められる。これを $0\leq k\leq M$ で計算して最大値をとる。

JOI2016予選 D - JOI国のお散歩事情 (Walking in JOI Kingdom)

苦手系で絶対バグらせると思ったけど一発で通って嬉しい。解法を日本語で説明するのが難しい…。

JOI2016本選 A - オレンジの出荷 (Oranges)

「 $dp[i][j]=i$ 個目のオレンジまでみて、今使っている箱に $j$ 個のオレンジが入っているときのコストの最小値」でやったら地獄を見た。こういうのは練習して掴んでいくしかないな〜〜。

JOI2016本選 B - スタンプラリー２ (Collecting Stamps 2)

適切に前計算しておけば、新しく出店したときに 'J' 'O' 'I' の選び方がどれだけ増えるかは一瞬で求まる。

JOI2017本選 A - フェーン現象 (Foehn Phenomena)

いもす法のイメージそのまま。標高そのものは忘れて、隣り合う地点の標高差だけ覚えておけばいい。 $R_j=N$ のときに注意…。

JOI2019予選 D - 日本沈没 (Japan Sinks)

海面が上がっていく様子を絵を描いたらわかりやすかった。

適当に圧縮して $A_i \neq A_{i+1}$ としてよい。海面の高さが $A_i$ に到達したとき、

$A_{i-1} \gt A_i \lt A_{i+1}$ なら島の数が $1$ 増える
$A_{i-1} \lt A_i \gt A_{i+1}$ なら島の数が $1$ 減る

JOI2020本選 A - 長いだけのネクタイ (Just Long Neckties)

はじめに付けているネクタイが長い人ほど長いネクタイを、短い人ほど短いネクタイを試着してもらう。

Codeforces Round #632 (Div. 2) A - Little Artem

市松模様に塗る。 $n\times m$ が偶数のときは 'W' を一マス選んで 'B' にすればOK。

Codeforces Round #632 (Div. 2) B - Kind Anton

$b_i \gt a_i$ のとき

$a_1, a_2,\ldots,a_{i-1}$ の中に $-1$ があればOK。

$b_i \lt a_i$ のとき

$a_1, a_2,\ldots,a_{i-1}$ の中に $1$ があればOK。

Codeforces Round #632 (Div. 2) C - Eugene and an array

Zero-Sum Rangesの要領で累積和を考える。数列 $s$ を $s_0=0,s_i=a_1+a_2+\ldots+a_i$ とすると、 $a$ のsubarray $a_l,a_{l+1},\ldots,a_r$ の和は $s_r-s_{l-1}$ と表せる。つまり $a_l+a_{l+1}+\ldots+a_r=0$ は $s_r=s_{l-1}$ と言い換えられ、求めるべきは $s$ のsubarrayのうち同じ値を含まないものの個数。これは尺取り法でできる。

Codeforces Round #632 (Div. 2) D - Challenges in school №41

"RL"と並んでいる子どもを入れ替えて"LR"にする
最終状態は LL...LLRR...RR

これと同じ感じでやる。73分かけてもうて反省…。

コメント

f:id:gyouzasushi:20200408210125p:plain

JOI難易度6埋まりました。次は7頑張る〜〜