うにゅーん、って感じだ

だいたいのコンテストサイトで橙か赤です、よく C#を書きます。

Advent Calendar Contest 2017 Move on grid 雑記

yukicoder Advent Calender Contest

解説 Advent Calendar 2017

これは解説 Advent Calendar 2017 の 13日目の記事です。
adventar.org
ちゃんとここまで埋まってきていてすごい！


問題の解説ページにわりとちゃんとした解説を書いたので、こちらはどちらかというと雑記という感じです。

ひとこと

この問題、わかっちゃえば簡単だからみんな解いて！！！！！！

雑記

問題はこちら。
No.612 Move on grid - yukicoder


解説の方にも書きましたが、これは今年の東大の入試問題を参考に作成しました。
当時ほんのちょっとだけ twitter で話題に上がったので、覚えている人もいるかもしれません。

今回の問題は、それを少しだけパワーアップしたものになります。
おそらく解説が上がるまでに通した人数は（writer/tester 除き）16 人で、これは想定よりだいぶ少ないなぁと思いました。

多分 {d \leq ax + by + cz \leq e} という条件をうまく噛み砕けなかったのだろうと思うのですが、元々は「平面 {ax + by + cz = d} と平面 {ax + by + cz = e} に挟まれた領域」みたいな感じに表現しようかなと思っていて（こちらよりはわかりやすいんじゃないかなぁと思っていたのですがどうでしょう…）。ただそれだと、そもそもこの平面がどんなものか想像するのに数学能力とコストを要しそうだなぁと思い、領域の概形がわからなくても式変形してれば解ける、みたいな大学受験数学にありがちな感じになりました（でもこんだけ解かれないなら難しくしちゃえばよかった……）。


上に書いた通り、この問題で出てくる {d \leq ax + by + cz \leq e} という条件は、3次元空間上の無限に広い分厚い板みたいなものを表しています。パラメータの値によって、その板がすごく分厚くなったりするわけですが。

それがわかった上で、どうすればこの問題の解法に行き着くかですが、まず単純に、以下の問題を考えてみましょう。

~~~~~~~~~~~~~~~~~~~~~~~~~
2次元平面上の原点に点Pがいて、1秒ごとに隣接する格子点にそれぞれ 1/4 の確率で移動する
そのとき、6秒後に直線 y = x 上にいる確率は？
~~~~~~~~~~~~~~~~~~~~~~~~~
（これは元ネタの東大の入試問題そのままです）


この問題の解法はいろいろありますが、自分が考えたのは以下のようなものです。

~~~~~~~~~~~~~~~~~~~~~~~~~
x の正方向、y の負方向に動くのは両方とも直線から見て右下方向に動いていて、
x の負方向、y の正方向に動くのは両方とも直線から見て左上方向に動いている。
よって、右下方向に 3 回、左上方向に 3 回動けば良いので、...
~~~~~~~~~~~~~~~~~~~~~~~~~

つまり何を言っているかというと、(1, 0) にいる状態と (0, -1) にいる状態は、どちらも上か左に 1 だけ移動すれば y = x に戻れるので、同一視できるよね、という話です。動的計画法みがあふれてきました。
より一般的に言うと、今いる点の座標じゃなくて、 y = x + k の k の値さえわかっていれば良い、k が同じだったら同一視できる！ というものです。


と、この話が、もちろん今回の問題にも利用できます。

条件式 {d \leq ax + by + cz \leq e} を見ると、x, y, z の値は重要でなく、 {ax + by + cz} の値さえあれば良い、ということがわかるような気がします。
実際、解説にもあるように、6方向の移動は、全て {ax + by + cz} の値の増減（x, y, z の値に依らない）で書き表せます。
（これがこの条件式をなるべく書きたくなかった理由です。強い人が見たらもう答えが書いてあるようなものだと思うので…）


というわけで、1次元の DP に落ちたので、これを解けば ok、という話でした。


個人的な動的計画法の話

個人的に、動的計画法の本質は

  • 部分問題に落とす
  • 複数の状態を同一視もしくは最適なものを選別し、状態数を減らす

だと思っていて、特に重要なのが 2 番目だと思っています。


