競プロ日記

問題
ACコード
WAコード(3打ルート作成)

#include <bits/stdc++.h>
#define GET_REP(_1, _2, _3, NAME, ...) NAME
#define rep(...) GET_REP(__VA_ARGS__, irep, _rep)(__VA_ARGS__)
#define rep1(...) GET_REP(__VA_ARGS__, irep1, _rep1)(__VA_ARGS__)
#define _rep(i, n) irep (i, 0, n)
#define _rep1(i, n) irep1(i, 1, n)
#define irep(i, a, n) for (int i = a; i < (int)(n); ++i)
#define irep1(i, a, n) for (int i = a; i <= (int)(n); ++i)
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define rrep1(i, n) for (int i = (int)(n); i >= 1; --i)
#define allrep(X, x) for (auto &&X : x)
#define all(x) (x).begin(), (x).end()
#ifdef LOCAL
  #include "../../Lib/cout_container.hpp"
  #define debug(x) cerr << #x " => " << x << endl
#else
  #define debug(x) 0
#endif
using lint = long long;
constexpr int    INF  = 1 << 30;
constexpr lint   INFL = 1LL << 62;
constexpr int    MOD  = (int)1e9 + 7;
constexpr double EPS  = 1e-9;
using namespace std;
namespace { struct INIT { INIT() { cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(15); } } INIT; }

struct Point {
  lint x, y;
};
vector ans;
int main(void) {
  lint k, x, y;
  cin >> k >> x >> y;
  bool negx = (x < 0), negy = (y < 0);
  x = abs(x);
  y = abs(y);
  bool bigy = (x < y);
  if (bigy) swap(x, y);
  lint xy = x + y;
  lint n  = 0;
  if (!(k & 1) && (xy & 1)) {
    n = -1;
  } else if (xy == k) {
    n = 1;
    ans.push_back({x, y});
  } else  {
    Point now;
    now.x = now.y = 0;
    while ((xy > 2 * k) || (xy & 1)) {
      if (y != now.y) {
        if (y - now.y >= k) {
          now.y += k;
        } else {
          now.x = k - (y - now.y);
          now.y = y;
        }
      } else {
        now.x += k;
      }
      xy -= k;
      ++n;
      ans.push_back(now);
    }
    n += 2;
    lint half  = (2 * k - abs(xy)) / 2;
    int  minus = (xy < 0 ? -1 : 1);
    ans.push_back({now.x + (k - half) * minus, now.y - half * minus});
    ans.push_back({x, y});
  }
  cout << n << "\n";
  allrep (p, ans) {
    if (bigy) swap(p.x, p.y);
    cout << (negx ? -p.x : p.x) << " ";
    cout << (negy ? -p.y : p.y) << "\n";
  }
  return 0;
}

新ABC最難関と噂のABC135 E Golfを解いた。
鬼のようにWAしたがなんとかAC。
問題がシンプルなのもあってか、解説の見た目がほとんど同じで中身も結構似ているのにやっていることが少し違うというのがあるようで、別種の解説に影響を受けてWAを量産してしまった。
自分がやりたかったことはkmjpさんの解説が近かったようで、それに気づいてからは案外すぐにACできた。


Kずつ進んでいき、残り距離が2K以内で偶奇が合っていれば2打で辿り着けるというのは分かったのだが、2K以内に入ってから偶奇が合わないからどうしよう、という問題があった。
最初に思いついたのが、ゴールと2Kの範囲内でちょっと近づければ偶奇が入れ替わり、同様に2打で辿り着ける！というものだが、そのうまい具合にちょっと近づける方法がなかなか思いつかなかった。

ここで魔のささやき声。
公式YouTubeの解説等の、右に行き過ぎて上に行き過ぎて戻れば3打で辿り着けるルートを作成できる！という解法。
この解き方は、Kずつ進んでいって残り2K以内になったらというわけではなくて、(0,0)からゴールまで通しのルートを作成するらしい。
そこを勘違いして取り組んでかなりのWAを量産した。

前述のやりたいことが違うというのに気づき、kmjpさんの解説にあった「行き過ぎても良い」という素晴らしいお言葉を見つけ、偶奇をあわせるために余分にK進む、という方針でACすることができた。

とはいえ、スタートからゴールまでのルートでも、2K以内からゴールまでのルートでも、どちらでも正しいルートは作成できると思うのだが、実装が間違っていたのだろうか。
完璧に理解しないとその問題を解いたと見なせない質なのだが、やりたかったこと違うというのは、どこで都合の良い勝手な変換が行われているか分からないので、今回のこの疑問は追求するだけのモチベーションにはならないのが救いである。
一応そちらのコードも載せておくが、後で見直すことはないだろう・・・。