うにゅーん、って感じだ

SRM highest:1959. C#を書きます.

Advent Calendar Contest 2017 Move on grid 雑記

解説 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# で競プロをする話

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

これは、競プロアドベントカレンダーの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 StudioC++ でも使えますが、「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 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 - グラフいじり 解説

解説 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日目から遅刻していることからも分かる通り、自分には残りの日を埋めるパワーはないので、ぜひみなさん助けてください!

コード祭り予選突破練習会をしました

しました。

atnd.org

9/30(土) にやりました。思ったより予選B が近く、慌てて開催 3日前くらいに大枠を固めて参加者を募集したのですが、結果15人もの人に集まっていただき、とても嬉しかったです!

昨年も同じような練習会を行った のですが、昨年との一番の違いは「学外の人も参加できるように貸しスペースを借りて開催した」というところで、実際に人が集まらないととても悲しいことになっていたと思うので本当に感謝です。
(これは他の大学の人からすると意外かもしれませんが、うちの大学は競プロ関連活動がそこまで盛んでなく、練習会などが盛んに行われている他の大学の方々が羨ましいなぁという感じ。今回貸しスペースを借りたのも、学内だけだと全然人が集まらなさそうだと思ったからというのがあります。)


前日

昼 〜 夜


バチャコンの問題セットが決まっていないがライブを見に行く

深夜 1時半ごろ 〜


多い


こんなことをしている場合ではない