例えば、いくつかの問題の配点が与えられて、これらで合計 P 点を取る方法は何通りあるか、みたいな問題だったら、
「i 問目まで見て、合計点が j 点」という状態が同一視できるので、これにより状態数が減らせます。

また、ナップサック問題だったら、「i 番目の荷物まで見て、重さの合計が j」という状態の中では、価値が最大のものが（その後どのような選び方をしたとしても）最適である、ということがわかるので、状態数を減らせます。


このように、動的計画法はどのような方法で問題を解けるようにしているのか、という本質が見えると、例えば今回のような問題でも、どこか状態を同一視できないかな……と考えるきっかけになりますし、色々な DP 問題を解けるようになると思います。

C# で競プロをする話

C#

競プロアドベントカレンダー

これは、競プロアドベントカレンダーの6日目の記事です。
adventar.org


ところで、解説アドベントカレンダーというものがありまして、まだまだ全然空きがあるので、皆様どうぞよろしくお願いいたします。
adventar.org


この記事の内容

この記事は、競プロで C# を使っている人の思ったこととか苦労とかをただつらつらと書くもので、読んでもあまり得るものはないかもしれません。
もちろん C# を使っている人、興味がある人に読んでもらいたいですが、C++ 以外の言語をほぼ使わない人にも読んでもらいたいです。
また、自分は C# の言語仕様や関数にそこまで詳しいわけではないので、鉞などあれば twitter までお気軽にお願いします。
あと、この記事内に出てくるコードはほとんどがそれ単体では動かないコードなのでご注意ください。
twitter.com


この記事に類似した記事

これは camypaper さんの記事です。基本的にはこれみたいに進んでいきます。
qiita.com
LINQ は便利。
emkcsharp.hatenablog.com


C# で競プロをするべきか

特に理由がなければ、C++ を使っていれば良いと思います。ただ、C++ はクソなので 個人的には C# を使う人が増えてくれると嬉しいです（それによって生まれる弊害に関して、私は一切の責任を負いません）。


C# の推しポイント

Visual Studio

もうこれがあるから C# を使っていると言っても過言ではない超優秀な IDE です。
Visual Studio は C++ でも使えますが、「VC++ は C++ ではない」という過激派がいたりするので Visual Studio + C++ な人は今すぐ C# に乗り換えるべき。

とは言いつつ、今は自分は Visual Studio は使っていません。Mac + Mono（C# コンパイラ） + Visual Studio Code（IDE ではないただのエディタ）という環境で C# を書いています。Visual Studio 以外で C# を書いている競プロer をあまり見たことがないので、いらっしゃいましたら教えてください。一体なんでこんな環境で書いているんだ…。

ところで最近 Visual Studio for Mac とかいうものが出てきましたが、あれは実質 Xamarin Studio なので C++ は使えません。やはり C# を使うべき。ちなみに自分はインストールしたら Macbook Air の容量をバカみたいに食ったので消しました。Xamarin Studio も巻き込まれて消えたのか、30GB くらい空きました。アプリ開発をしたくなったらまた入れます。

LINQ

LINQ とはなんぞや、という話は多分ここがわかりやすいです。
ufcpp.net
（このサイトは C# を書くなら多分めっちゃ見るサイトだと思います。めっちゃ詳しいしわかりやすくておすすめです）

あまり競プロと関係がなさそうにも見えますが、少し煩雑な処理がワンライナーで書けたりするので便利です。
例えば、配列の偶数の和（ただし複数回登場する数は 1 個だけ足す）を求めたいときは、

int sum = arr.Distinct().Where(x => x % 2 == 0).Sum();

で求まります。
愚直に書くのに比べて微妙に遅いのが少し残念ですが、使い慣れるととても強力な武器になります。

ラムダ式

上のコードに出てくる x => x % 2 == 0 のことです。
これは、だいたい以下の関数を表しています。

bool iseven(int x) {
    return x % 2 == 0;
}

もちろん複数引数の関数も定義できますし、返り値の型も自由です。
こちらが詳しいです。
ufcpp.net

ジェネリック

C++ で言う template みたいなものだと思います。ただ、こちらはもっと型に厳格なものです。
この記事がわかりやすいです。
ufcpp.net

配列外参照で RE

