競技プログラミングを始めた

競技プログラミングを始めました。今日、人生ではじめてコンテストに参加もしました。やっていて思ったことをいくつか書こうと思います。

ちなみにこれが600記事目ですが、特に特別なことはしません(いつもどおり)。

蟻本に挫折する人生

実は競技プログラミング自体は高校生のころから学んではいました。ただ、入門書として「プログラミングコンテスト チャレンジブック」・通称"蟻本"を選んでしまったのが間違いでした。そのせいで何度も蟻本で挫折をして(高校1年生の数学の知識で理解できるわけがなかった)、「入門書を読み通すことすらできないんだから競技プログラミングの世界はすごいなぁ…」と思いながら撃沈しました。

それから時が経ち、大学に入って研究室の同期とコンテストに参加することになりました。正直、挫折の経験があったので、当初あまり乗り気ではありませんでした。しかし、ゼミで競技プログラミングに取り組むようになって、「あれ？蟻本の前半のほうだけでも問題解けるんじゃん」と気が付きました。

そうなんです。蟻本を入門書と思ってはいけないのです。あれの前半は確かに基本的なことの解説をしていますが、後半になるにつれて超上級者向けの内容になっていきます。つまり、蟻本はどちらかといえばドキュメントに近い性質の本になっています。この事実を知らないままいたことを今かなり後悔しています…

ABCに参加した感想

すでにゼミでABC(AtCoder Beginner Contest)という初心者向けコンテストの過去問に取り組んでいたので、問題の傾向・環境構築などに慣れた状態で参加しました。今回はA問題からD問題まで解けて、パフォーマンスが1255でした。初心者に毛が生えた程度の実力という感じですね。

さて、僕は全体で何位だったかというと、5000人中1000位でした。初心者向けコンテストとはいえ、蟻本に挫折した僕でさえ上位1/5に食い込めました。

蟻本で挫折しないでくれ

これがこの記事で一番いいたいことです。「蟻本を入門本と思わないでくれ」。たしかに、前半部分は読んだほうがいいです。しかし、後半(特にグラフ以降)は初心者のうちは要りません。前半の内容だけでABCでDまでは解けるのです。

では、どのような順序で入門すればいいのでしょうか？僕が思うのはこんな感じです。

1. 蟻本の前半を読む
2. 理解できてなくてもいいので ABCの過去問を解いてみる
3. 調子づいてきたら環境を整える
4. コンテストに出る

まず蟻本の前半を読みましょう。そして、なんとなく「アルゴリズム」の感じを掴みます。そしたら、AtCoder Scoresで100点の問題を解いてみてください。正直、プログラミングの基本がわかっていれば100点・200点はカンタンに解けます。この辺を解くことで「競技プログラミングの型」を覚えてください。3問も解けば十分です。300点問題からはアルゴリズム力が必要になってきます。

過去問を解いてなんとなく呼吸がわかってきたら、環境を整えてモチベーションを加速させましょう。atcoder-cli(ディレクトリの作成・テストケースのダウンロード)とonline-judge-tools(テストの自動実行)がオススメです。

atcoder-cli インストールガイド | わたしろぐ

環境も整えてマクロを作り出したら、いよいよコンテストに出てみましょう。ここまでちゃんと準備ができていればコンテストをそこそこ楽しむことができます。

最後に: 競技プログラミングをやってから気がついたこと

競技プログラミングに取り組みはじめて1ヶ月ちょっと経ちます。そのなかで、「アルゴリズム」を考える力がついてきました。ここでいうアルゴリズム力は、「問題の解法」つまりロジックを考える力のことです。この1ヶ月で、今までよりもロジックを慎重に考えるようになりました。

「アルゴリズム力」といわれて「二分探索などを知っていること」だと思いこんでいる人は損しています。アルゴリズム力はロジックを組む力なのです。

Generatorで自然数列とか素数列を作った

「ゼッタイにこういうライブラリあるだろ」と思って探したんですが、なかったのでここに書いておきます。ライブラリ化はするまでもないですが、たびたび使うので…

// 自然数列. [0, 1, 2, 3, 4, ...]. 数列の最初の数を引数として受け取ります.
const naturalNumbers = function*(n = 0) {
    while (true)
        yield n++;
};
// フィボナッチ数列. [0, 1, 1, 2, 3, 5, ...]. はじめの2項を受け取ることもできます
const fibonacciNumbers = function*(n = 0, m = 1) {
    while (true) {
        yield n;
        [n, m] = [m, n + m];
    }
};
// 素数列. [2, 3, 5, 7, 11, ...]. キャッシュ機構がついているので高速に回るはずです.
const primeNumbers = (() => {
    const _primeNumbers = ((cache = [2,3,5,7,11,13,17,19,23,29]) => function*() {
        yield* cache;
        for (let i = cache[cache.length - 1] + 2; ; i += 2) {
            let isPrime = true;
            for (const j of cache) {
                if (j * j > i)
                    break;
                if (i % j == 0) {
                    isPrime = false;
                    break;
                }
            }
            if (isPrime)
                cache.push(yield i);
        }
    });
    return _primeNumbers();
})();
// 乱数列. [29, 74, 51, 62, ...] のように、引数として受け取った数の範囲の乱数を生成します.デフォルトは0〜99.
const randomNumbers = function*(n = 100) {
    while (true)
        yield 0 | Math.random() * n;
};
// 降下列. [10, 9, 8, 7, ...] のように、引数として受け取った値から1つずつ下がっていきます.
const downFrom = function*(n) {
    while (n >= 0)
        yield n--;
};
// リピート. [0, 0, 0, 0, ...] のように、受け取った値を繰り返し続けます
const repeat = function*(n) {
    while (true)
        yield n;
};

