問題
ACコード
WAコード

#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; }

using Weight = int;
struct Edge {
  int src, dst;
  Weight weight;
  Edge(void) {}
  Edge(int src, int dst) : src(src), dst(dst) {}
  Edge(int src, int dst, Weight weight) : src(src), dst(dst), weight(weight) {}
};
using Edges = vector;
using Graph = vector;

void edges_to_graph(Graph &graph, const Edges &edges, const int vertices, const bool directed = true) {
  graph.resize(vertices);
  for (const auto &e : edges) graph[e.src].emplace_back(e);
  if (!directed) for (const auto &e : edges) graph[e.dst].emplace_back(Edge(e.dst, e.src, e.weight));
}

void dfs(Graph &g, int v, vector &route, vector &checked, bool &ok, const vector &vlist, const int len) {
  if ((int)route.size() >= len - 1) return;
  route.push_back(v);
  if (checked[v]) {
    ok = true;
    return;
  }
  checked[v] = true;
  for (const auto &e : g[v]) {
    if (!vlist[e.dst]) continue;
    dfs(g, e.dst, route, checked, ok, vlist, len);
    if (ok) return;
  }
  route.pop_back();
  checked[v] = false;
}

Graph graph;
int main(void) {
  int n, m;
  cin >> n >> m;
  Edges edges(m);
  rep (i, m) {
    int a, b;
    cin >> a >> b;
    edges[i] = {--a, --b};
  }
  edges_to_graph(graph, edges, n);
  vector route(n + 1);
  iota(all(route), 0);
  bool changed = true;
  int  len = INT_MAX;
  while (changed) {
    changed = false;
    vector vlist(n);
    rep (i, route.size() - 1) vlist[route[i]] = true;
    rep (i, route.size() - 1) {
      vector checked(n);
      bool ok = false;
      vector newroute;
      dfs(graph, route[i], newroute, checked, ok, vlist, len);
      if (ok) {
        int start = newroute.back();
        rep (j, newroute.size()) {
          if (newroute[j] == start) {
            route = vector(newroute.begin() + j, newroute.end());
            len   = newroute.size() - j;
            break;
          }
        }
        changed = true;
        break;
      }
    }
  }
  len = len != INT_MAX ? len - 1 : -1;
  cout << len << endl;
  rep (i, len) cout << route[i] + 1 << "\n";
  return 0;
}

コンテスト参加中は考えるべきではないと判断した問題だが、正解となるグラフがどのようになるのか分かれば全体の理解は簡単だった。
BFSでの解説が多く見つかったが、DFSの方が書きやすいし制約的にも大丈夫そうなのでそちらで実装した。
直感的にはBFSの方がやりたいことにあってそうだし早そう。
DFSでACまで持っていったが、すんなり理解したわりに実装はバグらせまくってしまった。

WAコードの一番の問題は、グラフが連結だと思いこんでしまっていたことも含む、グラフへの理解のなさ。
工学系出身なので理系ではあるものの、グラフ理論なんてものはやっていない(たぶん)ので、競プロである程度勉強したとは言え、やはりグラフと言えば全ての頂点が繋がっているという固定概念が抜けきれていない。
孤立した点があるならそんなのグラフじゃないじゃん・・・という話だ。
それに気づくまでに時間がかかりすぎた。

グラフが連結であれば、入次数が0の頂点がなければ必ず閉路があると言える。
だが、逆に入次数が0の頂点があれば必ず閉路がないとは言えない。
グラフが連結だと思い込んだ上で、これも言えると思い込み、-1を出力する条件をグラフ全体の入次数のみで判定してしまっていた。
これがWAコードの大きな間違い。
他にも少し間違っている部分はあった。

まず、DFSで子→親への遷移を止めているところ。
普通のDFSならこれをしないのは無限ループの元だが、閉路を見つけるという目的に限ってはこの遷移を止めてしまうと2頂点の閉路を見つけられなくなってしまう。

次に、経路として取った頂点の順番を記録した配列と、その頂点を通ったかどうかO(1)で判定するための配列を別々に取っていたのだが、DFSの帰りに順番の配列の方はpopしたのに、判定の配列の方を変更するのを忘れていた。
完全に頭から抜けていた。
似たようなものはまとめた方が間違いなく良いのだが、順番の記録と判定をうまく一気に行えるような方法はないのかなぁ。