これはしてくれない言語の方が良くないと思うのですが、C# ではちゃんと配列外参照するとランタイムエラーになります。
Visual Studio と合わせると、どこで配列外参照してその時のこの変数に格納されている値はいくつ、みたいなのが見れるのでとても便利！（IDE なのでそれはそう）


入力

C++ には cin とかいう強力なやつがいますが、残念ながら C# にはそんな便利なものはありません。それどころか、次のスペースまで読む、ということができず、1文字読むか1行読むかしかできません。
なので、C#er の人々は自分で入出力を書いている人が多いです。

ただ、それは面倒臭いので、自分はラッパーを作るだけにとどめています。
以下で簡単な説明を（一行の文字数の関係で public やら static やらを省略しているので、適宜）

1行に 1入力

1行に 1入力であれば、普通に入力を取れます。

int Int => int.Parse(Str);
long Long => long.Parse(Str);
double Double => double.Parse(Str);
string Str => Console.ReadLine().Trim();

Trim は先頭末尾の空白を除去するというもので、時々サンプルをコピーしてくると入力の先頭末尾に空白が入っているクソ問題があったりするのでついています。

1行に複数入力（配列で取得）

int[] IntArr => StrArr.Select(int.Parse).ToArray();
long[] LongArr => StrArr.Select(long.Parse).ToArray();
double[] DoubleArr => StrArr.Select(double.Parse).ToArray();
string[] StrArr => Str.Split(new []{' '}, System.StringSplitOptions.RemoveEmptyEntries);

LINQ の Select というメソッドが Python でいう map のようなもので、それを使ってまとめて変換ができます。
Split は引数なしで空白区切りにしてくれるのですが、返される要素から空の要素を除去するオプションを念のため。
String.Split メソッド (String[], StringSplitOptions) (System)

1行に複数入力（個数分の変数に格納）

C++ の cin みたいな便利なのが欲しいと思って作りました（打つ文字数はどうしても多くなるので完全に cin みたいな使い勝手を実現できているとは言い難いですが…）。

bool eq<T, U>() => typeof(T).Equals(typeof(U));
T ct<T, U>(U a) => (T)Convert.ChangeType(a, typeof(T));
T cv<T>(string s) => eq<T, int>()    ? ct<T, int>(int.Parse(s))
                   : eq<T, long>()   ? ct<T, long>(long.Parse(s))
                   : eq<T, double>() ? ct<T, double>(double.Parse(s))
                   : eq<T, char>()   ? ct<T, char>(s[0])
                                     : ct<T, string>(s);
void Multi<T>(out T a) => a = cv<T>(Str);
void Multi<T, U>(out T a, out U b) {
var ar = StrArr; a = cv<T>(ar[0]); b = cv<U>(ar[1]);
}
void Multi<T, U, V>(out T a, out U b, out V c) {
var ar = StrArr; a = cv<T>(ar[0]); b = cv<U>(ar[1]); c = cv<V>(ar[2]);
}

このように使います。

int a; char b; string c;
Multi(out a, out b, out c);
// 100 A qwerty  みたいな入力を受け取れる

out キーワードはどうしても省略できなさそうで、つらい気持ちになっています（言語的には絶対に省略できてほしくないですが）。
あと、入力の数を可変にする方法を探しているのですが、out + params は使えないらしく、今は一つ一つ書いてあります。
ここには引数 3 つまでしか書いてないですが、自分のソースには 6 つまで書いてあります。
f:id:riantkb:20171206013110p:plain

意外と1行で色々な型の入力を受け取らなければいけないケースはわりと多いので、多分便利な方だと思います。

出力

camypaper さんの記事の方にもありますが、毎回 Flush して遅いので AutoFlush を false にしようという話があります。
自分の場合は大体こんな感じです。

static StreamWriter sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
static void Main() {
    sw.WriteLine("Hello, World!");
    sw.Flush();
}

また、下のような関数が欲しかったので、ラッパーを作りました。

static StreamWriter sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
static void Main() {
    int a = 10;
    string b = "qwerty";
    // 引数で与えたやつを空白区切りで出力してほしい
    Prt(a, b);
    // 10 qwerty

    int[] arr = { 1, 1, 4, 5, 1 };
    // 配列の中身を空白区切りで出力してほしい
    Prt(arr)
    // 1 1 4 5 1
    sw.Flush();
}
static void Prt(string a) => sw.WriteLine(a);
static void Prt<T>(IEnumerable<T> a) => Prt(string.Join(" ", a));
static void Prt(params object[] a) => Prt(string.Join(" ", a));

