競技プログラミング

問題 解法 左から順にドミノの並びを見ていく場合、並び方は ・縦に1つ置く ・横に2つ重ねる の2パターンです。 そこで、直前の並びに対する次の並びでの塗り方のパターンを考えます。 ・「...

問題 解法 長方形の辺の候補となるのは2本以上存在する棒です。また、4本以上存在すれば正方形にすることが出来ます（正方形は長方形に含まれる） 　よって、同じ棒が2本現れる毎に辺の候補に追加し、その中から1番...

問題 解法 xからKを経由してyに行く最短経路は、xからKへの最短経路とKからyへの最短経路の和になるので、 事前にKから各点への最短経路を求めておけば良い。 最短経路は、対象が閉路の無い木構造なので、幅...

問題 解法 寿司の数が105なので、O(N)であれば間にいそう。ということで、まずは全探索で考えてみる。 考えられるパターンは以下の4ケースに分けられる。 ケース1：時計回りに何個か寿司を食べてそのま...

いよいよ水色が目前と言うことで、気合いを入れて臨んだのですが、逆に空回りしてしまったのか、Ｃで詰まって爆死しました。 ちょっと反省ですね。 A - Programming Education 問題 解...

問題 解法 長さNの数列の切れ目はN-1通りあるため、3つの切れ目を選ぶ組み合わせはn-1C3通りあります。Nは最大2x105であるため、全ての組み合わせを試すのは現実的ではありません。 「P、Q、R、Sの...

問題 解法 以下の数式の値を最小にするbをどのようにして求めるかという問題です。 $$ abs(A_1-(b+1)) + abs(A_2-(b+1)) + ... + abs(A_N-(b+1)) $$...