2019-02-16から1日間の記事一覧
教育的!!! 問題へのリンク 問題概要 個の正の整数 が与えられる。今、以下の操作を好きな回数だけ行う。 個から 2 つの正の整数 () を選んで、 を で置き換える この操作を行うと、最終的には 個の と 1 個の正の整数が残る。残る整数の最小値を求めよ。 …
文字列を値にもつ DP、ご無沙汰!!! 問題へのリンク 問題概要 本のマッチ棒を使ってできるだけ大きな数値を作りたい。 マッチ棒で 1, 2, 3, 4, 5, 6, 7, 8, 9 を作るのにそれぞれ 2, 5, 5, 4, 5, 6, 3, 7, 6 本のマッチ棒が必要である。 ただし各桁に用い…
教育的典型題 問題へのリンク 問題概要 カッコ列が与えられる。カッコ列に最小個数の '(' と ')' を挿入して「整合のとれたカッコ列」にせよ。またそのようなものが複数通り考えられる場合には、辞書順最小のものを求めよ。 制約 考えたこと 超定番。 AtCode…
Bellman-Ford 法を活用する典型問題ですが、少し注意が必要な問題ですね。 問題へのリンク 問題概要 頂点 辺の重み付き有向グラフが与えられます。 頂点 から頂点 へと至る最長路の長さを求めてください。 ただし、いくらでも長い路が存在する場合は inf と…
これは単に二項係数知っているかを問う感じ...? この頃と今とでは、多少問題傾向も違う気がする。 問題へのリンク 問題概要 個の数値が与えられる。このうち 個以上 個以下を選ぶときのその平均値の最大値を求めよ。 また最大を達成する選び方が何通りある…