CompetitiveProgrammingAdventCalenderの19日目の記事です。この記事では自分の好きなアルゴリズムやそれを使うSRMの問題なんかについて書いていこうかと思います。講座的な記事というよりは単純に自分の思うままに好きな内容を書いた読み物的な記事になるかと思いますが、Topcoderをやってる人なら多分楽しめるんじゃないかと思うので最後までお付き合いください。（特に断りが無い限り問題は全てDiv1の問題です）
まずはアルゴリズムの王道ともいえるDPから。競技プログラミングでもやっぱりDP系の問題が一番多いんじゃないんでしょうか。特にTopcoderではDP率が高いんで正直DPさえできればRedcoderになれるんじゃないかっていう。
そしてここに書くぐらいなんで自分ももちろんDPが好きな訳です（結構ぽろぽろDPの問題落とすんで決して胸を張って得意とも言えないけど）。自分で何となく問題を考えてみると大体DPに帰着できる問題になっちゃいますしね。DPの基本的な考え方とかはchokudaiさんの最強最速アルゴリズマー養成講座にも記事があるんで「DPについてまだどうも良く分からない」という人はそちらを参考にするといいと思います（ここを読んでる人で読んでない人もいないと思いますが）。
後は最初にも書いたようにとにかく色々な問題があるのでとにかく解きまくって慣れるしかない部分もあるとは思います。他の人のコード読んだりしてるうちに最初はもやもやとしてたのが段々霧が晴れたように理解できるようになってくると思います。DPが分かるようになるとTopcoderライフが全く変わる…と思います。
さて、DPに関する好きなSRMの問題ですが、DPで巧妙な問題な問題はいくらでもあるので、あえて簡単でシンプルな問題を選びました。SRM412Easy,ForbiddenStringsです。DPの入門にはうってつけの問題だと思うので是非トライしてみて下さい。（chokudaiさんの講座でもこれを例題に挙げれば良かったと思うのですが…）
問題概要(ForbiddenStrings)
30以下の整数nが与えられる。A,B,Cからなる同じ文字が3文字続かない長さnの文字列の数を返せ。
続いては二分探索です。DPより頻度は少ないですがこれも使えるようになると大きいと思います。自分にとって印象深い二分探索の問題はSRM421Easy,EquilibriumPointsです。
問題概要（EquilibriumPoints）
1次元座標上に惑星がn(2<=n<=50)個あり、座標をx[i],重さをm[i]として与えられている。引力は惑星の重さに比例し惑星からの距離の2乗に反比例する。この時左右からの引力が釣り合う点を全て求めよ。
当時はDiv2Mediumとしてこの問題に挑んだのですが、多項式の解として求めようとしたりして本番中には解けずじまい。SRM直後にchokudaiさんに質問して二分探索で解けると言われた時は衝撃を受けました。ソートされた要素の探索としての二分探索は知ってましたが、こういう時にも適応できると知って世界が変わりました。SRM380Medium,CompilingDecksWithJokersなんかも二分探索を適用するとびっくりするぐらい簡単に解ける問題例ですね。
あと二分探索は、DP(SRM390Medium,PaintingBoardsなど)・最短路問題(SRM479Medium,TheAirTripDivOneなど)・フロー(SRM428Hard,FeudaliasWarなど)・2-SAT(SRM464Medium,ColorfulDecoration)・閉路検出(SRM524Medium,LongestSequenceなど)といった具合に色々なアルゴリズムと組み合わせた問題があるのも楽しいところですね。
二分探索の注意点は単調性がちゃんと成り立ってるかを確認することですね。ぱっと見で単調性が成り立ってそうでも実はそうではなく、FailedSystemTestが大量発生したSRM483Hard,Sheepのような問題もあるので。
これは二分探索よりもさらに頻度が少ないですが、三分探索が必要な問題が出たときにきっちり解けると嬉しいですね。三分探索の概念自体は二分探索を知ってすぐに調べたのですが、「凸性があるということは微分すると単調性を持つということだから、別に三分探索自体は必須ではないのでは？」と思ってました。しかし次に挙げるSRM426Medium,CatchTheMiceと出会ってその考えは打ち砕かれることになります。
問題概要(CatchTheMice)
2次元平面状にn(2<=n<=50)匹のネズミがいて、初期位置をxp[i],yp[i]、速度ベクトルをxv[i],yv[i]で与えられている。ある時間に、辺が座標軸と平行な正方形の檻を平面に降ろしてネズミを全てその内部に捕まえたい。正方形の辺の長さの最小値はいくつか。
この問題は別の解法もあるにはあるのですが、三分探索を使えば圧倒的にシンプルに解くことができます。詳しい解説は省きますが、「xy平面上に直線がいくつかある時、f(x):あるx座標における直線のy座標の最大値（最小値）とおくと、f(x)は凸性を持つ」という性質を見つければこの問題に三分探索を適用することが出来ます。
同じくこの性質を使うことで、三分探索でシンプルに解ける問題としてSRM276Medium,TestingCarやSRM240Medium,WatchTowerなどがあります。また、関数f(x)自体は凸性を持ちかつ微分可能ではあるけど、xが離散的な値しか取らない（整数だけとか）ために三分探索を適用しないといけない場合もありますね。
これはアルゴリズムそのものというよりも、それが適応できる問題でどういう風に辺や点を取るかを考えるのが面白いって感じでしょうか。長くなっちゃうので問題詳細は省きますが、TCO10R5Medium,LongJourneyやそれと似たような問題であるSRM492Hard,TimeTravellingGogoあたりが好きなダイクストラの問題です。
上に挙げなかった以外で好きなSRMの問題です。
KSubstring(SRM404Medium)
長さn(2<=n<=3000)の数列が与えられる。ある長さmの2つの互いに重ならない部分列の和をそれぞれS1,S2とした時、最も小さいS1とS2の差と、それを取る時の最も大きいmを求めよ。
単純にやるとO(n^3)となってTLEするものをちょっとした工夫でO(n^2logn)にするという、自分の中では競技プログラミングの王道かなと思う問題のタイプです。特別なアルゴリズムの知識も必要なく実装量も少なめなので良い問題かなと。結構昔に解いたのですが、当時に比べ色々と知識が付いた今でも変わらず良問に思えたのでここで紹介しました。
TheAlmostLuckyNumbers(SRM453.5Hard)
全ての桁の数字が4または7の整数をLuckyNumber,少なくとも1つのLuckyNumberで割り切れる整数をAlmostLuckyNumberと呼ぶことにする。a以上b以下のLuckyNumberの数を求めよ。(1<=a<=b<=10^11)
包除原理という、ちょっとした数学（算数？）の知識を使うことでパズルみたいに解ける問題で楽しかったです。この問題のwriterはVasylさんという方なのですが、自分はVasyl問題が結構好きだったりします（問題名の頭にTheが付いてたら大体Vasylさんだと思います）。好きという割には結構Vasyl回でボロボロだったりするんですけどね…
何というか本当に自分の思うままに書いただけで、初心者向けでも上級者向けでもなくまさに誰得だよって感じの内容ですが、ここまで読んでくれた方はありがとうございます。ここに上げた問題はどれも良問だと思うので、是非解いてみたり、あるいは他の人のコードを読んでみたりするといいと思います。では皆さん、素敵なTopcoderライフを！