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

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

TSP

AtCoder ABC 183 C - Travel (灰色, 300 点)

C++ なら next_permutation() を使うことで 通りの全探索ができる! 問題へのリンク 問題概要 個の都市 がある。都市 と都市 とは距離が だけ離れている。 都市 から出発して各都市をちょうど一度ずつ訪問して都市 に戻ってくる方法のうち、その移動距離の総…

AtCoder ABC 180 E - Traveling Salesman among Aerial Cities (水色, 500 点)

TSP だ!! 問題へのリンク 問題概要 3 次元空間内に 個の都市、都市 1 から 都市 N がある。 座標 の都市から の都市に移動する際には のコストがかかる。 都市 1 からスタートし、全ての都市を 1 度以上巡って都市 1 に戻るまでの最小コストを求めよ。 制…

AOJ 3191 Watering (AUPC 2020 day3-G)

この問題に似てた drken1215.hatenablog.com 問題へのリンク editorial 問題概要 の順列 を最適化したい。以下の手順にしたがって、各要素 のスコアが定まる。この 個のスコアの最大値の最小値を求めよ。 値が のいずれかであるような数列 ( 項) が与えられ…

Educational Codeforces Round 74 E. Keyboard Purchase (R2200)

こういうのを素早く処理できるようになりたい 問題へのリンク 問題概要 長さ の 種類の文字からなる文字列 が与えられる。いま、 種類の文字の順列 として考えられる 通りの並びのうち最適なものを求めたい。 順列のスコアは、 上のすべての連続する 2 文字…

diverta 2019_2 F - Diverta City (銅色, 900 点)

冷静になれば自然な構成ではあるね...企業コンのラス問だと身構えてしまうのがよくない 問題へのリンク 問題概要 頂点からなる重みつき無向単純完全グラフであって、 通り考えられるハミルトンパスに対して始点と終点が同じものを同一視して得られる 通りの…

AtCoder ABC 073 D - joisino's travel (水色, 400 点)

Floyd-Warshall で前処理してどうのこうのする問題。特に ICPC 系などでよくある! 問題へのリンク 問題概要 頂点 辺の重み付き無向グラフが与えられる。このグラフ上で 個のチェックポイントをなす頂点集合が指定されている。好きなチェックポイントからス…

AOJ 2237 The Castle (JAG 夏合州 2010 day3-F) (500 点)

一目見て bitDP なのはわかるのだけど、手こずった...ウチ弱すぎるのん... 問題へのリンク 問題概要 匹の猫をステージ に順番に送り込む 猫 がステージ をクリアできる確率は 猫 がステージ をクリアしたら、次のステージ もその猫で挑まなければならない 猫…