ABDの三完。Cを飛ばしたのは正解だったけど、Eを解き切れなかったのは良くない。
コンテスト後のツイート
D 二乗DP。1,2,...,nやn,n-1,...,1を除くことに注意。
— titia (@titia_til) December 19, 2022
E 完全グラフ（クリーク）同士を繋げるのだと思うけど解き終わらなかった。コンテスト後に、頂点2のグラフを二回使うケースを忘れていたことに気付いた。
C. Another Array Problem
同じ隣接2マスに二回操作を行うと両方とも0になることを利用すると、配列の長さが4以上なら全体を最大値にすることができる……と気付けるかどうか。
愚直を書けば気付けたかと思ったけど、愚直を書いたつもりで「同じところは二回やらない」みたいな実装にするとダメ。結構ハマりやすいかも。
E. Node Pairs
たくさんWAを出したけど一応自力でAC。
ツイートで方針はあっているけど、頂点数2だけでなく、もっと頂点数が多い完全グラフも複数回使うことがあるので、個数制限のないナップザック問題のようにして解けばOK。
最初、頂点数の多い完全グラフから貪欲に使っていけば良いのでは？ と考えたため、大体一回ずつしか使わないという考えから抜けられなかったのがまずかった。
0 件のコメント:
コメントを投稿