params によって可変長引数が取れ、それを空白区切りで結合してます。
確か string の配列を引数に渡すとコンパイルが通らないのですが、理由がよくわからないのと困ることが全然ないので今のところは放置しています。
それによりいわゆるフォーマット出力がやりづらくなりましたが、C# 6 でこんなものが追加されたので問題なし。
ufcpp.net


色々 C# にないもの

long double

そんなものはないです。諦めましょう。
ちなみに多倍長整数はあります。
BigInteger 構造体 (System.Numerics)

UpperBound/LowerBound

そんなものはないので自分で実装しましょう。

swap

ないはずですがさすがにこれくらいは必要だったら実装をすれば良いと思います。

Priority Queue

そんなものはないので実装しましょう。
自分はこの記事のサンプルソースを自己流に改変したものを使っています。
ufcpp.net

ググればいっぱい実装が出てきますし、最初に紹介した camypaper さんの記事にもあるので適当に拝借すれば良いでしょう。

どんな実害があるかというと、Dijkstra を実装するのにまず Priority Queue の実装から入る羽目になったりします。

deque

そんなものはないので自分で実装しましょう。ところで私は持っていません。
この前 deque を使う問題が出た時はなんか stack を組み合わせて解いた気がします。

set/map の upperbound/lowerbound

そんなものはないので平衡二分探索木を実装しましょう。ところで私は持っていません。
C++ と Java にはあるので当然どんな言語にもあるのだろうとか言っていつかのコード祭り予選 D 問題にそれが必要な問題が出て、クソかよと言ったこともあります。

ちなみに最近自分の取っている解決方法としては、諦めて C++ を書く、です。
（さすがにそろそろ庭に平衡二分探索木を植えなければならない）

multiset/multimap

そんなものはないので平衡二分探索木を実装しましょう。ところで私は持っていません。

next_permutation

そんなものはないので自分で実装しましょう。ところで私は持っていません。
どうしても必要な時は C++ を書きますが、なかなかそんなことはないです。

pair

普通に pair みたいな型は Tuple だったり KeyValuePair だったりがあったりしますが、比較が定義されていないので実装をしましょう。
ついでに make_pair も実装しましょう。
（自分の環境では using static util しています）

class pair<T, U> : IComparable<pair<T, U>> where T : IComparable<T> where U : IComparable<U>
{
    public T v1;
    public U v2;
    public pair(T v1, U v2) {
        this.v1 = v1;
        this.v2 = v2;
    }
    public int CompareTo(pair<T, U> a) => v1.CompareTo(a.v1) != 0 ? v1.CompareTo(a.v1) : v2.CompareTo(a.v2);
    public override string ToString() => v1 + " " + v2;
}
static class util
{
    public static pair<T, U> make_pair<T, U>(T v1, U v2) where T : IComparable<T> where U : IComparable<U> => new pair<T, U>(v1, v2);
}

#define

そんなものはないです。マクロいくない。
typedef に近いものはあります。

数値であることを表す interface

何が言いたいかと言うと、こういうことです。
C#のジェネリクスでできないこと - Qiita

それを解決する方法として、式木 (expression tree) を使うという方法があります。
ここはもうよくわからんなので、詳しくは以下を参照してください（自分はこのページの一番上にあるコードを利用しています）。
ufcpp.net


C# のつらいポイント

すでに上の C# にないもの のコーナーで十分つらくはなりましたが……。

ICPC

C# が使えないコンテストは少ないながらいくつかありますが、その中で最も影響が大きいのが ICPC です（Java は使えるのに…）。
今年は C++ の練習を積んでから行ったのでまだどうにかなりましたが、去年までは本当に vector の sort すらできない有様でした。

他にはハル研のマラソン（あれはコードを用意する手間があるので致し方ない）や、C# が使えないのに VB が使えるとかいうわけのわからないコンテストがあったりしました。

AOJ

