AOJ 2618

珍しく問題の解説を書いてみます

AOJ2618 Trip to Kyoto

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2618

問題概要

二次元平面上に道路が東西、南北に距離 の間隔で無数に走っていて、正方格子をなしています。

で東西の道路と南北の道路が交差しています。

人の座標 が与えられて、道路上を単位時間あたりに距離 だけ移動することができます。

全員が道路上のある 点に集合するとき、集合するためにかかる時間の最小値を求めてください。

解法 1

実はこの問題は、タイトルの Trip to Kyoto がネタバレになっていて、京都に旅行に行けば良いことが分かります。

行きました。普段写真は撮らないんですが、今回は頑張って撮ってみました。

部分点 1：移動

まず、移動を考えます。浜松駅から京都駅まで新幹線で 時間くらいかかります。事前に新幹線の時間を調べていましたが、バカだったので失敗しました。浜松　京都　新幹線でグーグル検索すると、最初に市役所から徒歩で駅まで移動するフェーズが加算されています（一敗）。早く着く分には待ってればいいのでWAではありません。

学割を使ったら往復で 円で が だったので気分が良くなりました（学割を適用した切符を得るために窓口に行く必要があり、社会性の要求で気分が悪くなった）。

部分点 2：宿泊

次に、宿泊を考えます。ホテル　やっっっっっっっっっす　駅前のホテルを予約して、二泊で 千円くらいでした。

寝るだけなので、とくにこだわっていません。

新しいホテルらしく、チェックインが自動化されていました。おじいさんなので機械の操作に手間取って15時間くらいかかりました。

部分点 3：食事

食事です。

day1 朝

おうちでパンを食べた　おいしいパンを作るパン屋さんになりたいです。

day1 昼

学会でありがちの昼食です（すみません、旅行ではなく学会参加です）。普段は1日2食（昼に起きるため）なので満腹になりました。

day1 夕食

居酒屋へ　写真を撮る気持ちの余裕がなかった

ビール3

バカなので翌日発表があるのに結構飲んでしまった　帰りに階段でREした

day1 夜食

昼に京都駅に着いて、目の前に豚まんが売られていたのでうっかり購入してしまいました。昼食として食べようとしましたが、支給されたので食べるタイミングを🐮ない困っちゃった

day2 朝食

バカの朝食　孤独な成人男性にありがち

day2 昼食

取り忘れましたが day1 の昼食とおなじです

day2 夕食

居酒屋へ　写真を撮る気持ちの余裕がなかった

再放送をやめよう

ビール3 ハイボール1

さすがに酔いました

帰ったらすぐ寝落ちした上に夜中に頭が痛くなり目が覚めた

day3 朝食

なんと、食べていません。孤独な成人男性にありがち2

day3 昼食

ご飯の上に乗っているのが牛肉なんですが、かなりおいしかったです。親近感をかんじる

day3 夕食

わりと量があって満腹になりました。

部分点4：観光

観光をします。京都には5万回来たことがありますが、改めてまわることにします。くるくる

清水寺

バスこみまくり

平日なのに1億人いてびっくりした　学生や海外の人が多いのか

京都駅

上に上がると展望できるところがある　展望デッキには誰もいませんでした　京都タワーが見えます　

鴨川

大きな川が流れていて、川沿いにくつろいでいる人が結構いました

水遊びをしている人はいません　みんなえらい

平安神宮

人はまばらでした　入り口にかなり大きい鳥居があります

中も広いです

京都大学

京都駅から清水寺を過ぎてもう少しバスに乗っていると京都大学に着きます

今日もまた、がぜるさんに会えませんでした

解法 2

当分の間、距離 間隔ではなく距離 間隔だと思って解くことにします。

とりあえず 度回転します。つまり と置いて、 について解きます。

回転後の単位時間あたりに、現在の座標を とすると （複号任意）に移動できることになります。

軸と 軸の移動（の部分）は独立に決めることができるので、軸を分離して一次元の問題として解いてもよいです（典型）。両方の答えを求めて、大きい方が答えです。

一次元の場合、座標の最大値-最小値を2で割った点に集合することが最適です。この値が奇数の場合 が生えるので、最初に全ての座標を 倍しておくと良いかもしれません。

では、距離 間隔の場合はどうでしょうか。

を で割って四捨五入します。つまり最初にあらかじめ近くの交差点まで移動することにします。交差点に移動後は、 に移動できると思って良いため、上の解法を使えば良いです。最初に近くの交差点に移動する部分が嘘なんですが、答えを考えたときにこの場合のロスは最大でも くらいです。したがって、上の解法で求めた点の周囲 くらいを見れば十分であることが分かり、その範囲にある点を全探索すればよいです。

点を決めた時の最短移動距離は、abs(x1-x2)+abs(y1-y2)ではないケースが限定されていることを利用した場合分けをすると求まります。

最初から解説を書くつもりはなかった（は？）ので、間違っていたらすみません

#include<bits/stdc++.h>

using namespace std;

int main() {
  int N;
  cin >> N;
  vector< int > X(N), Y(N), x(N), y(N);
  for(int i = 0; i < N; i++) {
    cin >> x[i] >> y[i];
    x[i] *= 2;
    y[i] *= 2;
    X[i] = x[i] + y[i];
    Y[i] = x[i] - y[i];
  }
  auto f = minmax_element(begin(X), end(X));
  auto g = minmax_element(begin(Y), end(Y));
  int mx = (*f.second + *f.first) / 2;
  int my = (*g.second + *g.first) / 2;
  int xx = (mx + my) / 2;
  int yy = (mx - my) / 2;
  int ret = 1e9;
  auto solve = [](int a, int b, int c, int d) {
    a += 2e8, b += 2e8, c += 2e8, d += 2e8;
    if(a % 20 == 0 and a == c) {
      return abs(b - d);
    }
    if(b % 20 == 0 and b == d) {
      return abs(a - c);
    }
    if(a % 20 == 0 and c % 20 == 0 and b / 20 == d / 20) {
      return abs(a - c) + min(b % 20 + d % 20, 40 - b % 20 - d % 20);
    }
    if(b % 20 == 0 and d % 20 == 0 and a / 20 == c / 20) {
      return abs(b - d) + min(a % 20 + c % 20, 40 - a % 20 - c % 20);
    }
    return abs(a - c) + abs(b - d);
  };
  for(int i = xx - 40; i <= xx + 40; i++) {
    for(int j = yy - 40; j <= yy + 40; j++) {
      if(i % 20 and j % 20) continue;
      int sub = 0;
      for(int k = 0; k < N; k++) {
        sub = max(sub, solve(i, j, x[k], y[k]));
      }
      ret = min(ret, sub);
    }
  }
  cout << fixed << setprecision(1) << ret * .5 << endl;
}

終わりに

そろそろ真面目な記事を書きたい