4月に研究室の同期から「ICPCに参加しない？」と誘われ、競プロを始めました。そこから約3ヶ月での参加だったので、かなり急ピッチでした。
練習ではC、Dも解けていたのですが、本番は焦りと緊張もありBまでしか解けませんでした。
終わったあとにほかのチームに聞いたところ、CもDも考察はおおよそ合っていたうえ、Bまではかなり順調に解けた分、悔しかったです。
全体としては大学内で6位でした。大学内1位(全体でも7位！)のこたつがめさんのチームは5完もしていて、格の差をまざまざと見せつけられました…
反省としては、3時間もの間、集中力を切らさないのは無理なので、甘いものを持ち込んで糖分を取りながら取り組むべきでした。
来年からは社会人なので出られませんが、今回の参加はかなり楽しかったので今後も競プロは続けていこうと思います。
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
"文字列".split 文字列を空白で分割する[配列].map マップ関数。非常によく使う"文字列"[/正規表現/] 文字列中で正規表現にマッチする部分を返す"文字列" =~ /正規表現/ 文字列が正規表現にマッチするか判定する"文字列1".count("文字列2") 文字列1のなかで文字列2が出てくる数をカウントする[Enumerable].min 数値の配列などで最小値を返すこのあたりはよく使います。
競技プログラミングを始めました。今日、人生ではじめてコンテストに参加もしました。やっていて思ったことをいくつか書こうと思います。
ちなみにこれが600記事目ですが、特に特別なことはしません(いつもどおり)。
実は競技プログラミング自体は高校生のころから学んではいました。ただ、入門書として「プログラミングコンテスト チャレンジブック」・通称"蟻本"を選んでしまったのが間違いでした。そのせいで何度も蟻本で挫折をして(高校1年生の数学の知識で理解できるわけがなかった)、「入門書を読み通すことすらできないんだから競技プログラミングの世界はすごいなぁ…」と思いながら撃沈しました。
それから時が経ち、大学に入って研究室の同期とコンテストに参加することになりました。正直、挫折の経験があったので、当初あまり乗り気ではありませんでした。しかし、ゼミで競技プログラミングに取り組むようになって、「あれ？蟻本の前半のほうだけでも問題解けるんじゃん」と気が付きました。
そうなんです。蟻本を入門書と思ってはいけないのです。あれの前半は確かに基本的なことの解説をしていますが、後半になるにつれて超上級者向けの内容になっていきます。つまり、蟻本はどちらかといえばドキュメントに近い性質の本になっています。この事実を知らないままいたことを今かなり後悔しています…
すでにゼミでABC(AtCoder Beginner Contest)という初心者向けコンテストの過去問に取り組んでいたので、問題の傾向・環境構築などに慣れた状態で参加しました。今回はA問題からD問題まで解けて、パフォーマンスが1255でした。初心者に毛が生えた程度の実力という感じですね。
さて、僕は全体で何位だったかというと、5000人中1000位でした。初心者向けコンテストとはいえ、蟻本に挫折した僕でさえ上位1/5に食い込めました。
これがこの記事で一番いいたいことです。「蟻本を入門本と思わないでくれ」。たしかに、前半部分は読んだほうがいいです。しかし、後半(特にグラフ以降)は初心者のうちは要りません。前半の内容だけでABCでDまでは解けるのです。
では、どのような順序で入門すればいいのでしょうか？僕が思うのはこんな感じです。
まず蟻本の前半を読みましょう。そして、なんとなく「アルゴリズム」の感じを掴みます。そしたら、AtCoder Scoresで100点の問題を解いてみてください。正直、プログラミングの基本がわかっていれば100点・200点はカンタンに解けます。この辺を解くことで「競技プログラミングの型」を覚えてください。3問も解けば十分です。300点問題からはアルゴリズム力が必要になってきます。
過去問を解いてなんとなく呼吸がわかってきたら、環境を整えてモチベーションを加速させましょう。atcoder-cli(ディレクトリの作成・テストケースのダウンロード)とonline-judge-tools(テストの自動実行)がオススメです。
環境も整えてマクロを作り出したら、いよいよコンテストに出てみましょう。ここまでちゃんと準備ができていればコンテストをそこそこ楽しむことができます。
競技プログラミングに取り組みはじめて1ヶ月ちょっと経ちます。そのなかで、「アルゴリズム」を考える力がついてきました。ここでいうアルゴリズム力は、「問題の解法」つまりロジックを考える力のことです。この1ヶ月で、今までよりもロジックを慎重に考えるようになりました。
「アルゴリズム力」といわれて「二分探索などを知っていること」だと思いこんでいる人は損しています。アルゴリズム力はロジックを組む力なのです。
「ゼッタイにこういうライブラリあるだろ」と思って探したんですが、なかったのでここに書いておきます。ライブラリ化はするまでもないですが、たびたび使うので…
// 自然数列. [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の一側面を取り上げただけであり、ESLintのメリットのごく一部にすぎません。
このような悲しい勘違いをこれ以上被害が広がる前に撲滅したいと思います。
続きを読む