Aizu Online Judge の C#(mono) のバージョンがとても古く（おそらく AOJ_tutorial.pdf にある mono 2.10 から変更がない）、普段書いているコードがコンパイルを通りません。アロー演算子がダメなのはまだ良いのですが、string.Join の引数が string の配列しか許容されないのが本当にアレなので、最近は AOJ で問題を解く時はほとんど C++ で書いています（そもそも ICPC の練習で解くことが多いというのもある）。

配列などの初期化

基本的には、色々な参照型は new で初期化してあげる必要があるので、2 次元配列や List の配列などはすべて初期化して回らなければなりません。
一応 LINQ で回せばワンライナーにはできます。

var arr = new int[10][];
var lis = new List<int>[10];
// この時点で arr[0][0] = 1 や lis[0].Add(1) などをすることはできない

for (int i = 0; i < 10; ++i) {
    arr[i] = new int[20];
    lis[i] = new List<int>();
}

実行時間

コンパイラのバージョンが上がるごとに改善はしてきましたが、やはり C/C++ には劣ります。普通のプロコンならまだしもマラソンだとわりと致命的なのでは……？

使っている人があまりいない

使っている人がそこまで多くないので、C++ のようには豊富にライブラリはないです。


自分もつい最近まで知らなかったのですが camypaper さんがライブラリを上げてくださっているようです。



というわけで、どちらかというと C# のここがつらい、という話になってしまいましたが、C# は慣れるとけっこう楽しいですし、C++ へのヘイトを着々と溜めることができるので みなさんぜひ触ってみてはいかがでしょうか。

Advent Calendar Contest 2017 C hel__world (2) 解説（？）

Advent Calender Contest yukicoder

解説 Advent Calendar 2017

これは解説 Advent Calendar 2017 の 4日めの記事です。
adventar.org
まだまだ全然埋まってないので助けてください。

解説（？）

問題はこちら。テスターをしました。
No.603 hel__world (2) - yukicoder


まずは、嘘が見つかってしまい大変申し訳ありませんでした。


さて、問題についてですが、本質というかもはや 99% は
{\displaystyle \prod_{1 \leq k \leq n} {}_{x_k}\mathrm{C}_{a_k}} を最大化するような {X = \{ x_1, ... , x_n \} \ \sum X = Const}
を探す問題になります（詳しい式は解説や元ネタ問題の解説の方を参照してください）。

https://yukicoder.me/problems/no/295/editorial の priority queue 解の方を読んでもらえばわかりますが、{x_k} の値を 1 増やす場合、全体の値は {\displaystyle \frac{x_k + 1}{x_k - a_k + 1}} 倍になります。そしてこれらは {x_k} の値が増えていくと単調に減少していくので、つまり今選べる中で一番大きいものを貪欲にとっていけば良い、ということがわかり、priority queue 解が生まれます。

ここで、お、これ二分探索したくない？ と思うはずです。きっとそう思うのです。
でも、実はそこからの道のりが意外と長いです。

今回は、解説というより、方針が思い浮かんでからここがつらかったダイジェスト、みたいな感じでお送りしたいと思っております。

（実は writer 解はこれとは違いますが、自分にはよくわからないです。）

二分探索の中で二分探索？

ここはそこまで大変とかいう話ではないですが、まず一つ重要なところだと思うので。
二分探索をするとなると、まずは、ある実数 {m} に対して、 {\displaystyle \frac{x + 1}{x - a + 1} > m > \frac{x + 2}{x - a + 2}} となるような {x} を探したい気持ちになります。
もちろんこれは二分探索をしても良いのですが（多分）、{c = x - a + 1} とおくと、これはそのままそこを使う回数（つまり求めるもの）と一致していて、かつ上の式が
{\displaystyle \frac{a + c}{c} > m > \frac{a + c + 1}{c + 1} \Leftrightarrow \frac{a}{c} > m - 1 > \frac{a}{c + 1} \Leftrightarrow c = \lfloor \frac{a}{m - 1} \rfloor}
となり、定数時間で求められるようになります。

分数の比較

二分探索をする上で分数の比較が必要不可欠ですが、普通にかけ算をしてしまうとオーバーフローしてしまいます。
そこで、2 つの分数 {\displaystyle \frac{a}{b}, \frac{c}{d}} に対し、

  1. {a / b} と {c / d} を比較する
  2. 同じだった場合、その値を {e} とおき、{\displaystyle \frac{d}{c - d \cdot e}, \frac{b}{a - b \cdot e}} に対して 1. を行う