使おうと思っていた問題が試しに投げて見たら IE になり悲しむ(ちなみにこの問題でした https://beta.atcoder.jp/contests/autumn_fest/tasks/autumn_fest_06


4時前にようやく完成


結局 11問 3時間になりました


当日


アナウンス


会場がわりとあっとこ本社に近い(新宿御苑はさんで反対側くらい)


スポンサー 欲しい!!!(5000兆円のフォントで)


到着

思ったより会場がちゃんとしていてよかった。

当初の予定より 10分遅れで開始


1時間20分ほどで全ての問題に AC がつく


やはり 2時間40分だと短かったらしく、オンサイトに聞いて 20分延長


2時間半ほどでこばさんが全完!


コンテスト、こんな感じになりました
https://not-522.appspot.com/contest/6671465998974976


コンテスト終了後、適当な解説をしたのち簡単な懇親会をしました。

www.slideshare.net



解いてね


以下、適当なツイ






このお二方とは、次の日の KUPC でもたくさんお話しできました🙌



練習会、やっぱりオンサイトめっちゃ楽しいので色んな人にどんどん開いて欲しい〜!

JAG夏合宿2017(+コード祭り2017予選A)参加記

9/22-24 に、JAG の夏合宿(http://acm-icpc.aitea.net/index.php?2017%2FPractice%2F%E5%A4%8F%E5%90%88%E5%AE%BF%2F%E6%A1%88%E5%86%85)に行ってきました。
今年初めて icpc アジア地区への切符を手にしたので、夏合宿は初参加!

宿泊部屋が足らないという話だったので、毎日お家に帰りました(ただ思ったよりオリセンが家から遠く、片道1時間かかったので宿泊したほうが良かったかもしれない)。


今回、チームメイトの一人は学会か何かが被ってしまったので、kurukuru-sushi からは りあん@rian_tkb)と 葦(@Ashurnasirpal)が参加し、毎日一人チームに迎え入れる形でコンテストに出場しました。

1日目

1日目はすぬけさんのセット(Japan Alumni Group Summer Camp 2017 Day 1 - AtCoder


この日のチームメイトはすみけんさん(実は高校の一つ上の先輩だったことがコンテスト中に発覚しびっくりした)。


Macbook Air に リアフォ を刺しているという謎環境なので、コンテスト前に簡単な操作方法のレクチャーをする(これは結局 3日間ともした)。

コンテスト中の流れ

(記憶が薄れてきているので細部が違っているかもしれないですがご容赦)


コンテスト開始。問題が1セットしかなくホチキスどめされていたのでまずはホチキスを丁寧に外し、問題を机にばらまく。

自分が最初に手に取ったのは E で、問題文の上部に BNF が見えたので問題概要を全く読まずに 3秒で葦くんに投げる(kurukuru-sushi では構文解析問題は全て葦くんに投げるという戦略を取っている)。

次に D を読むと、これは簡単な算数。早速コードを書き始める。途中少し詰まった(直角でないところを直角だと勘違いしていた)ところですみけんさんが J を一瞬で通す。その間に自分もミスに気づき、続けて D も AC。

次は多分 K に取り掛かっていたと思う。問題文を読んでこれはどうせ C_i - G_i でソートしてほいするやつでしょ、とか言いつつ書く。マイナスがついたりつかなかったり、どっちがおっきいとどうなる(自分は通す直前までコストとゲインを逆だと思っていた)とかがややこしいのでそこらへんを色々試すが、どうしてもサンプル1 とサンプル2 が同時にうまくいくようなことがない。そうこうしているうちにすみけんさんが A をいけそうとのことだったので書いてもらう。

K はこれ以上考えるとドツボにはまりそう(というか既にはまっている)なので、ここで葦くんに投げた E の様子を見にいく。問題を読むにそこまでつらそうな問題には見えず、スカラーは要素数1 のベクトルじゃない? と言ったらなんか解決したらしい。

その間にすみけんさんが一人で A を通し、葦くんに E を書いてもらう。手の空いたすみけんさんに K を投げ、その間に自分は H を考える。制約がクソでかいので、明らかにうまい方法があるやつ。こういう問題はまず条件を緩めた問題から考えると良い ので同じ動きを連続でしてよい場合を考えると、3つのうち高々2つの動きしか使わないことが判明。ということは交互にやっていって片方だけ残ってしまったらくるっと回る動作を間に挟めばよい、とわかる(よく考えるとこれが最短ムーブになる証明をしていない)。

ちょうどその頃 K のサンプルを手で試していただいていたすみけんさんにより、C_i + G_i でソートしてほいだということが判明。そこで自分が C と G を逆と勘違いしていたことも判明。

そのあと順位表を見て F が通されているように感じたので F を解けそうな目で見る。するとぱっと見ごつかった問題が実は自分より後での各文字の最初の登場位置と、自分より前での各文字の最後の登場位置がわかれば解けることがわかり、かつそれは普通に各文字から前後に伸ばしていけば間に合うので、途端に解ける問題に大変身した。

そのあたりで葦くんが E を通し、続けて自分が H, K, F と AC。E が通ってから F が通るまで 30 分かかっていない。

残る問題は 4 問で、正直人間に解ける問題が残っていなさそうに見える。

残り40分くらいで、葦くんが G が最小費用流になりそうだと気がつき、自分がライブラリの写経を始める(G をぱっと見フローと気づけなかったのはとても反省…)。写経をしている間に 2人の考察によりじわじわと解法がまとまり、コードを書くが、実装が重くしかも若干バグらせたため時間切れ、とても悔しい(でも結局その後書き上げても通らなかった)。


結果は 7完 7位。上にはガチプロしかいないので人類トップ、ってことでまぁ僥倖かなぁという気持ち。



普通に疲れていたのでそそくさと帰宅してしまった…。


2日目

2日目はこどふぉのgym(http://codeforces.com/gym/100633/


この日のチームメイトはあるごんさん。あるごんさんを kurukuru していく。

コンテスト

(あまり覚えていないし疲れてきたのでここは適当です)

全体的に readforces だった。

最初に L を読んでいけそうに思ったが、誤読したのとまぁまぁバグらせて(無駄に O(N) で解いていた)結局 5WA。冷え冷え〜。

あとは B が簡単な DP だったのでささっと実装したり(Mod が 10億9 でキレた)、G の forward というのが時計回りか反時計かわからずあるごんさんに読んでもらい、そのまま解法を伝えて書いてもらったり、葦くんが H の問題文読解に成功して AC したり、I をわかんねぇなぁ〜、と言いながら貪欲を書いて AC したりしました。


結果 5完で、オンサイト 6位かな? 全体的にキツすぎるセットだった…。


この日は Hec さんとけっこう話をしていた気がする。ABC-D じゃない 400 は怖いよね、という話もした気もする。


コード祭り予選まで少し時間があったので新宿で弐寺をしてから帰った。SP六段です。


コード祭り予選A

その日は予選A がありました(CODE FESTIVAL 2017 qual A - AtCoder

ボーダー予想として、本戦ボーダーは4完早解き、ありがとう祭りのボーダーも4完になるかなぁ、と踏んでいたので、D から開くことを決意。すぎむさんの 700 なので AND Grid のような思いつき構築ゲーが出るかもと予想していたので、死ぬ気で解きにかかるぞという強い意志。


結果、D をうまく思いつけて運良く 27分ほどで通せて、最後に A で 1RE(文字の長さが 4未満の場合に死んでいた)したものの全体 75位、日本人 19位という成績でした。勝ったなガハハ!

d が 2 より大きい偶数のときに各色が大きな正方形を描いていることに、ツイートする用の図を書いているときに気づいた(ア)

D はもちろんつらかったけど他の問題も普通につらくてつらいセットだなぁとなった。


2回目のパフォ 2800 超えによりレートもそこそこ上がった。嬉しい。

3日目

3日目は JAG のセット(Japan Alumni Group Summer Camp 2017 Day 3 - AtCoder


この日のチームメイトはめるさん。めるさんを kurukuru していく。

コンテスト中の流れ

めるさんが A を読んですぐ AC。葦くんが B を読み、実装に入る。自分は C の読解に苦しむ(グリッドに整数が記入されている的な設定でもよかったのでは?)。

葦くんが苦しみながらも B を通し、自分も苦しみながら C を通す(上から下じゃなくて左上から右下に斜めに埋めていってしまったので実装がクソつらかった)。

D はC に苦しみつつも問題概要を聞いていて、さすがに bitDP だろうという気持ちになる。ぱっと見 {O(2^{2N})} っぽいが部分集合の部分集合はもうちょいオーダーが落ちそうに感じ、この方針で行こうと考える。
あいこじゃない遷移は簡単だが、あいこになる確率がとてもつらい。ただ、うまくベン図を書いて考えると {O(N)} で求まり、勝利。AC。

そうこうしているうちに葦くんが F の考察をまとめる。プロ。そのまま葦くんが書いて AC。

E については、自分が + で区切ればいいというのを思いつくが、そのまま区間DPしても 2500^3 になりダメ。すると葦くんが解法を閃いてくれる。プロ。それは自分が実装を行い、AC。実装はめるさんに投げてしまってもよかったかもしれないなぁ。

あとは G を考えていたが、きっと解法は枝刈りではないだろう…、と思ってしまっていたので、相性が悪いと思いつつもフローを考えたりしていて、結局そのまま終わってしまった。6問解いた時点でもう少し時間が残っていたら枝刈ろうと思えていたかもしれないが、まぁ致し方なし。

あと、G をほぼ諦めていた段階で D の計算量を計算したらやはり部分集合の部分集合は {3^{N}} 個で、{O(N \ 3^{N})} になっていた(大学受験数学が得意)。



結果 6完で、オンサイト 7位? 2日目と同じくらいキツいセットだった…。


まとめ

競プロづくしでとても楽しい3日間でした!
コンテストの内容については、さすがにこれは通せなきゃダメだったなぁ…、みたいなのはほとんど無かったような気がしたのでまぁ悪く無かったと思います。ただ、どの日も半分以上の問題の実装を担当したので、もう少し配ればよかったかもなぁとは思いました(自分はそこまで実装の速い方ではない)。

国内予選突破という目標を達成してしまったので来年の ICPC はコーチとして出ようかなぁとか思っていたのですが、やっぱりチーム戦たのしすぎなので来年も選手として出ているかもしれません。まだわかりません。



懇親会的なものがなかったり帰宅勢だったりしたので、あまり交流ができなかったのが少し心残り……。
次は KUPC 東京オンサイトにいく予定です!



ACM-ICPC 2017国内予選 参加記

半年ぶりのブログ更新ですね。
本当はこの記事の前に、この前 SnackDown2017 というやつでインドに行った、という記事を書かなければならないのですがちょっと色々忙しかったのでそのうち書きます。

あらすじ

icpc たいてっく予選は毎年熾烈(しれつ)を極めていた。謎の組織 FCCPC 、†赤きもの†へと進化した後輩、大魔王 yosupot ...。
ただ、そんなたいてっくにも希望はあった。謎の組織 FCCPC は謎すぎたため消滅、大魔王 yosupot は力を溜めるための眠りについた。
今こそたいてっく予選に打ち克つべき! †赤きもの†へと進化した後輩の次の1枠を狙い立ち上がったチーム「kurukuru-sushi」の前に立ちはだかったのは、チーム「IQ1」だった…。

登場人物

チーム「kurukuru-sushi」

rian_tkbりあん), Ashurnasirpal(葦), monman53(もんまん)からなるチーム
http://icpc2017.yamagula.ic.i.u-tokyo.ac.jp/team/1308

チーム「IQ1」

吹雪, 睦月, 夕立 からなるとてもバランスの良いチーム
http://icpc2017.yamagula.ic.i.u-tokyo.ac.jp/team/1142

チーム「ninjaribaton

nari, baton, ninja からなるガチプロ後輩チーム
http://icpc2017.yamagula.ic.i.u-tokyo.ac.jp/team/1327

ティッピーぬいぐるみ

チーム「kurukuru-sushi」の机の上に鎮座するぬいぐるみ


国内予選前日 (7/13)

たいてっく予選突破が絶望的だった一昨年、去年とは異なり、たいてっく予選突破が現実味を帯びている今年のicpc国内予選。……というより、今年の出場選手のうち†赤きもの†へと進化した後輩の次にレートが高いのが自分で[要出典]、さすがにたいてっく予選突破できないと人権がない、という状況になり今までにないプレッシャーに追われる rian_tkb。

血迷った rian_tkb は、秋葉原に赴き25000円のキーボードとリストレストを購入する。

(今思うと、ここまでして突破できてなかったら本当にやばかった)

国内予選当日 (7/14)

コンテスト前

今期の授業は全て切ったのでリハーサルが終わるまでに大学に着けばいいのだが、家にいても落ち着かないので早めに家を出る。


ラボに置いてあった蟻本を持ち、蟻本に書いていない平衡二分探索木と、あとは AtCoder の提出のうち特に苦手なものの提出コードを印刷して会場に向かう。


チームメイトが皆蟻本を持ってきていたので積み上がる。

リハーサルも3問通して暇なので遊ぶ(上の kurukuru-tippy もこのとき撮影)。

この後、もんまんくんが M問題を頑張って通していた。

コンテスト中

最速で印刷ジョブを飛ばしたつもりがプリンターがトナー切れで、少しタイムロス。
その間に A問題を読む。
……ん? これは恐ろしいほどに簡単だぞ???
横からめっちゃ口を挟みながらもんまんくんにコーディングしてもらい、そのまま AC。ここまで 5min。

葦くんが B を読んでいたので見ると、構文解析
問題文がよくわからなかったのでよくよく読むと、ダブルクォーテーションで split して偶奇を気にしつつぐっ、とやるだけ。
しかし、A が通ってしまい PC を空いた状態にしたくないという焦りから見切り発車してしまい、少しめんどい実装になってしまった。
ただそこまでバグらせずに通してくれたのでよかった(とは言ってもやはり時間はかかってしまった)。ここまで 30min。

葦くんが B 問題と格闘している間に C 問題を手に取ると、h, w <= 10 なのが不思議なレベルで簡単な問題。
本当にやるだけにしか見えない。
もんまんくんに解法を伝えつつ紙コーディングをしてもらう(もちろんこれにもめっちゃ口を挟む)。
葦くんが B を通したらそのまま C を実装してもらい、AC。ここまで 40min。

ここで順位表を見る。
結構いい感じに進んでいたと思っていたので IQ1 に時間ペナルティでとても大きく離されていてとてもビックリする。
この様子だと正答数で上回らないと IQ1 に勝てないぞ……。

ここで自明問題が尽きる。
自分はすでにちょっとテンパっていたので、葦くんに D の問題文の要約を頼む(正確には問題概要はほぼ入っていたが、D に入る問題に見えなかった(=普通に解ける気がしなかった)ので誤読が怖くて読んでもらうことにした)。
どう考えても n * m <= 500 が重要な制約だが、よくわからない。
葦くんから整理された問題概要を聞くが、まだわからない。
ただ、こういうのは大抵 n = m あたりが重要なので、紙に 20 * 25 = 500 という式を書く
→ あ、これいけるのでは???
PC が空いていた焦燥感もあり、とりあえず書き始める。
途中少しテンパるが、大きなバグもなく実装した……はずが、答えが合わない。
よく見てみると、求めるものが作れるレシピの集合が何通りあるか、ではなくレシピの集合の要素数の最大値だった(ここは葦くんの誤読だったと思う)。
ただ、修正自体はすぐにでき、AC。ここまで 1h10min。

ここでまた順位表を見ると、また IQ1 との差が広がっている。これは本格的にヤバい……。
E は無理そうという話があったので、先に F を見る。明らかに考察ゲーの匂い。
無理そうと言われていた E も読むが、確かに無理そうだったので、F の考察をする。
とりあえず計算用紙に印をつけて実際に折ってみる。
左からの位置と上からの位置と左右どっちに折ったかがわかれば、次の状態が定式化できそうな状態にはなる、が、まだ考察が進まない。
もう少し考察をすると、上から何番目にあるか、というのは折り方と 1対1 に対応することがわかる。
あと、逆に折った状態から展開したとき、右に開いても左に開いても上から何番目かというのが変わらないことがわかった。
が、前からやっていくべきか、後ろからやっていくべきかがよくわからない。
両方からやって 2^30 はさすがに間に合わなさそう……。

ここでうだうだ言っていると、もんまんくんが考察の手助けをしてくれて、一気に解法へ結びついた


(折った状態から展開したとき、右に開いても左に開いても上から何番目かというのが変わらない、という自分の考察を完全に忘却していた)

ばばばっと書く。
1-origin なので境界条件とか +1 するか、とかがクソめんどい。
実際にバグる。
サンプルが合うようにコードをいじいじする。

そうこうしているうちに葦くんが G 問題がいけそうな雰囲気になったと言っていて、写経が必要なのでとりあえずコードを印刷して交代する。

コードを印刷して眺めていると、バグがすぐに見つかる。
また交代してもらってそこを直すとサンプルが通ったので、そのまま投げると AC。俺ってもしかして天才か??? ここまで 2h。

葦くんが G の写経をしている間、E を考えるが普通に無理そう。
H に関しても、4回まで調べればいいので探索範囲はすごく絞れそうだが絞り方がよくわからない。
なので、葦くんの G の解放に反例がないかどうかを調べる。

葦くんのコーディングが終わってサンプルを食わせるが、バグっている。
いくつかのしょうもないバグは潰し、見た目上はいい感じに動いているが、どうしても関節点列挙がバグっている……。写経はもんまんくんに適宜チェックしてもらっていたので問題ないはず……。
もう時間がなかったので一回バグったままで投げてみるが、当然 WA。
結局バグがどこかわからず、最後は順位表を見ながら終了。

最後の 2h59m59s で IQ1 が F を通していて、時間ペナルティ的に 1WA でも出していたら順位が逆転していたので、本当に危なかった。


結果、ABCDF の 5完 0WA早解きで 16 位でした! まぁ上々では
f:id:riantkb:20170715204109p:plain

Standings
http://icpc2017.yamagula.ic.i.u-tokyo.ac.jp/standings/

コンテスト後





打ち上げに行くが全然飲み足りないので、家で独り祝勝会

いま、めっちゃジンが入っています✌︎

あとがき

国内予選突破できて本当に良かった。
こんな日が来るのは本当に夢みたいで、大学入って競プロ始めて以来、一番嬉しいかもしれない。

それではみなさん、つくばで会いましょう!