ARMERIA

Rubyと競技プログラミングの話 AtCoderやCodeforcesの問題解説記事が多め。

AOJ

パソコン甲子園2019本選 (AOJ 0426) 三角形の個数の和

お題箱より。 Aizu Online Judge 解いてなかったのでこのリクエストを見て解きました。 解法 言い換えを重ねる 全ての点の個数を と表記することにします。 「全ての点集合について、その集合に含まれる三角形を数えて合計する」を、「全ての三角形をなす3点…

KUPC2020Spring F ボタンの木

お題箱より。 Aizu Online Judge Arena 解法 公式解説と逆になってしまいますが、与えられる を改めて と定義します。これが正である頂点は「過剰なので減らす必要がある」、負である頂点は「不足しているので増やす必要がある」ことになり、全ての を にす…

HUPC2019 Day1 D: 貪欲が最適?

お題箱より。 Aizu Online Judge Arena 解法 答えとなる金額の払い方の必要条件を考える ある金額 について貪欲な払い方よりも真に枚数が少ない払い方が存在することを、単に「金額 は条件を満たす」と書くことにします。そして条件を満たす最小の金額(答え…