とすると、log 回くらいで比較が完了します（今回は分母と分子の差が小さいことが保証されているのでもう少し早そうですし、オーバーフローしないところまで小さくなったらかけ算で比較してしまうと良いです）。

combination の計算

これはみなさん大丈夫だと思うので省略します。前もって階乗とその逆数を計算しておいて、n を Mod 取って n - k を Mod 取ったものより小さくなったら 0 、そうでなければその間を計算して k! で割る、みたいな感じ。

精度が足りない

これで全て大丈夫、かと思いきや、このままだとまだ通りません。というのも、m の値が 1 付近で精度を求められ、 1.00000000000000000114514 みたいな数を扱う羽目になります。でもそこについては簡単に対処できて、m ではなく m - 1 の値を決めることにより探索範囲を [1, 1e6] から [0, 1e6] に変更して対処できます（1 付近でないところで精度を求められると死にますが、恐らく大丈夫だろうという結論になりました）。あ、ちなみにもちろん long double じゃないと精度が足りません。

時間が足りない

これで今度こそ大丈夫、かと思いきやそうではありません。二分探索時に要求される精度が高いのでどうしてもループ回数が多くなってしまい、微妙に間に合いません（高速化のプロなら間に合うかもしれないです）。
そこで、二分探索をする範囲を絞ります。
上で定義した {c} と式変形で得られた式を用いて、
{\displaystyle a_k > (m - 1) \cdot c_k > a_k - (m - 1) \\ \displaystyle \Rightarrow \sum a_k > (m - 1) \cdot \sum c_k > \sum a_k - n \cdot (m - 1) \\ \displaystyle \Rightarrow \frac{\sum a_k}{\sum c_k} > m - 1 > \frac{\sum a_k}{n + \sum c_k}}
とすることができ、これで二分探索の範囲を絞ることができ（自分の雑な計算では二分探索のループが最大 40 回程度で終わるという結論になりましたが本当かどうかは知りません）、これでようやく通るようになりました。


という感じで、テスターをしながらとても大変だなぁと思っていました。

難易度設定については、そもそもネタ元問題が★5 あるかなぁという気持ちはあって、ネタ元★4 今回の★5 くらいが適正かなぁと（個人的には）思いました。

DDCC2017 本戦 C - グラフいじり 解説

AtCoder DDCC

解説 Advent Calendar 2017

これは解説 Advent Calendar 2017 の 1日めの記事です。
adventar.org
全然埋まってないので助けてください。

（1日目から遅刻したので、これより先にnmさんの2日目の記事が公開されました）

解説（？）

