ARMERIA

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

AOJ

Ritsumeikan University Programming Contest 2013 (AOJ 2507) Computer Onesan

お題箱より。 Aizu Online Judge 解法 実は過去の解説記事に類題があります。 Educational Codeforces Round 17 D. Maximum path - ARMERIA Codeforcesの問題は最大化でAOJの問題は数え上げという違いはありますが、解法はほぼ同じです。 左上から右下に向か…

Waseda University Programming Contest 2020 E: LCM Count (AOJ 3155)

お題箱より。 Aizu Online Judge 解法 最小公倍数や最大公約数は、素因数ごとに「重複度の最大値/最小値」を取るという観点で捉えると考えやすくなることがあります。 の最小公倍数(LCM)は、全ての素数 について各要素における の重複度の最大値 を求め、 …

University of Aizu Programming Contest 2014 (AOJ 1548) Yu-kun Likes a Directed Graph

お題箱より。 Aizu Online Judge 解法 重み の負辺を足してできるだけ重み合計が大きい( に近い)負閉路を作りたいので、与えられたDAGについて「1本以上の辺で構成されるパスであって、重み合計が 未満であるもののうち一番大きいものの重み」が分かれば良…

University of Aizu Programming Contest 2012(AOJ 1508)RMQ

お題箱より。 Aizu Online Judge 解法 1点更新と区間最小値取得ならセグメント木でできますが、シフト操作が厄介です。シフト操作は「数列から要素を1つ削除する」「その要素を数列の別の場所に挿入する」とみなすことができますが、この操作によって間に存…

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

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

KUPC2020Spring F ボタンの木

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

HUPC2019 Day1 D: 貪欲が最適?

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