なかけんの競プロノート
🕒 2020/10/18 🔄 2021/06/14

ABC180感想戦

🐶

AtCoder Beginner Contest 180に参加しました。

A - boxは、N-A+Bでいいとして、B - Various distancesで1WA（提出 #17441824）をやってしまいました。しかも、すぐに原因がわからなかった。。。ユークリッド距離の計算誤差が原因だろうなと思ったけど、どう書きなおせばいいかわからなくてCへ。

C - Cream puffは、ただの約数列挙。 $\\sqrt{N}$ までやればよくて、順番に表示したいのと重複したくないことから、setを使う。たぶん、昔だと $\\sqrt{N}$ のところで場合分けをしてそう。

Bに戻って、ぜんぶ double で受け取っていたのを、long long で受け取るようにして、ルートの計算のところではじめてdoubleを使うようにしました。これで通りました。このときはなぜこれで通ってたのか、なぜはじめので通ってなかったのがよくわかってなかったですけど、今よく考えれば、大きい数をdoubleで答えたら、1つ目の距離が1e+08みたいな表記になってしまうからダメだったんだな、とわかりました。

で、D - Takahashi Unevolvedです。

はじめは、まぁA倍を使えるのは100回くらいだから、それぞれカウントしていけばいいんじゃないかって思って、YをAで割りながら、Bを何回足せるかを数えればいい、と安直に思っていました。で、サンプルが通らずに、よく考えたんだけど、順番逆だなこれ。

上側はさまよってるけど、左下側でようやく正しい結論にたどり着く。A倍してからBを足すのと、Bを足してからA倍するのとだと、後者の方がすぐにでかくなるので、Bを足すのは後でやったほうがいい、と考え直す。XをA倍していきながら、Bを何回足せるかをカウントしていけばいい。オーバーフローに注意して（右下側）、提出。そして、1WA（提出 #17462057）、かなしい。

これ通せないのは順位的にかなりヤバいそう、と思いながらよく見てみると、XをA倍したときに、オーバーフローしてないかのチェックはいれてたけど、Y以上になっていないかのチェックが入ってない。オーバーフローに意識が行き過ぎていた。修正してAC（提出 #17462472）。

コンテスト中、掛け算をしたときにオーバーフローをしてないことをチェックするの、どうすればいいんだっけ？　となってたんですよね。解説にある

while((double)a*x<=2e18 && a*x<=x+b && a*x<y){

はわかりやすい。doubleに変換してからlong long に収まるかをチェックするのか、なるほど。

この時点で40分経過していて、あとは1時間でEができればうれしいなと思って、E - Traveling Salesman among Aerial Citiesへ。

巡回セールスマン問題だけど、距離が変なので、この距離について考える。サンプル2を見ると、途中で1に戻るのもありなのがネックで、こうなると、どういう巡回になるんだ？　という気持ちに。

右側で、1⇒2⇒3⇒1と、1⇒2⇒1⇒3⇒1の比較を式で書いてみると、たしかに右側も最小。Z方向は、上への移動距離だけをカウントすることなんだな、ということに気づく。左側で、2次元の場合に、下への移動距離を無視したらどうなるかなと考えると、なんだか1に戻ってくるのは効率が悪そうな気がする。なるほど、これは罠だ、1に戻ってくるのは実は考えなくてもいいパターンじゃないか？　という気持ちになる。

解説を読むと、この考えはあってるんだけど、三角不等式が成り立つからか、たしかに。上への移動距離ということは、「上上」「下下」の移動は寄り道しても変わらず、「上下」「下上」の移動は寄り道すると距離が増えるので、寄り道していいことはおこらない。だから、1に戻ってくるのは考えなくていいんだな。

じゃあこれ、距離は変だけど、普通の巡回セールスマン問題として解けばいいんだな、と思ったものの、書いたことがなかったのでググる。

【競プロ】bitDP入門(緑・水コーダー向け) - Qiita

この記事を参考に書く（今見たら、「ミスがあってので修正中」になっている・・・）。まぁそういうことで、書いたもののサンプルも通らず、どこが悪いんだろうと格闘してるうちに時間制限です。記念に出してはみた。提出 #17477921

終了後、他の人のコードを見て、何がダメだったかがわかる。「状態とそれを達成した場所」を保持していたけど、「状態と今いる場所」を保持しないとダメだな。例えば、1⇒2⇒3が最短だったとしても、4に行くときは1⇒3⇒2⇒4のほうが短いかもしれないので。1,2,3を巡回した状態に今いる場所がそれぞれある必要があって、それがないならこうしたチェックができない。

  dp[1][0] = 0;
  for (ll i = 0; i < MAX; i++) {
    for (ll j = 0; j < N; j++) {
      if (dp[i][j] == INF) continue;
      for (ll k = 0; k < N; k++) {
        if (1 & (i>>k)) continue;
        dp[i|1<<k][k] = min(dp[i|1<<k][k], dp[i][j] + cost[j][k]);
      }
    }
  }

巡回したものをbitで管理して、今いる場所も管理する。はじめは、スタート地点に距離0でいる、を格納。各状態に対して、今jにいるとして、まだkに行っていないなら、kに移動するための距離を更新していく。こうして順番に更新していけば、最終的に、すべての点を巡回したときのコストが、最終地点別に求まる。

  ll ans = INF;
  for (ll i = 0; i < N; i++) {
    ans = min(ans, dp[MAX - 1][i] + cost[i][0]);
  }

最後にスタートに戻るのも考慮して完成。

結果、41分2WAです、悲しい。下げが止まらない。