色んなアルゴリズムを、用例を交えたりして駄弁る

公開日:2018-12-23
最終更新:2018-12-23

色んなアルゴリズムを、用例を交えたりして駄弁る

前置き

この記事はみす51代 Advent Calender 2018 23日目の記事です。

ここ最近、ひたすらゲーム創ってました。創ってて楽しかったし、無事完成して安心してます。冬コミで頒布されるらしいので喜んでます。

一方これは直近のAtCoderの結果です。はい、レートが重力に逆らえてません。今までは青い空を飛び回っていましたが、このままでは水色の海に落ちた後、しばらくして茶色の地面に激突するのも時間の問題でしょう。競プロをしてるとゲーム開発はしやすくなりましたが、ゲーム開発をしても競プロは精進出来ないらしいです。

以上は実話であり、公式記録(注:1)、専門家の分析(注:2)、関係者の証言(注:3)を元に構成しています。メーデー民も騒ぐような落下速度ですので、ここはひとまず対策を講じましょう。ブラックボックスを真水につけるが如く。

(注1 : レート)
(注2 : レート計算システム)
(注3 : 他の競プロer)

本題

茶番はさておき、この記事では、色んなアルゴリズムに関するイメージ及びおススメサイトを紹介します。1つでも興味を持てるアルゴリズムが出来てもらえたら、是非解いてみましょう。以下のサイトとかおススメです(AtCoderだと、どの問題にどのアルゴリズムがあるか分からないため)

なお独断と偏見と半日足らずの時間で、悲しみの向こうへと行きながら色々書いているため、これを読んでAtCoderなどのレートがバードストライクを起こしても責任は負いません(僕が鳥の方です)。

動的計画法(DP)

皆さんお馴染みのあれ。授業ではよく出てきますが、想像以上に色んな問題があります。「授業を受けるだけでは情報量が足りないなぁ」と感じられる素晴らしいジャンル(授業にはちゃんと出ましょう)。

色んな問題で使われる影響で、これが強くなれば解ける問題の量は膨大に増えます。安定してレートを上げたい人は真っ先にやりましょう。音ゲーの地力を上げるには二郎を食べる必要があるのと同様、レートの地力を上げるにはDPをやる必要があるのです(諸説あり)。

理論

実践

  • DP まとめコンテスト
    新年早々にあるコンテスト。お正月が暇な人は、暇つぶしに是非出ましょう。忙しい人も、可能な範囲で時間を空けて出ましょう。
  • Typical DP Contest
    上のコンテストの前身となるコンテスト。20問もありますが、まだ6問しか分かんないです。

フロー/二部マッチングなど

知名度が高い一方で、全体的な難易度もそれなりに高い。雰囲気は好きだけど、実際に実装するのは(よくわかんなくなるので)嫌いです。青色/黄色になりたいと思ったら、とりあえずこれは出来るようにしたい。

bit系

bit演算

低レイヤを扱う人、メモリ制限の厳しい組み込み開発とかで使われそうな印象の分野。
競プロ界で有名な某旅人さんは、(AGCなどへの出題傾向的に)多分これが好きな気がする。

半分全列挙

N=30~40のときによく使われる。
題材は基本、母集団全体にyes/noの全パターンを計算したら上手く行くけど、時間が足りないような問題で使われる。
手法は、母集団を二つに分けて、それぞれでyes/noの全パターンを計算 → 片方のパターンを元に、もう片方のパターンからmapや二分探索で探す感じ。
探すときにO(1),O(logN)に出来たら、問題は実質解けたようなものと言えるものはよく見る。(何やかんやその探すパートが一番きつい)

数学系

二分累乗法

a^bというものを考えたとき、bが異常に大きい場合は普通にfor文は回せない。
そういう時に使う。

フェルマーの小定理

数学苦手な人は、理論は放置して用途だけ覚えておいた方が良いランキングではかなり上。1/N は普通に計算できるけど、1/N(mod M)みたいな、よく分からない存在を計算するときに使われる。具体的な内容になると、数学科の群,環,体の話に入るらしいので、深入りは危険。