りあんちゃん「で、今日やる問題ってどんな問題なの？」
たくぼくん「今日の問題はこれ。DDCC2017 本戦 の C 問題 だよ。」
りあんちゃん「それじゃあ問題を読んでみるね。有向グラフが与えられて、一つ以下の辺の長さを変えて、全てのサイクルの長さを 0 にできるかどうか…？ なんかもう何を言っているのか全然わかんないよ……」
たくぼくん「うーん、確かにそうだね。じゃあまずは『全てのサイクルの長さが 0 である』というのがどういう状態なのか、どうやれば判定ができるかを考えてみようか。」
りあんちゃん「全てのサイクルの長さが 0…。うーん、そもそもどういう状況なのか全然よくわからないよ……。」
たくぼくん「そうだね。じゃあ少し言い換えて、『どの頂点からどんな経路をたどってその頂点に戻ってきても、必ず距離が 0 になる』と言い換えてみようか。」
りあんちゃん「えっと……なるほど！ 確かにそう言い換えられるね！ でもそれってどういうことなんだろ……」
たくぼくん「一応そこまで言い換えられれば十分ではあるんだけど、じゃあもう少し言い換えようか。マイナスの距離、とかは少し考えづらいから、距離じゃなくて何か別のパラメータが上下していると考えてみようか。例えば……高さとか。」
りあんちゃん「つまり、各頂点に高さを設定して、プラスの辺はその分高い、マイナスの辺はその分低い……ってこと？」
たくぼくん「そう！ それじゃあそのとき、条件はどう言い表せる？」
りあんちゃん「えっと、距離が 0 ってことは高さの変位がないってことだから、それじゃあ一周してきても高さが変わらない、ってことだ！」
たくぼくん「そういうこと！ つまり全ての点の高さが矛盾なく定まることと同値なんだ。」
りあんちゃん「じゃあ適当な頂点の高さを適当に決めて、全ての頂点が矛盾なく決まればおっけーってことか！」
たくぼくん「今回は強連結であることが保証されているからそれで大丈夫。強連結でない場合も逆辺が簡単に張れるから同様にできるはずだよ。」
りあんちゃん「これでやっと判定はできたけど、長さを変えてこうなるかどうか、はどう判定すればいいの……こんなのできるの？」
たくぼくん「実は長さを変える場合、長さをいくつにすればいいのか、というのはさっきの高さの話を考えるとわかるよ。」
りあんちゃん「あ、そっか！ 2 点の高さがわかっていれば、その間の辺の距離は高さの差分である必要があるんだね。」
たくぼくん「つまり、その辺の本来の長さ、というのは、その辺を除いたグラフで各頂点の高さを求めてやればわかるんだ。」
りあんちゃん「なるほど〜！ 計算量的にも間に合いそうだし、これが答えだね！」
たくぼくん「残念ながらこれだと TLE するんだ。内部の高さを求めるところが O(N) じゃなくて O(M) かかるからね。」
りあんちゃん「え〜〜〜！ じゃあどうすればいいの？」
たくぼくん「ここまでくればあともう少しだよ。内部の高さを求めるところの計算量は落ちなさそうだし、消す辺を選ぶところをどうにかして O(N) にできないかな？」
りあんちゃん「え、何言ってるのそんなの無理でしょ。」
たくぼくん「そう言わずに……。消す辺は 1 本ずつじゃなくて、とある頂点が終点であるような辺全てを一気に消しても大丈夫なんだ。」
りあんちゃん「うーん…？？？ ちょっとわかんなくなってきた。どういうことなの？」
たくぼくん「なんかだんだん受け答えが雑になってきたなぁ…。つまりどういうことをするかというと、ある頂点からスタートして、その頂点に帰ってくる辺以外に対して高さを計算する。その時点ですでに矛盾があったら NG だけど、そうじゃない場合は最後にその頂点に帰ってくる辺全てを見て、それらが繋いでいる2点の高さとその辺の長さとの矛盾をチェックして、矛盾の数が 1 つ以下なら ok、ってことになるんだ。」
りあんちゃん「うーん。つまり、始点に戻ってくる辺っていうのは、高さを計算するのに関係ないから、互いに影響しないからまとめて矛盾をチェックできる、ってこと？」
たくぼくん「そういうこと！（台本棒読みだけど……）」
りあんちゃん「まぁなんとなくわかったような気がしなくもないけど、でもこんなのコンテスト中に思いつくの？」
たくぼくん「コンテスト中はこんなちゃんと理路整然と考えられてはいないけど、でも考察をしていればいずれ近いところまでは十分思いつけるとは思うよ。やっぱり『全てのサイクルの長さが 0 である』って条件をどう自分にとってわかりやすい言葉に言い換えられるかがポイントだったのかな。」
りあんちゃん「ふーん……。」
たくぼくん「（もう飽きちゃってる……）」

あとがたり

この問題は、予選を勝ち上がったメンバーで行われる本戦という舞台でけっこう虐殺が行われたのと、公式解説がなんやねん、と（個人的には）思ったので自分の解法を書きました。
まぁコード祭りもありましたしもう忘れている人が多そう…。
公式解説、なんやねんとは思いましたがあちらの方が汎用性が高そうで、こういう問題を安定して通すには多分公式解説の方法がさっとできると良いのだろうと思います。まぁ800点問題に取り組む人はこれくらい常識でいてほしい、ということなのでしょうか（つらいにゃあ）。


さて、上の方でも書きましたが解説アドベントカレンダーの埋まり具合があまりよろしくないです。
1日目から遅刻していることからも分かる通り、自分には残りの日を埋めるパワーはないので、ぜひみなさん助けてください！