最後に、WAコードの方針なら間違いではないのだが、方針を変えたときに一緒に変えるべきだと気づけなかった部分。
閉路の長さの管理方法の問題。
長さ用の変数と閉路の頂点を格納する配列を別に取っていた。
基本的な方針として、閉路に含まれる頂点+終点になる頂点1つ(始点と被る)の配列を用いて、閉路を縮められないかを確認していた。
この場合、全ての頂点を用いる閉路が最短だとしても、頂点数がN+1より大きくなることはない。
そこで、長さの初期値をN+1にしてN以下の閉路を探していくようにすれば、(WAコードの方針なら)-1になることはないと分かっているので、閉路の初期値に全ての頂点を含めることで、N以下の閉路を見つけられなくてもそのまま出力してうまくいくような実装にしていた。
正しい方針では-1であるかどうかは事前に調べられないので、長さがN+1から変わっていない=閉路を見つけられていない、で判定するようにした。
しかしそうすると、実際に全ての頂点を使った閉路が存在するのか、あるいは閉路が存在しなくて初期値のままになっているのかが、正しく判定できない状態になってしまっていた。
この問題は、長さの変数を「現在の閉路の長さを表す変数」というよりも、「今まで見つけた最短の閉路の長さ」というような役割に変えることで解決した(ほぼ同じような役割だが)。
すごく単純な話だが、長さ用の変数は用意しなくても、Vectorならsize()でO(1)で取得できる。
それなのになぜわざわざ長さ用の変数を用意したかというと、ループの条件式や中身で何度も関数が呼ばれるのを避けたかったからである。
O(1)とは言っても関数呼び出しのオーバーヘッドはあるわけで、そういうの嫌だなぁととても思うタイプ。
そもそもなぜC++を好んで使っているかというと、競プロ関係なく、プログラムは速度至上主義的な考え方だからである。
細かい部分を気にするなら細かい部分まで気を配れる実力つけろという反省。


明らかにDAGが関係してくる問題だと思ったのだが、トポロジカルソートは実装できなかった。
だが閉路を見つけて色々するような経験を積めたので、DAGとかトポロジカルソート関連の問題が出てきたときに生きてくれるだろうと思う。

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

問題
ACコード

#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; }

template 
class ModInt {
  long long n_;

