競プロ日記

問題
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とかトポロジカルソート関連の問題が出てきたときに生きてくれるだろうと思う。

差分: +39

4完
Dに時間がかかりすぎた。
苦手だったわけではないが、単純に舐めていた。
真剣に解いていたつもりだけど真剣じゃなかったというのかな・・・。
後50分は縮められたはず。

A問題

かんたん。

B問題

かんたん。

C問題

相当悩んだ。
なるべく差が小さい2つの値の積でNを表せれば良いというまではすぐ分かった。
「同じ周の長さの長方形なら面積を最大にできるのは正方形である」というのはなぜか昔から何度も考えたことがあったので、この方針に疑いはなかった。
ただそれを全く実装できない！
とりあえずNを素因数分解して、あとはその組み合わせの積でなるべく差が小さくなるようにする、ナップサック問題的な問題なんじゃないか？とずっと考えていた。
でもそうするとおそらく間に合わないし、そもそもC問題レベルではないと思ったのでそういう解き方ではないと考えた。
あるときふと思いついた、「√Nから探索始めればいいじゃん！」と。
頭カチカチって感じ。
かなりの長時間考えていた気がするが、改めて確認してみると意外と20分しかかかっていなかった。
ここまで24分。

D問題

これ解くのにおよそ1時間！遅い！
算数の問題だな！と思って紙とペンで頑張ってみたのだが全く進まない。
小学生時代相当頭良かったので解けるだろうと高をくくっていたので解いている途中ずっとショックとも戦っていた。
"数学"ではなく"算数"だと完全に認識してしまっていたので、三角関数なんていう概念はなかったのが敗因。
なんとかして相似とか合同とかで解こうとしていた。
角度が30°とか45°とかで固定で、どれだけ溢れるでしょうとかが算数の問題で、サンプルの回答に無限小数らしき実数が出てくる時点で三角関数が出てくるのは明白だ。
サンプルを見るのが遅すぎたのもよくない。
なんならサンプルを見た後にも、今までの算数の思考が残りすぎて、「無限小数？なんで？どうやって出てくるの？長さの掛け算割り算で角度がそんなことになる？」となかなか理解できなかった。
それもあって三角関数使えると気づいてからもすんなりいかなかったが、それでも10分程度でACまで持っていけたと思う。
二分探索でも解けるみたいだが、角度ごとに溢れるかどうか計算できるならそんな遠回りせずに普通に最大角度求められるんじゃないか？と思う。
深く考えていないが、溢れるかどうかだけでも条件分岐が必要とは書かれていたものの、直接求めるよりは単純に計算できるんだろうか。
これを解いた時点で82分。
さすがにきつい。

E問題

Dを解けるはずという確信はあったので、Dを解いている途中にはちらっとしか見ていない。
18分弱で一応考えてみたが、さすがに無理だった。
消化コストAiと食べにくさFiを小×大となるようにソートするところまでは思いついたが、その先がうまくいかなかった。
完食にかかる時間XとFiのペアーをsetに入れて、最も大きいものを取り出してFi減らしてまたsetに入れて～というのをやろうにも、あまりにもKが大きすぎる。
Fiの最小公倍数を求めれば、全ての人が(LCM/Fi)回修行すれば、最初のsetの順番はそのままで全ての要素がLCMだけ減る！という方針が思いついた中では一番考えている感がある。
考えている感はあるが、Fiに10^6, 10^6-1があった時点で終わってしまうのでたいぶしょうもない。
あまり解放について調べていないのだが、答えを決め打ちして二分探索するっぽい。
その解き方自体はどこかでそういうのがある見たレベルにはあるのだが、詳しくは知らないので勉強ポイント。

F問題

未だに問題すら読んでいない。


これから算数の問題っぽいものも数学の問題と心構えて解きます・・・。

最近件の3完のEを解いたのだが、何も見ずに解けてしまった。
参加したコンテストのEで想定解が新しい知識を必要としないものは一番最初だけだったので、久々に自力で解けて嬉しい。
時間的にもそんなにかからなかったので、D解けてたらEも行けたかもなあと惜しい気持ちもある。
この3完は置いておいて、少なくとも練習だとEもたまにじゃなくて安定して解けるようにならないと始まらない感じがたいぶ出てきたので、頑張って経験積んでいきたい。

差分: +106

4完
1週遅れになってしまったからコンテスト終了後急いで書いている。
風邪を押して参加したけど最低限4完できてよかった。
ちなみに月曜日から5日間熱が出て、書いている今も咳はかなりひどい。

A問題

かんたん。

B問題

全探索に苦手イメージがあるものの、問題文に全探索してねと書いてあったのですぐに分かった。

C問題

ちょっと前のFにもあったスライム問題だ！
解説見ると少し難しそうなことを書いているが、1つ前の要素が異なれば答えに+1を繰り返していけば簡単に解けた。

D問題

三角形を作れる条件を正しく把握していなかった。
風邪が悪いよ風邪が。
紙に書いて把握し直してからは5分くらいで解けたイメージ。
ここまで44分。

E問題

これは解けても良かったなぁ。
燃料1回でどこまで行くべきか、をうまく表せなかった。
AからB、BからC、CからDのルートでA→Dを1回の燃料で行けるとすると、Bまで行った場合の残り燃料と、Cまで行った場合のBで補給した場合の残り燃料と補給しなかった場合の残り燃料と、Dまで行った場合のCで補給した場合の残り燃料とBで補給した場合の残り燃料と補給しなかった場合の残り燃料と・・・と、何通りも考えないといけない！どうしよう！が終始抜けなかった。
想定回答はワーシャルフロイド2回らしいが、最短経路求めてから最短経路求めるのは意味分からんけど頭良い。
言われてみれば確かにこういう何通りも道筋があるものを解けるのが最短経路問題だ。
結局補給すればその時点で燃料はMAXになるので、補給した後にいくつか消費した分の燃料を記憶するのではなくて、前回補給した場所から次にどこで補給できるかをグラフで全て記憶すれば確かに全通りを網羅できる。
この問題は解ける可能性十分あったと思っていたが、書いていたらグラフをどういうところで使えるか本当に知っているか？と問うてる問題に見えてきた。
だとすれば、間違いなく経験不足でグラフに苦手意識のある今解けなかったのは当然かもしれない。
ワーシャルフロイドは問題を解いた経験はないものの一応知識としてはあったのだが、今回は問題を解いたかどうかの経験はあまり関係なさそうに思える。

F問題

なんか解けそうだなぁと思いながら色々考えてみたがなんか解けなさそうだなぁになった。
全ての数字を横に並べ、同じ数字があれば上に重ねていくような図を想定し、だるま落としのように下から抜いていくような考え方かなぁと思って進めてみたものの、この形だと抜ける回数までたどり着けなかった。
問題文の「選び、食べる」の言葉選びのセンス○。


今回の反省ポイントはDで理解が浅いまま進めてしまったこと。
三角形の構成条件なんて簡単やろと思ったら確かに簡単だったけど抜けてた。
やっぱり風邪が悪いよ風邪が！

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