使用例

このように使います

// 自然数を順番に取り出したい
for (const n of naturalNumbers()) {
    console.log(n);
}

ついでにいくつか補助関数をつくりました。組み合わせると便利なはずです。

const pair = function*(arr1, arr2) {
    const item2 = () => arr2.next().value;
    for (const item of arr1)
        yield [item, item2()];
};
const map = function*(arr, f) {
    for (const item of arr)
        yield f(item);
};
const take = (gen, n) => {
    const res = [];
    for (const item of gen) {
        if (n-- <= 0)
            break;
        res.push(item);
    }
    return res;
};

補助関数の使用例:

for (const [index, prime] of pair(naturalNumbers(1), primeNumbers())) {
    console.log(`${index}番目の素数は${prime}`);
}
// 小さいほうから素数を10個取り出す
console.log(take(primeNumbers(), 10));

俺がESLintを勘違いしていたのはお前らが悪い！

ESLintというツールをご存知でしょうか？これは「コードスタイルを統一するためのツール」です。そのため、

• リーダブルコードを読んだことがある人
• コードの整形について知っている人
• if文まわりの改行について一家言ある人

には必要ありません。 〜完〜

！！！！！！違います！！！！！！

違います！これはESLintの一側面を取り上げただけであり、ESLintのメリットのごく一部にすぎません。

このような悲しい勘違いをこれ以上被害が広がる前に撲滅したいと思います。

そもそも静的型付けって？TypeScript入門以前の話

みなさんは「型」についてご存知でしょうか？「intとかcharみたいなアレでしょ？」くらいの知識はあるかと思います。今回の記事では型についての種々の疑問について解説して行きたいと思います。

• そもそも型とは？
• 型があるとなんで嬉しいの？
• 静的型付け・動的型付けって？
• プログラムに型がなくても静的型付けってどういうこと？

なお、この記事ではTypeScriptの型をもとに話しますが、他の言語でも言える普遍的な内容になっています。

そもそも型とは？

型とは、データの分類の名称のことです。たとえば0、42はnumber型、''、'hello world'はstring型です。

型はプリミティブ値以外の式にもつきます。たとえば式1 + 2はnumber型、式'hello' + ' ' + 'world'はstring型です。

また、変数や関数の引数・返り値にも型をつけることができます。型がついた変数は、その型の値しか代入できません。

たとえば、number型の値を2つ受け取ってnumber型の値を返すmax関数はこのようにかけます。

const max = (a: number, b: number): number => a > b ? a : b;

型があると嬉しいこと

型があると嬉しいことはいくつか挙げられます。

1. 型注釈をみることで関数の動作をだいたい想像できる
2. 静的型検査を行うことで「実行時エラー」をなくすことができる

1つ目はオマケで、2つ目のほうが重要です。

型注釈から関数の動作を予想できる

たとえば、map関数は以下のような型を持ちます。

const map = <T, T2>(f: (bef: T) => T2, a: T[]): T2[] => {
    const res = [];
    for (const item of a)
        res.push(f(item));
    return res;
}

fとaを受け取り、aの各要素にfを適用した結果を返す関数になっており、型定義もそのようになっています。

静的型検査を行って実行時エラーをなくせる

静的型検査というのは、プログラムを実行せずに型が正しくつけられているか検証する作業です。たとえば次のコードはTypeScriptの型検査ではじかれます。

const n = '3'; // おや？
const m = 4;
console.log(n * m); // 文字列と掛け算してしまっている！

実はJavaScriptではこのコードは意図したとおり(?)12を表示してくれます。これは静的型検査がないかわりに実行時に必要に応じてキャストしているためです。

しかし、もしnが外部からの入力だったとしたらどうでしょうか…？

const n = await readFile('hoge.txt', 'utf8'); // hoge.txtから読み込んでいるけど…
const m = 4;
console.log(n * m); // 数値で掛け算できている保証はない

これはごくカンタンな例でしたが、もっと巨大なコードになっていくと、いちいち調べるのは大変です。そこで、型をつけて検査をしてエラーをはじきます。

型検査

