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翻訳使ってみた。めっちゃ読みやすかったので次から初手翻訳でいきます。