けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AOJ-ICPC600点

AOJ 2293 Dangerous Tower (JAG 夏合宿 2011 day2-D) (600 点)

めっちゃ面白い問題! 問題へのリンク editorials 問題概要 個の直方体がある。 番目の直方体は の形をしている。 今、これらの直方体からいくつかを選んで積み木を作る。このとき、奥行き方法は必ず長さが になるようにする。 縦または横方向については、 …

AOJ 2594 Reverse a Road II (JAG 模擬地区 2014 F) (600 点)

ネットワークフローアルゴリズムの構造をちゃんと理解しているかを問う良問ですね!! 問題へのリンク editorials 問題概要 頂点数 、辺数 の有向グラフ と、2 頂点 が与えられます。 いま、グラフの辺を 1 本選んで向きを反転させます。それによって、- 間…

AOJ 2376 DisconnectedGame (JAG 冬合宿 2010 day3-H) (600 点)

こないだの ARC でめっちゃ似た問題が出たので!これは、SolveMe を含む、りんごさんによる伝説のセット。 drken1215.hatenablog.com 問題へのリンク 問題概要 頂点数 のグラフが与えられる (入力は の隣接行列で与えられ、初期状態では非連結である)。この…

AOJ 2439 箱根駅伝 (JAG 夏合宿 2012 day3a-F) (600 点)

sky さんの提唱した、代々伝わる名問題!!! 問題へのリンク 問題概要 人の選手が箱根駅伝を走っている。テレビの放送では中継所で各チームの通過順位と共に前の中継所からの順位変動が表示される。 ある中継所を 番目に通過したそれぞれの選手について、前…

AOJ 2171 Strange Couple (JAG 夏合宿 2009 day3-G) (600 点)

ランダムウォークな問題! 実数係数の連立方程式の練習に 問題へのリンク 問題概要 頂点の重み付き無向グラフが与えられる。ただし自己ループを含み得る (多重辺はない)。二頂点 が指定されていて、 から へとランダムウォークによって辿り着きたい。 ただし…

AOJ 2336 スプリング・タイル (JAG 夏合宿 2010 day2-G) (600 点)

グリッド系は苦手意識あるけど解けてよかった 問題へのリンク 問題概要 二次元マップが与えられて、各マスは 床 ('.') 壁 ('#') バネ ('*') の 3 つの属性がある。スタート ('s') とゴール ('g') が設定されていて、いずれも床属性である。 s から g へ最速…

AOJ 2370 RabbitWalking (JAG 冬合宿 2010 day3-B) (600 点)

これを解いていたおかげで ARC 099 E - Independence がすぐに思いつけた感はあるかも。むしろ制約的に ARC 099 E の完全上位互換だと言える。 問題へのリンク 問題概要 頂点 辺の無向単純グラフが与えられる。 このグラフが「奇数長のサイクルがない」とい…

AtCoder ARC 081 E - Don't Be a Subsequence (黄色, 600 点)

部分列 DP の考え方を試せる問題 問題へのリンク 問題概要 文字列 A が与えられる。 A の部分文字列とはならないような文字列 (英小文字のみ) のうち、最短の長さのものを求めよ。 複数考えられる場合にはそのうち辞書順最小のものを求めよ。 制約 1 <= |A| …