  public:
  constexpr ModInt(const long long num = 0) : n_(num % mod_num) {}
  constexpr const long long&value() const { return n_; }
  constexpr bool   operator==(const ModInt &r) const { return this->n_ == r.n_; }
  constexpr bool   operator==(const long long &r) const { return this->n_ == r; }
  constexpr bool   operator!=(const ModInt &r) const { return this->n_ != r.n_; }
  constexpr bool   operator!=(const long long &r) const { return this->n_ != r; }
  constexpr bool   operator<(const ModInt &r) const { return this->n_ < r.n_; }
  constexpr bool   operator<(const long long &r) const { return this->n_ < r; }
  constexpr bool   operator>(const ModInt &r) const { return this->n_ > r.n_; }
  constexpr bool   operator>(const long long &r) const { return this->n_ > r; }
  constexpr bool   operator<=(const ModInt &r) const { return this->n_ <= r.n_; }
  constexpr bool   operator<=(const long long &r) const { return this->n_ <= r; }
  constexpr bool   operator>=(const ModInt &r) const { return this->n_ >= r.n_; }
  constexpr bool   operator>=(const long long &r) const { return this->n_ >= r; }
  constexpr ModInt operator+(const ModInt &r) const { return ModInt(*this) += r; }
  constexpr ModInt operator-(const ModInt &r) const { return ModInt(*this) -= r; }
  constexpr ModInt operator*(const ModInt &r) const { return ModInt(*this) *= r; }
  constexpr ModInt operator/(const ModInt &r) const { return ModInt(*this) /= r; }
  constexpr ModInt operator+(const long long &r) const { return ModInt(*this) += ModInt(r); }
  constexpr ModInt operator-(const long long &r) const { return ModInt(*this) -= ModInt(r); }
  constexpr ModInt operator*(const long long &r) const { return ModInt(*this) *= ModInt(r); }
  constexpr ModInt operator/(const long long &r) const { return ModInt(*this) /= ModInt(r); }
  friend ModInt operator+(const long long &l, const ModInt &r) { return ModInt(l) += r; }
  friend ModInt operator-(const long long &l, const ModInt &r) { return ModInt(l) -= r; }
  friend ModInt operator*(const long long &l, const ModInt &r) { return ModInt(l) *= r; }
  friend ModInt operator/(const long long &l, const ModInt &r) { return ModInt(l) /= r; }
  constexpr ModInt &operator++() { return *this += 1; }
  constexpr ModInt &operator--() { return *this -= 1; }
  constexpr ModInt &operator+=(const ModInt &r) {
    n_ += r.n_;
    if (n_ >= mod_num) n_ -= mod_num;
    return *this;
  }
  constexpr ModInt &operator-=(const ModInt &r) {
    if (n_ < r.n_) n_ += mod_num;
    n_ -= r.n_;
    return *this;
  }
  constexpr ModInt &operator*=(const ModInt &r) {
    n_ = n_ * r.n_ % mod_num;
    return *this;
  }
  constexpr ModInt &operator/=(ModInt r) {
    long long exp = mod_num - 2;
    while (exp) {
      if (exp & 2) *this *= r;
      r   *= r;
      exp /= 2;
    }
    return *this;
  }
  friend istream &operator>>(istream &is, ModInt<mod_num> &r) {
    is >> r.n_;
    r.n_ %= r.mod_num;
    return is;
  }
  friend ostream &operator<<(ostream &os, const ModInt<mod_num> &r) { return os << r.n_; }
  explicit operator int() const { return n_; }
  explicit operator long long() const { return n_; }
  explicit operator double() const { return n_; }
};

using mint = ModInt;
vector<vector<vector>> dp;
int main(void) {
  int n, k;
  cin >> n >> k;
  dp.assign(n + 1, vector<vector>(n + 1, vector(k + 100)));
  dp[0][0][0] = 1;
  rep (i, n) {
    rep (j, i + 1) {
      rep (l, k + 1) {
        dp[i + 1][j][l + 2 * j] += dp[i][j][l];
        dp[i + 1][j + 1][l + 2 * (j + 1)] += dp[i][j][l];
        dp[i + 1][j][l + 2 * j] += dp[i][j][l] * j * 2;
        if (j > 0) dp[i + 1][j - 1][l + 2 * (j - 1)] += dp[i][j][l] * j * j;
      }
    }
  }
  cout << dp[n][0][k] << endl;
  return 0;
}

むーずかしくなーーーーーい？？？？？
箱根駅伝DPってなんやねん。
箱根駅伝DPを知っていることの難しさに加え、kの遷移について工夫する必要がある点についても考えると、これマジでABCか？って感じ。
個人的今まで解いたABC最難問(最理不尽)は今でもサプリメントだが、典型の難しさと工夫の難しさは過去最高じゃないかなぁという気がする。

それと今回配るDPを使った。
貰うDPと配るDPの違いはあまり詳しく見ていなかったものの、書いていたらこういうことなんだろうなというのがここ1ヶ月くらいで分かってきた。
貰うDPの方が好きなのだが、さすがに今回は配るDPの方が書きやすそう。
ここで配るDP初心者の罠。
kの遷移ではkより大きい値は持ち得るのは分かるものの、kより大きいdpの値は答えとなるdp[n][0][k]には影響を及ぼさない(よね？)し、配るDPなら配列外参照しても答えには関係ないし、ということで気軽に配列外参照してやったのだが、全然ダメだった。
そういやC++って配列外参照したら既にあるデータ破壊することがあったわ・・・。
さすがに昔からC++使ってるのでWAの後すぐに気付けたが、本番ならWAカウント1だもんなぁ。
いつか読んだDPの配列は最大値プラスいくつか余裕持っておこうねが頭によぎる。
件のサプリメントでDPは最初に要素数決定しておいた方が良いかも、と少し考えたものの、自分がコンテストで競うよりも勉強に重点を置いていることを考えると、要素数を最大値と置くよりも入力値から最大値を決定した方がDPの状態・遷移を追えると思ったのでそのようにしていた。
入力値を使うにしても余裕をどれくらい持たせるべきかを把握して、いついかなるときも配列外参照はダメ！と思っておこう(C++の基本)。
以下本題。


