Codeforces Round #627 (Div. 3)
Codeforces Round #627 (Div. 3)に参加しました。
- A - Yet Another Tetris Problem
- Yet Another Palindrome Problem
- C - Frog Jumps
- D - Pair of Topics
- E - Sleeping Schedule
- 参考
A - Yet Another Tetris Problem
問題概要
デフォの盤面に2 * 1のテトリスを積んでいき全部消せるかどうか
解説
偶奇を見るだけです。
提出
Yet Another Palindrome Problem
問題概要
部分列に回分があるか判定
解説
1 1 1のケースを見逃していました（なんで・・・）
提出
C - Frog Jumps
問題概要
カエルがRLの指示に従って飛びます。
解説
0 ~ N+1にいきたいんですが、サンプルからエスパーするとLの長さの最大値+1だといいです。
提出
D - Pair of Topics
問題概要
i < jでa_i + a_j > b_i + b_jとなるi,jの組みを探す問題。
解説
iとjが別れてると評価しにくいので a_i - b_i > - (a_j - b_j) という形にして処理します。 あるiについてa_i - b_iを見て、マイナスの配列でそれ未満の数がいくつあるかを数えればよい。元の数が+の場合は絶対に自分が入るので、-1しておく。最後に半分にする。これ握手とかのやつで見たな。
提出
E - Sleeping Schedule
問題概要
N回寝る意思決定をする人がいます。i回目の意思決定では起きてからa_i or a_i - 1時間後に寝ることを選択できます。l <= x <=r 時に寝始められた日はgood dayです。1日の時間をH時間とし、H時間寝るとして、適切に意思決定をしたときのgood dayの回数の最大値を求めてください。
解説
DPやるだけ。 dp[i][j]: i回意思決定後のj時に起きたときのgood daysの最大値。
