うにゅーん、って感じだ

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

就業体験日記 #1

  • 前日の推定就寝時間 : 2:30
    • はいダメ
  • 起床時間 : 8:50
    • 普通に時間がヤバい
    • やんやん駅(まで|から)ダッシュをしたら集合時間の 5分後に着いた
      • ギリギリセーフみたいなとこある
  • 簡単な説明とノートPCのセットアップをした
    • 自分だけ謎のエラーを吐かれてセットアップ失敗した(かなしい)
  • 配属するチームに合流しチームのミーティングを端っこの方で聞いていたりした
    • 大学院のチーム開発演習の授業で聞いたような単語がちらほら出ていてほえ〜となるなどした



ACM-ICPC 2018 国内予選

ICPC国内予選がありました。

なり、りあん、ぴろずのチーム「narianZ」で参加し、7完で2位でした!!!
f:id:riantkb:20180707160833p:plain

人類1位


東工大からは 11チームが参加して、おそらく3チームがアジア地区予選に進出しそうです
(まさか IQ1 が予選落ちするとは……)
f:id:riantkb:20180707162416p:plain

〜 チーム結成

去年の WF進出チーム「ninjaribaton」のメンバーの nari くんとチームを組むことになり、あと一人を探す

一昨年の WF進出チーム「po」のメンバーの piroz さんに入っていただけることになり、narianZ が完成


rian_tkb はチーム唯一の WF 未経験者かつ US配列できないマンかつ C++書けないマンなのでチームの印刷と睡眠担当です

ところで

チーム U Don すき


模擬国内予選 (7/1)

模擬国内予選に参加しました
2018/Practice/模擬国内予選/順位 - ACM-ICPC Japanese Alumni Group

人類1位になる

あまりコンテストの詳細は覚えてないにゃん


国内予選前日 (7/5)

夜になってから US 配列キーボードを買いに出る





国内予選当日 (7/6)

コンテスト前

夢の中でも icpc に参加する


narianZ に割り当てられた会場が普段あまり使わないところで、色々と困る


エスパーにより GCC を見つける
つらい

ぬいぐるみが増える(ティッピーは大きすぎて持ち運びがつらいのでお休みです)


コンテスト中

最初にぴろずさんが A、りあんが B、なりくんが C を読む。
印刷を待っている間 A の問題文を覗き見ていたら自明そうに見えたのでそのままぴろずさんに通してもらう。
その間に B を読む。明らかにやるだけだが折り返す方の長さの方が長いときに少しめんどいかもなぁと思う。
なりくんが C が一瞬だと言っていたので先にそちらを実装してもらう。
そのあと B を実装したが、高さと幅の入力が逆だと思ってたりして少しバグらせる。
コードを印刷したら3秒でバグに気づき(折り返す方の長さの方が長いときに死んでた)、AC。
自分が B に苦戦している間に D は全探索だという話になっていて、ぴろずさんが通す。
E, F がよくわからないね、ということを言っていたらなりくんが G は簡単な構文解析をしたらあとはしゃくとりをやるだけ、とか言い出して、「なんだこいつ、ついに頭がおかしくなったか…?」と思う(前半の構文解析は確かに難しいものではないが、後者のしゃくとりは普通にクソけわしいと思うんですが…)。
ただ E, F の解法が全然詰まっていなかったので、とりあえずなりくんに G を書いてもらう。
主に F の考察をしながら、なりくんが G のデバッグをしているなぁ〜、と思っていたらいつの間にかサンプルが合い、そのままテストケースも通る。?????? 本当に意味がわからない。
なりくんが G を通している間に F も実装の軽い O(N^2 log N) 解が閃き、また E も桁上がりのシミュレーションをやっていくだけだということがわかる(個人的には E は知識ゲーに見せかけて全然そんな感じではない(どころか逆に知識が邪魔をするタイプの問題)なのでけっこう良問だと思う)。
F より E の方が実装が軽そうだったので、ぴろずさんからなりくんに F の解法を伝言ゲームをしてもらいつつ、自分が E の実装をする。
適当に実装したらまぁまぁバグらせ、ぴろずさんに助けてもらいつつバグを取るもサンプルが合わないので、コードを印刷しつつ F を完全に理解したなりくんにコーディングをバトンタッチ。
コードを印刷したらミスを 3秒で発見した(入力を左右逆に取っていた)ので、割り込み実装をし AC。
そのままなりくんも F を AC し(実行時間は 30秒くらいかかった)、2時間20分ほどで 7完。
その時点では H は全く通されていなかったので、完全に集中力が切れて H を考えるフリをしながらぼーっとしたり順位表を眺めたりして過ごしていた。
UT a.k.a ls のペナルティが小さかったので G が解かれて抜かされることを覚悟していたが、運良く 2位のままフィニッシュ。




コンテスト後




感想




しうかついやだー

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++ へのヘイトを着々と溜めることができるので みなさんぜひ触ってみてはいかがでしょうか。