最初問題読み間違えて順列部分を見落としていた。
「絶対値だから0の場合は1通り他の場合は±で2通りあるから分けてDP遷移させよう」なんて考えたけど全然違った。
全く思いつかなくてPDF解説読んだけど解説もむずかC。
読み間違えてていたとは言え、DPで解けそうという部分があってたのはgoodポイント。
YouTubeの解説の説明部分を軽く見て理屈を理解した気持ちになり、実際に実装してみるも答えが合わない。
見比べてみるとkの遷移が間違っていた。
動画やその他ブログ等で正しい遷移を調べてみるも、なぜそんな遷移になるのか全く分からなかった。
理解にかなり手間取ったので考え方をメモしておく。


今までやってきて知っているDPには、「その状態で確定した値」を入れていた。
この表現もそのまま聞いてもなんのことやらだが、簡単に言うとその状態で実際に数え上げたらその値になるということだ。
今回の問題で同じようなDPを考えるとうまく行かない。
Kの遷移のうち、保留していた点と新しい点をつなげる場合、増加する奇妙さkはどの点を保留しているかによって変わってしまう。
そうすると、どの点を保留しているかについても情報を保持する必要がある上、kの遷移も保留している点それぞれに行う必要が出てきてしまう。

今回のDPはそうではなくて、「その状態で最低限持ち得ることが保証された値(その状態が持つポテンシャル)」を入れる。
DPの遷移はYouTubeの解説通り(新しい点同士を繋ぐ), (新しい点をどちらも繋がない), (新しい点の片方と保留した点を繋ぐ), (新しい点の両方と保留した点を繋ぐ)の4つがある。
どの遷移についても保留した点を繋ぐのは新しい点であることから、保留した点は保留した点同士繋ぐことはないことが分かる。

次に、今見ているi段目の新しい点について、保留した点と繋がない遷移をする場合を考える。
その次のi+1段目の新しい点と保留した点を繋ぐことを考えると、i段目で繋ぐよりも1つ多く交差することになる。
また最終的には、保留した点は全て繋がれる必要があることから、今まで保留した点j個全ての点が1つ多く交差すると考えて良い。
よって、kを遷移させるときは、保留した点が左右で2つあることも踏まえて、(次のi+1段目で保留する点の個数)×2を足し合わせる。
なお、DPの遷移上、「残り1段しかないのに保留している点が10個ある」なんてことにもなるが、このような値は答えに影響しない。

このように考えると、新しい点と保留した点を繋ぐ遷移は、今まで足してきた「最低限持ち得ることが保証された値」を実際の値に確定させる遷移であるとも言える。
すると、新しい点と保留した点を繋ぐ遷移よりも、繋がない遷移の方がkの増加量が多いのは、「値を確定させる=i+1段目の遷移で交差できる点が減る」と捉えられるため直感的にも理解できる。
少なくとも自分はこのように理解している。


この実際の値としてはおかしい「最低限持ち得ることが保証された値」を保持するのは、「点を保留する」という、実際の状態としてはおかしい状態を保持するからだと考えている。
例えば、ナップサック問題についてのDPを考える場合、[特定の重さまで][特定の番目の品物まで]を状態として持つ。
これらの遷移は全て問題の条件としてありえる値である。
しかし今回のDPでは、[点を特定の個数保留する]という状態を持つが、点を保留した状態なんていうのは問題で許されていない。
最終的には必ず全ての点同士が繋がれていなければならない。
この中間値専用の仮想の状態が、特殊なkの遷移を生み出す。
先程も書いたような、どの点を保留しているかまで保持するようなDPを(時間やメモリの問題は置いておいて)考えると、このような特殊な遷移ではなく、毎回kの増加量を計算して足し合わせる一般的な遷移ができるのだが、この特殊な遷移が時間やメモリを節約するために工夫した部分となるのだろう。