静的型付け・動的型付けとは？

• 静的型付けはプログラムを実行する前に型をつける
• 動的型付けはプログラム実行時に型をつける

TypeScriptは静的型付けをするので、静的型付き言語です。TS→JSのコンパイル時に型チェックが行われます。コンパイルが通れば実行時エラーが起きないことが保証されます*1。

型推論

静的型付き言語であっても、必ずしもすべてに型を書く必要はありません。たとえば目視でも「1 + 2はnumber型だ」という"推論"ができます。二項演算子なら、その左辺と右辺の項、演算子の情報さえあれば推論できます。この推論機能によって、型アノテーションを省略することができます。ただし型推論の目的は型アノーテーションの省力化ではありません。

もし型推論がなかったら、次のように書かなければなりません(下のような構文はそもそもTypeScriptにありませんが)。

const a : number = ((1 + 2 : number) * (3 - 4 : number) : number)

さすがにこれは過剰です。演算子は型が言語仕様から決まりきっているので、オペランドとの組み合わせが決まれば返り値の型は一意に決められます。型アノテーションが必要になることはありません。

関数の推論についてはややこしいので、参照記事をご覧ください。

TypeScriptの型推論詳説 - Qiita

ここで重要なのは、型推論は静的に行われることです。静的型検査を行いながら推論をしていくので、型推論によって不要な型アノーテーションを消したからといっても実行時エラーは起きえません。型推論と動的型付けはごっちゃになりがちなので、気をつけてください。

参照

TypeScriptの型推論詳説 - Qiita

*1:ただし、TypeScriptはJavaScriptのスーパーセットで、型がないところは勝手にany型がつけられて検査時にエラーが出ないため、適切な型付けをしていることが前提ですが

就活を振り返る

2018年(学部3年) 4月 院進以外に、就職という道があると気がつく(院には当然進むものだと思いこんでいた)

5月 院進と就職で悩み始める

6月 就職しようと決める

〜12月 「自己分析」とか「業界研究」とか何すればいいか分からないし、部活が忙しくてやる暇がない

1月 近所でやってたインターンや説明会に参加する

2月 就活を始める。

企業ホームページの採用情報のところから直接応募するスタイルを取った。就活サイトに登録したり、説明会に参加したりしていなかったため、手当たりしだい応募する形になった。

• C社 課題選考通る→一次面接を受ける→お祈り
• P社 書類選考すら通らず
• C社 選考通る→いつまでもメールが返ってこなかったので東京から帰る途中に「面接は明日いかがですか？」来る→無理だったので断る
• C社 ウェブテスト受ける→一次選考→お祈り
• D社 一次面接(Google Hangout)を受ける→二次面接へ→お祈り
• H社 書類選考通る→一次面接(ウェブ面接)を受ける→最終選考を受ける→お祈り
• L社 課題選考を受ける→一次面接(現地)を受ける→最終面接へ→内定！
• Y社 課題選考に通る→適性検査→一次面接へ

雑感

課題選考はとりあえず通るので、最低限は技術力を評価されていたと思います。しかし、とにかく面接が通りませんでした。後でも書きますが、チームで開発したことがなくて、どういうふうに働くか具体的なイメージができなかったのが要因の一つだったと思います。

最終的に、受けた中で一番年収が高い企業になりました。労働条件もとてもいいので嬉しい限りです。ただ、その環境を享受できるほど能力がある自信がないので非常に不安です。というか周りのレベルについていけるのでしょうか…？がんばります。

面接でたびたび「どういうふうにして情報を仕入れていますか？(技術系の流行の追い方みたいな意味だったと思う)」と聞かれたのが印象的でした。

「Linuxカーネルの役割をカンタンにいくつか挙げてみて」と言われて出てこなかったのが悔しかったです。プロセス管理とかメモリ管理とか分かるけど、それが「カーネル」という言葉と結びついていませんでした()。授業でもやりましたし、応用情報の勉強でもやっていてそのへんの知識はあっただけに、惜しいことをしました・・・

よく聞かれたこと

• 「将来的にどういうエンジニアを目指しているか？」
• 「チームで開発したことはあるか？」(これはメチャクチャ聞かれた！！)
• 「チームで働くとき、どうチームに貢献できるか？」

後悔したこと

チーム開発の経験についてほぼ毎回聞かれましたが、インターンやアルバイトなどに行っていなかったため毎回困りました。開発型のインターンに行っておくと有利かもしれません。インターンに参加しておけば、実際にチーム開発を経験できるので、チーム開発に向いていないのにプログラマになってしまう事故を防げます。

他に、自己分析をしていなかった…というかやり方が分からなかったのは良くありませんでした。自己分析をすることで、自分に合う環境を探す指標が作れるので、「何が好きか」「どう働きたいか」「何が嫌か」「どういう福利厚生が欲しいか」などをまとめるだけでもだいぶ違ったんじゃないかと思います。