転じてAtCoderでは基本的に、N=100000のときなどに、50000 C 20000 みたいな場合の数を計算しないといけないときに普通に出てくる。具体的には、組み合わせの公式 nCk = n! / (k!(n-k)!)を上手いこと使うと何とかなる。

とりあえずは、1/n(mod m)か、nCm (n,mはでかい) を計算したいときは引っ張ってこよう。蟻本には実装とかちゃんと書いてあるよ。

中国剰余定理

Twitterでは大体中国幼女定理って言い換えてる人が多い。
まだ理論を上手く理解できてないので嫌い。

包助原理

2017年のAtCoderでは比較的出てきた印象。
全く解けなかったし理解も出来てないので大嫌い。

配列計算系(区間に対して四則演算とかいろいろやるやつ)

しゃくとり法

基本は区間の和の値をベースに、全通り試した最小(最大)値が欲しいときに扱う。これは意外と、知らなくても何とか実装しちゃって、その後「名前付いてたの」と言われる印象。でも難易度が上がるとやっぱりやヴぁい。

セグメント木(通称:セグ木)

区間最小値を求める問題でよく扱う。クエリ処理をしてくださいみたいな問題でよく出る印象。値の変更クエリがある場合、1ヵ所しか無ければ簡単に実装できる。

平方分割

区間最小値を求めたいけど、ある区間全部へ値を操作するときによく扱う。

BinaryIndexedTree(通称:BIT)

区間和を求める問題でよく扱う。しゃくとり法とは違い、クエリ処理系でよく出る印象。

ゲーム系

分かんない…分っかんないよ。ゲーム系の言ってることは一つも分かんないよ。ゲーム系の最適な行動、何が最適なのか分かんないよ。分かんない私には分かんないの!Nimってどういう問題で使えるの。暗記だなんてイヤだよ、次の出題でレートが下がるだけだよ。Grundyのどこが良いの、状態を数値に置き換える感じが全然つかめない!xorってなんなのどこからその閃きが来るの。Grundy数もどうやったらそういう発想が生まれるの。Grundyの日本語訳を調べたら口やかましい人だったよ!
分かんない分かんない分かんない分かんない分かんなーい!ゲーム系のことは昔から何一つこれっぽちも分かんないんだよ!

ゲフンゲフン取り乱しました。とりあえずわかんないです。
このセリフに既視感を覚えた人はこのアニメを見返しましょう。

おまけ

混ざってるから分類分け出来ない系

  • アルゴリズムの簡単なまとめ
    どんなアルゴリズムがあるかもっと知りたい初心者向け。この記事よりも良くまとまってるし、コンテスト中に、使えるアルゴリズムを検索するのに使えそう(使ったことはないけど)

(一部の人にはクエリ処理に関する解説と話していましたが、流石にレートがヤバいので急遽変更しました。ご了承下さい)

おしまい

こうならないように頑張ります。

明日は @ikarostech の「(全然決めて)ないです」だそうです。
聖夜に何を語ってくれるのか乞うご期待。

記事が少しでもいいなと思ったらクラップを送ってみよう!
131
+1
@25tomaの技術ブログ

よく一緒に読まれている記事

0件のコメント

ブログ開設 or ログイン してコメントを送ってみよう
目次をみる

技術ブログをはじめよう

Qrunch(クランチ)は、ITエンジニアリングに携わる全ての人のための技術ブログプラットフォームです。

技術ブログを開設する

Qrunchでアウトプットをはじめよう

Qrunch(クランチ)は、ITエンジニアリングに携わる全ての人のための技術ブログプラットフォームです。

Markdownで書ける

ログ機能でアウトプットを加速

デザインのカスタマイズが可能

技術ブログ開設

ここから先はアカウント(ブログ)開設が必要です

英数字4文字以上
.qrunch.io
英数字6文字以上
ログインする