新年度になりました

今年は花粉大丈夫かもしれない。

2024/4/3

ゲームフリーク Programming Contest 2023

atcoder.jp

問題

N個の点とM個の無向辺がある。辺iは点A_iと点B_iを結び、長さはC_iである。
任意の点から始めて、同じ点を通らずに別の点へ移る時の最長経路を求めよ。

制約

  • 2\le N\le 10
  • 1\le M\le\frac{N(N-1)}{2}

方針

DFS。計算量はO(NN!)。10!=3628800。

int n, m;
cin >> n >> m;
vector<vector<int>> g(n, vector<int>(n, -1));
for (int i = 0; i < n; i++){
  int a, b, c;
  cin >> a >> b >> c;
  --a; --b;
  g[a][b] = g[b][a] = c;
}
vector<int> p(n);  //1
iota(p.begin(), p.end(), 0);  //1
int ans = 0;
do {
  int sum = 0;
  for (int i = 0; i < n - 1; i++){
    if (g[p[i]][p[i + 1]] == -1) break;
    sum += g[p[i]][p[i + 1]];
  }
  ans = max(ans, sum);
} while (next_permutation(p.begin(), p.end()));  //2
cout << ans << endl;
return 0;

ポイント

2でnext_permutationを使うために、1で要素が昇順にソート済みである配列を用意している。

最近の購入品

  • 革靴
    [テクシーリュクス] ビジネスシューズ アシックス商事 本革 TU-7032 ブラック 26.5cm
    革靴。通勤用のものが磨り減っていたので購入。歩きやすい。8999円。
  • Kindle本
  • 折りたたみ傘
    日本製 ミラトーレ 折り 60cm 10本骨 小宮商店
    中学生の頃から使っていたものが壊れかけていたので購入。骨がしっかりしている。14300円。
  • Yシャツ
    [アオキ] 長袖白無地 形態安定シャツ メンズ 白(EALM4014) (3個)
    裄丈80cmを購入したがもう少し長い方がよさそう。3個で10533円。
  • ゴミ箱
    アスベル フタ付きゴミ箱 45L 白 A6324 (2個)
    キッチン用に購入。2個で5160円。

限られた時間

AtCoder Problemsの問題を解くことに多くの時間を費やしているので、なかなか本を読む時間がない。睡眠時間を削っても大丈夫なスーパーマンではないし、仕方ないね。健康第一。