gyouzasushi’s diary

競プロとか

今日の競プロ(2020/4/13) + Codeforces Round #634 (Div. 3)

AtCoder 1問
Codeforces 6問

ABC162 F - Select Half

解説AC。
「 $dp[i][j]=i$ 番目までからどの2箇所も連続しないように $j$ 個選んだときの総和の最大値」をする。これだと $O(N^2)$ かかるように思えるが、実際に $j$ として考えるべき値は $\lfloor \frac{i}{2} \rfloor - 1,\lfloor \frac{i}{2} \rfloor,\lfloor \frac{i}{2} \rfloor+1$ の高々3通りだけなので間に合う。
考えなきゃダメな遷移が実はとても少ないみたいなやつ、昨日解けなかったこれと全く同じ思考回路や…。これでさすがに身についたと思いたい。

Codeforces Round #633 (Div. 1) C - Perfect Triples

実験！
f:id:gyouzasushi:20200413202842p:plain
最初の方をビット表記してみる。
f:id:gyouzasushi:20200413205137p:plain
いえーーい

Codeforces Round #634 (Div. 3) A - Candies and Two Sisters

Codeforces Round #634 (Div. 3) B - Construct the String

Codeforces Round #634 (Div. 3) C - Two Teams Composing

二分探索した。

Codeforces Round #634 (Div. 3) D - Anti-Sudoku

違う行・違う列・違う正方形に属するマスを9個選んで書かれている数字を変える。

E2 - Three Blocks Palindrome (hard version)

f:id:gyouzasushi:20200414015522p:plain

$a$ として使う数字

左の $a$ の右端のindex $l$ 、右の $a$ の左端のindex $r$

を固定すると、区間 $(l,r)$ に最も多く登場する数字を $b$ として使うのが最適。

コメント

DeepL翻訳使ってみた。めっちゃ読みやすかったので次から初手翻訳でいきます。