最近の状況

ここのところブログの更新をサボっていたので近況報告でお茶を濁そうと思います。生存報告とかいう動画を投稿するYouTuberっぽいですね。

研究室とか

現在大学4年生で、今年の4月に研究室に配属になりました。前期のあいだは教科書の輪講を主にやっていました。

それから、前期は部活のほうにも週に2、3回顔を出していました。プログラミングと部活の両立はさすがに難しくてプログラミングのほうがおざなりになっていました…

あとは朝バイトに週3で入っていて若干体調が崩れてきています。なんとか立て直したい…

競プロ

4月からはじめた競プロですが、このあいだセールをしていたので螺旋本を購入しました。今は半分くらいまで終わりました。

ここのところ思っているのが、競プロは数学とかなり似ているな、ということです。発想力がなければ解けない問題は、数学と同じで「この問題、あの問題の解法で行けそうじゃないか？」というくらいまで量をこなし知識をつけるしかない気がします。そのため、ABCのDを埋める作業を螺旋本と並行してやっています。センスがある人はぱっと解法が浮かぶのでしょうが、僕にはムリです…

彼女ほしい

ああああああああああああああああああああああああああああああああああああああああああああ彼女ほしいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいい

スターリンソートをJSで実装してみた

スターリンソートなる、「整列されていない要素を"粛清"することでO(N)でソートを実現する」というネタが盛り上がっているようなので、便乗して書きました。

実装

まず、空のソート結果を格納する配列を用意します。そして、リストを先頭から見ていきます。ソート結果配列の末尾がリストの要素より小さければ、ソート結果にリストの要素を追加します。

const stalinSort = arr =>
  arr.slice(0).reduce((acc, a) => (acc.length === 0 || acc[acc.length - 1] <= a ? [...acc, a] : acc), []);

スターリンソートの開始位置を変えてみる

このスターリンソートは、[100, 1, 2, 3, 4, 5]のように最大値が先頭に来てしまうと残りの要素がすべて粛清されてしまうという問題点があります(他にもあるやろ！)。そこで、開始位置を変えることで、得られる配列の長さを最大化してみようと思います。

これは「最長部分増加列」を求める問題と同一になります。ちなみに、最長部分増加列を求めるにはO(NlogN)かかるのでスターリンソートのメリットがなくなります。本末転倒ですね。

const bound = comp => (arr, key) => {
    let s = 0, t = arr.length;
    while (t - s > 1) {
        const mid = s + Math.floor((t - s) / 2);
        if (comp(arr[mid], key))
            s = mid;
        else
            t = mid;
    }
    return comp(arr[s], key) ? t : s;
};
const lower_bound = bound((a, b) => a < b);
const upper_bound = bound((a, b) => a <= b);

const longestStalinSort = arr => {
    const dp = [];
    for (const item of arr)
        dp[lower_bound(dp, item)] = item;
    return dp;
};
console.log(longestStalinSort([100,1,2,100,3,4,5]));
console.log(longestStalinSort([1,3,5,2,4,6]));

ICPCに参加して

経緯

4月に研究室の同期から「ICPCに参加しない？」と誘われ、競プロを始めました。そこから約3ヶ月での参加だったので、かなり急ピッチでした。

大会感想

練習ではC、Dも解けていたのですが、本番は焦りと緊張もありBまでしか解けませんでした。

終わったあとにほかのチームに聞いたところ、CもDも考察はおおよそ合っていたうえ、Bまではかなり順調に解けた分、悔しかったです。

全体としては大学内で6位でした。大学内1位(全体でも7位！)のこたつがめさんのチームは5完もしていて、格の差をまざまざと見せつけられました…

反省としては、3時間もの間、集中力を切らさないのは無理なので、甘いものを持ち込んで糖分を取りながら取り組むべきでした。

来年からは社会人なので出られませんが、今回の参加はかなり楽しかったので今後も競プロは続けていこうと思います。

Rubyでコードゴルフするためのtips

AtCoder Beginner ContestのA問題を1分で解くためにRubyを書いているのですが、そのときのTipsが溜まってきたので書いておきます。

入力編

まず入力を受け取るところです。ここを高速で書けるとだいぶ強いです。

a,b,c=gets.split.map &:to_i

1行で与えられた数値A B Cを受け取ります。

単に文字列を受け取りたいなら

s=gets

で構いません。

また、単にgetsとして1行読み込むと、その行を$_という変数で参照できるようになります。こうすると変数に代入する手間が省けます。

gets; p $_.count(1)

出力編

A問題で多いのはYes/Noを出力させる問題、数値を答えさせる問題です。

Yes/Noを答えるときは三項演算子を使うとカンタンです。ただし、他の言語と異なり、?と:の前後にスペースを入れる必要があります(入れなくていいケースもありますが、考える時間がムダなのでとりあえず入れるといいです)。

puts true ? "Yes" : "No"
puts true ?"Yes":"No"

Rubyでは文字列リテラルのほかにシンボルというものがあり、こちらでも同様に出力できます。ここでは:の前のスペースは不要です

puts true ? :Yes: :No
puts true ?:Yes: :No

数値の出力にはpというメソッドを使えます。putsより文字数が削減できます。ただしpで文字列を表示しようとすると、クォーテーションごと表示されてしまうので使えません。

p 42

便利なメソッド・Tips

• "文字列".split 文字列を空白で分割する
• [配列].map マップ関数。非常によく使う
• "文字列"[/正規表現/] 文字列中で正規表現にマッチする部分を返す
• "文字列" =~ /正規表現/ 文字列が正規表現にマッチするか判定する
• "文字列1".count("文字列2") 文字列1のなかで文字列2が出てくる数をカウントする
• [Enumerable].min 数値の配列などで最小値を返す

このあたりはよく使います。

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

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

ちなみにこれが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ヶ月で、今までよりもロジックを慎重に考えるようになりました。

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