典型的な二部マッチングの問題です。 問題へのリンク 問題概要 枚の赤いカードと、 枚の青いカードとの間でマッチングを作っていきます。 各カードには整数値が書かれていて、最大公約数が 1 より大きいカード同士をペアにすることができます。 最大マッチン…

AOJ 1163 カードゲーム (ICPC 国内予選 2009 E) (400 点)

グラフの最小全域木の構造に関する理解を問う良問ですね。 問題へのリンク (AOJ) 問題へのリンク 2 (AtCoder) editorials 問題概要 連結な重み付き無向グラフ が与えられます (頂点数 、辺数 )。 の全域木のうち、全域木に含まれる 本の辺の重みのメディアン…

AOJ 2536 Median Tree (JAG 模擬地区 2012 C) (400 点)

BNF が書かれているので、LL(1)文法を再帰降下とかするのが標準みたいだけど、ad-hoc にスタックでなんとかしてしまった 問題へのリンク 問題概要 以下の BNF によって定義された文字列が与えられる。 <Cipher> ::= <String> | <Cipher><String> <String> ::= <Letter> | '['<Cipher>']' <Letter> ::= '+'<Letter> | '-'<Letter> | 'A' | 'B' |</letter></letter></letter></cipher></letter></string></string></cipher></string></cipher>…

AOJ 2584 壊れた暗号生成器 (ICPC 模擬国内 2014 C) (400 点)

LCA ライブラリを持っていれば書くだけ！ 問題へのリンク editorial 問題概要 頂点の根付き木が与えられる (根は頂点 0)。この木上で幅優先探索を行う (隣接する頂点のうち、頂点番号が小さい順にキューに push する)。 このとき、探索順序が であったとした…

AOJ 2677 Breadth-First Search by Foxpower (JAG 春コン 2014 A) (400 点)

このブログの「区間 DP」タグを充実させたい。この問題は本当に典型的な区間 DP なのでちょうどいい！！！ 問題へのリンク 問題概要 長さ の整数数列 が与えられる。これらに対して以下の操作を好きな順序で好きな回数だけ行う。 値の差が 1 以下であるよう…

AOJ 1611 ダルマ落とし (ICPC 国内予選 2016 D) (400 点)

最小包含円と似て異なる問題。 問題へのリンク 問題概要 二次元平面上に 個の点がある。 半径 1 の円を上手に配置したときに、その中に含めることにできる点の個数の最大値を求めよ。 制約 考えたこと 「 点のうち 2 点を通る半径 1 の円」に探索候補を絞っ…

AOJ 1132 Circle and Points (ICPC 国内予選 2004 D) (450 点)

面積二等分系問題、こないだ ICPC アジア 2019 にも出ていた。そっちは超むずいけど、こっちは簡単。 問題へのリンク 問題概要 頂点の凸多角形が与えられる。以下の条件を満たす点 P を求めよ: P を通る任意の直線によって、凸多角形は面積の等しい 2 つの凸…

AOJ 2442 Convex Cut (JAG 夏合宿 2012 day3b-C) (400 点)

コピペできる環境だったからライブラリで殴ったけど、ICPC 環境だったらタイピング量を減らす工夫せなアカンかな... 問題へのリンク 問題概要 下図のような、五角星 個があって、 個目の五角星から 個めの五角星までの最短距離を求めよ。 制約 考えたこと 五…

AOJ 2402 天の川 (ICPC 模擬国内 2012 D) (400 点)

えーーーーー、つらいけどむずかしくはなく、でもつらいん... 崖登り 問題概要 (略) 基本的にはグリッド上を移動していく最短路問題だけど、色々制約が付随している 考えたこと 一目見て Dijkstra 法が使えるとわかるけど、面倒... ポイントになりそうなのは…

AOJ 1150 崖登り (ICPC 国内予選 2007 D) (400 点)