けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

配列再利用

Codeforces Round #584 - Dasha Code Championship E. Rotate Columns (R2400)

すんごく横長な行列に関する問題だけど、実は横の長さを縦の長さ以下にできるというタイプ。 そうすれば の問題に帰着できて、。あとは の bit DP...なのだが、TLE がとれなかった。微妙に詰めが甘かった。。。 問題へのリンク 問題概要 の行列があたえられ…

AtCoder AGC 033 D - Complexity (1000 点)

これを解けなかったのが強い敗北感。 DP 配列が巨大になりそうなときに、最適化する対象を入れ替えるテクは今までなんども見ているのにそれが思いつかない思考の硬さを思い知らされた。 問題へのリンク 問題概要 0 と 1 のみからなる行列の複雑度を すべて同…

AOJ 2370 RabbitWalking (AOJ-ICPC 600 点)

これを解いていたおかげで ARC 099 E - Independence がすぐに思いつけた感はあるかも。むしろ制約的に ARC 099 E の完全上位互換だと言える。 問題へのリンク 問題概要 頂点 辺の無向単純グラフが与えられる。 このグラフが「奇数長のサイクルがない」とい…