脳log[20211216]

2021年12月16日 (木) [AtCoder] JOI 2021/2022 二次予選 過去問から精進２問。■C 問題「国土分割 (Land Division)」。すること自体は難しくない。目指すべき状態を作ることも判定することも簡単にできる。だから仕切り方を全探索して数えるのは簡単にできるはず。それでは時間が足りないから効率がいいように手続きを組み立てるわけだけど、実装するのにすごく迷った。関数を抽出して処理がまとめられそうでまとめられなくて、でもやっぱりまとめたくてできなくて。提出 #27909751 (100 点 / 566 Byte / 69 ms)。結局抽出できたのは I 関数のみで、メインの処理は似た構造を重ねた二重ループのままになった。■E 問題「交易計画 (Trade Plan)」。制約上限が頂点数、辺数、クエリ数すべてで 40 万なので、判定はほぼ定数時間で行わなければいけない。UnionFind をうまく使うだけ。提出 #27932262 (100 点 / 727 Byte / 2581 ms)。もちろん一度は間違えた>WA。最初からうまくはできない。■飛ばされた D 問題「飴 2 (Candies 2)」。解けないんだよなあ。DP で間違いないと思うんだけど。単体の数と２数の和の２種類の数があって、２数の和から単体の数(と見なせる状態)への遷移があって、そういうのを整理しながら数列をスキャンしていって最大値を答えるんだと思うんだけど、答えにたどりつかない。