競技プログラミングのための音楽

こんにちはきゃたぱるです。キャットアッパーです。

競技プログラミングをする時にオススメの作業用BGMを紹介します。

クラシック編

作業用BGMを聞きながら参加できる競技プログラミングは問題文が日本語でないものが多いです。すると歌詞付きの曲や、ポピュラー音楽だとReadingの妨害になることがあります。クラシックの曲は使われる楽器の音や流れのマナーがいい感じに穏やかなのでコンテスト序盤に役立ちます。長い曲が多いので、一曲だけでコンテスト全部をまかなえることもあるでしょう。注意点として、人によっては飽きるということです。

ボレロ

ボレロ/モーリス・ラヴェル【ミューズ交響吹奏楽団】 - YouTube

ボレロはおよそ同じ戦慄が100回以上繰り返されてゆるやかにクレッシェンドしていく曲です。問題の読み始めにほそぼそと曲が始まり、コンパイル成功時にはオーボエが鳴り始め、SubmitしてACの表示が出ると同時にシンバルが鳴る。このような流れをイメージすると調子が乗ってきてスムーズに問題が解けます。

新世界より　第三・四楽章

「新世界から」第3楽章 - YouTube

普通に曲を嗜むときは、第一楽章から聴くほうが良いのですが、BGMとしては第三楽章くらいから始めて聴いたほうが良いと思います。第四楽章の有名なフレーズに8分程度で到達するので問題文を読んで理解するのにちょうど良い時間でしょう。第四楽章の中盤のくるくるまわるところは頭にじんじんきて全完のちからを与えてくれます。

「惑星」より「火星」「木星」

組曲「惑星」より「火星」 ホルスト - YouTube

「惑星」の中で有名な２つです。「木星」を知らない人はいないでしょうから、こちらの方がより確実に調子を整えてくれるでしょう。「火星」も終盤あたりが良い感じ（小並感）なのでお勧めです。

交響曲第9番

ベートーヴェン 歓喜の歌 交響曲第九番 Beethoven Symphony No 9-video ...

年末のコンテストとかに良いでしょう。すこし短めなのでコンテスト中盤辺りにかけるのがお勧めです。展開が速いので思考のペースを曲に合わせるのがやや難しいです。全完した後や、もうやることがなくなった時に喜びの表現としてこの曲を聞くのもよいでしょう。

インストゥルメンタル編

クラシックもインストゥルメンタルですが、もっとポピュラー音楽よりのインストゥルメンタルにも違った良さがあります。ズンチャズンチャと踊るために作られた曲だったり、ヒーリングのために作られた曲だったり、いろいろな用法用量がありますので、自分にあった曲を探すのもよいでしょう。今回は曲名ではなくて作曲者、もしくは演奏者を紹介していきます。

Jazztronik

Jazztronik - set free - YouTube

ミキサー以外のメンバーがぐるぐるしている様々な雰囲気の曲を作るJazztronikです。ピアノ色が強い曲から、最近ではポップな曲も多いです。多くあるアルバムの中から自分の好みのテイストの曲を探してみてください。インストだけではないので、いろいろ試すとよいでしょう。

姫神

神々の詩 姫神 大地の風景 - YouTube

ヒーリング・ミュージックでは有名な姫神です。コンテスト開始前とかに聴くと落ち着けてよいでしょう。

DEPAPEPE

DEPAPEPE ONE - YouTube

ギターで歌うDEPAPEPEです。軽快で明るい音を爪弾くので、コンテスト中のテンションの調整の妨害に鳴ることはありません。いくつかクラシックの曲もDEPAPEPE調にアレンジしてカバーしているので、そういうのが好きな人にもお勧めです。

ナニワエキスプレス

SESSION'83 NANIWA EXPRESS 「RED ZONE」 '83 ...

上方フュージョン、ナニワエキスプレスです。テンポがよくうるさくない、良い感じ（小並感）の曲調です。

池田亮司

池田亮司 + / - [ the infinite between 0 and 1] キュレーターインタビ ...

電子音楽の人です。0と1がビンビンする感じが頭にじんじん来て全完まちがいなしでしょう。作業用BGMにすごく適している曲が沢山です。

J-POP編

あまりお勧めとかないです。皆さんの好みの楽曲を聞くのが一番だと思います。終盤辺りにかけるとアクセルがかかって良いのではないでしょうか。アニソンがJ-POPかどうかは怪しいですが、アニソンとかも好きな人には良いとおもいます。ぴょんぴょん。

その他

新谷良子

新谷良子-WonderfulWorld(歌詞字幕付き) - YouTube

いいよね～

まとめ

最後のやつはただの私の好みです。ごめんなさい。

BGMに向いてる曲、向いてない曲、いろいろありますが、その曲が好きで、コンテストに一緒に臨む心意気さえあればなんでも作業用BGMになりえます。上の方であげた、クラシックもインストも新谷良子も、人によってはBGMにならなかったりするでしょう。みなさんも自分にあったBGMを探してNice Music, Nice Contest.でがんばってください！プロ！

IOI参加記

IOI2014(たいぺい）に行ってきました。

参加記を書きます。

Day0 (7/12)

• 同級生は模試があるが、私は行かない。成田へ行く。
• Narrative Clipという30秒ごとに写真とってくれて、いい感じに場面ごとにまとめてくれるウェアラブルカメラを買おうとアキバに寄り道するも、置いてない。
• 適当に「ぷちます！」のグッズを買って成田に向かう
• 同じスカイライナーに代表が3人(@catupper, @joisino_, @HIR180)乗っていたらしい。なお車両は違った。
• 成田から集合ホテルへの道に迷う。歩こうと思ったけどバスを待つことにする。
• バス停でいろんな人に会う。来たバスには(@takayuta1999)が乗っていて、これにて代表全員集合。
• ホテルに着いたら、いろいろな説明を受ける。台湾にいきたいわん。
• ｼﾞｪｲﾎﾟｳｼﾞｭ先生によるOutputOnlyに関する前日講義
• phidnight先生による様々な問題に関する前日講義
• 晩御飯　おいしい
• ゆたぽよ先生はプロ
• hos先生によるJOIOpenContestやIOI過去問の解説
• 寝る

Day1 (7/13)

• 朝起きて朝ごはんを食べる。一番乗りだと思ったら随行員の人々が沢山いた。
• 来年以降NPCAからのJOIerが少なくなるねーみたいな話をする。時代はCTF。
• 空港へ行く準備をする。@HIR180さんがちょっと起きてこない。結局我々だけ先にターミナルへ
• queueで待っていると@HIR180さんと合流
• みんなで「今から出発するぜ」の写真を撮る。写真速報に載る
• 飛行機に乗る。すぐに寝る
• 起きたら「飯が欲しかったら主張してくれ」という旨が書かれた付箋がはられている。従う
• 昼飯（機内食）おいしい
• 到着まで時間があったので「アナと雪の女王」を観る。すごく面白い
• アナがエルサを探しに森に出て「私が怒らせてしまったから、夏を冬にしちゃったんでしょ。」というシーンの、言い方、演出、情景、流れなど、あらゆる要素が美しくて感動する。
• 台北に着く
• ホテル行きのバスが来るまで時間があるらしいのでコンビニに行く
• 台北のヴィヴァレッジ業のドンである黒松のドクペっぽい飲み物を買って飲む
• そんなことをしていたらバスが来てしまう。急いでバスに飛び乗る。
• 随行員を置いてけぼりにする。
• 到着後、ひとつ次のバスで随行員たちが来るとのことで、ホテルのロビーで待つ。
• 運営側のボランティアの人とお話する。Setを布教しようとしたら、随行員たちを載せたバスがやってくる。
• たのしいやで。
• IOIのリュックをもらう。中にTシャツ等いろいろ入っていて待遇が良い。
• 折りたたみ傘も入っているで。水泳キャップも入っている。お守りも入っている。
• 万能頭巾も入っている。帽子も入っている。かぶる物がかぶっている。
• いろいろな人が見える。
• 運営スタッフのうちガイドなどのスタッフ台湾の大学生たちの人々でした。台湾の女性はべっぴんさんが多いなと思った。
• 部屋のキーを授かって、部屋に荷物を入れる。
• 夕食へ向かう。ビュッフェでした。おいしい
• ガイドさんから「なんかカードキーのおとしものがあったっぽいよ。あんたじゃないよね？」と聞かれる。図星。
• 夕食のあとTallentShowというイベントがある。
• 交流イベントだったけどそこまで交流できなかったつらい。というのもあまり選手がいなかった。
• あとから知ったが、あらゆる選手がその時間CFに出ていたらしい。
• とりあえずつかれたから寝よう。

Day2 (7/14)

• 今日はプラクティスと開会式がある日。
• バスにのってプラクティス会場に行く。台北101が近くに見えて高い。
• 会場のロビーでけん玉交流をする。じょいしのさんがプロだった。
• プラクティス会場に入っていろいろ実施する。RBSTやLinkCutTreeを実装する。なお競技にはやくだたなかった模様。
• GreenTriangleMonsterのぬいぐるみをHIR180さんに借りてスモールマスコットとして申請する。
• 昼ご飯。おいしい。
• 開会式。ねむたい。
• 選手紹介で"Japan！"「いぇーい！」をやる。
• 本当は手をふっただけ。
• 闇のQuarantineの始まり。IOIerたちはネットが使えなくなる。
• DanceNightというイベントがあったが文化の違いのためご遠慮。
• 寝る。おやすみ。

Day3 (7/15)

• 競技一日目
• 緊張する。
• 金を取らなければならない個人的な理由があったのですごく緊張する。
• 競技が始まる。うぉー難しい
• 二問目Wallが簡単そうなので解こうとする。解けない。むずかしい。
• 一問目Railの56点が実装は大変だが取りやすそうに見えたので解く。バグを埋め込んでちょっと時間を取られる。
• もう一度Wallを見ると、「あっこれMIT6.851のTIME TRAVELで見たやつだ」ってなる。100点を取る。
• Scott Wuと目が合う。
• 三問目Gameの部分点が簡単だったので出したらとれた。42点
• 部分点の大きさからRailのほうが簡単と思い全完を狙いに行くが時間切れ。
• あーこれは金難しいなーとなる。
• なんか日本から部員が応援してくれていたという情報を得て俄然やる気が出る。これは金を取るしかない。
• 台北市内を観光。でかい本屋に行く。台湾語のゆるゆりを発見。
• おいしいディナーを食べる　他国とも交流　折り鶴をあげる　じょいしのさんがプロだった
• かえって寝る。おやすみ

Day4 (7/16)

• 遠足
• イラン市の文化体験村みたいなのに行く。コマをつくる。
• ポーランドのチームのひとに凸ってPOIの翻訳はよというクレームを入れる。最新の問題だから仕方ないねとのこと。
• ゆたぽよ先生がシャボン玉をおいかける。動画に収めたいくらい素晴らしい光景だった。
• イラン市の歴史博物館に行く。他国と交流して写真とか撮る。
• イラン市と台北市をつなぐ世界で2番目に長いトンネルを通る。
• バスの中で韓国チームと仲良くなる。ルービックキューブとかjubeatは交流に使いやすいぜ！
• 「いやぁ筐体はプレイしたことあるんだけどiPadでやったことはないんだよねー」と言っていた彼が私のハイスコアを上回るスコアでプレイし終わったあとに記録を残さないように一時停止ボタンを押す動作の滑らかさを僕は忘れない。
• 夜はGameNightというのがあったが面白くなさそうだったので台湾の人々とお話をする。英語はできなかったけど漢字で会話できた。漢字がかけてよかったー！
• みんなでプールに行く。ぬれる。
• 寝る。おやすみ

Day5 (7/17)

• 競技二日目
• 今日は良い点を取らないと金がとれないので超緊張。
• 実は案外緊張していない。むしろそれが逆効果だったのかもしれない。
• 三問目Holidays　これは見るからに良問！答えはわからないけどすごくイイ問題だぞ！と思う。だけど答えはわからない。簡単な部分点を取る。47点
• 一問目Gondolaたくさん小課題があるけど簡単なので普通に解く。バグバグしながら100点
• Scott Wuと目が合う。
• 二問目Friends　最大安定集合ってNPクラスやないかーいと思いながらグラフの特殊性を探るも無理。なんかフローを使えば解ける部分点が見えた。がんばってフローを組む。69点
• 時間切れ
• 金を取れなかった！ごめんひろむ！
• ご飯を食べたあとに解析をする。解法をみて目からうろこ。今回のIOIは良問ぞろいだと思った。
• 台北101の地下一階のフードコートで東京カレーを食べる。麻婆臭豆腐もすこし食べる。うぎゃぁ
• 台北IOIの展望階に登る。感動的眺め。
• タクシーに乗ってホテルに帰る。すぐ寝る。おやすみ

Day6 (7/18)

• 遠足
• 遊園地に行く。絶叫マシーンにのるも「あっこれ、ひらパーのほうが楽しいわ」ってなる
• けど最後にのったフリーフォールジェットコースターが楽しすぎた。
• そのあと隣接のウォーターパークに行く。雨が降ってきたけどプールだし関係ないね。
• 大きな波を発生させるプールに入ってむっちゃ流される。
• むっちゃ疲れる。
• 晩御飯を食べる。別格美味しかった。
• ホテルに帰る。じょいしのさんとアイマスなどのお話をする。一番日本語を喋ったシーン。
• すぐ寝る。おやすみ。

Day7 (7/19)

• 閉会式がある日
• 閉会式でいろんなパフォーマンスがある。おもしろい。
• 日本代表みんなメダル獲得おめでとう！
• 最後に満点が3人前に出てカッコ良かった。会場全体スタンディングオベーション。
• この光景は一生忘れないであろうくらい、素晴らしい光景であった。
• 台北師範大学にいってFarewell Party
• 韓国選手と99というトランプゲームをする
• スーパーボールすくい、ピンボール、綿菓子、折り紙などいろいろした。
• 太極拳もやりました。たのしかった。
• 韓国選手達と「昨夜そっちの部屋にいったらもう寝てたから今夜遊びに行くわ」「おｋまっとるで」という約束をする。
• よるホテルに戻って韓国選手達とトランプやjubeatなどする。ダウトとジジ抜きをしました。
• おそくなったので寝る。おやすみ。

Day8 (7/20)

• 日本に帰る日
• 最後の朝ごはんを食べる。おいしい。
• さようなら台北。さようならIOIer。
• 帰りも「アナと雪の女王」を観る。
• 成田について、このあとIMCに行くゆたぽよ氏とお別れ。
• ほかの選手団とも解散。
• スカイライナーでhosさんとフラクショナルカスケーディングの話をしてさようなら。
• さようなら世界。
• return 0;

などなどいろいろありました。

みなさんの声援のおかげで銀メダルとれました！みんなありがとう！夏期セミナーに行くので会える人は会いましょう！。

あと、これからIOIを目指す人のために、おすすめ書籍を幾つか並べておきます。あくまで私が便利だと思った本で、人によって向き不向きがあると思うので、適当に手にとって観ていただければ幸いです。

Introduction to Algorithms

プログラミングコンテストチャレンジブック [第2版]　?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

苺ましまろ 5 (電撃コミックス)

コンピュータ・ジオメトリ―計算幾何学:アルゴリズムと応用

アルゴリズムデザイン

JOI春合宿2014参加記

第26回IOI日本代表の選抜をするJOI春合宿に行ってきました。

Day0 (3/19)

• 午前中に終業式があったので、それに出なければならなかった
• 終業式中にJOI予選に参加しただけで表彰される謎イベントがあってつらい
• 新幹線で会場まで行く
• DEGwer氏が「@各位　代表おめでとうございます」と初日からハラスメントをしていた
• プラクティスで既出の問題を解く
• 去年のプラクティスから引き続き出題された「一緒に足し算」が相変わらずReadingHard
• 全完したあとはshortcodingしてたけどWAしか出なくて冷える
• そんなに冷えていない
• hosさんによるBIT講義があった　きっと明日BITが出るだろうと思った
• 自己紹介で台湾においしいお茶を飲みに行くといってしまったので代表に選ばれないといけなくなった

Day1(3/20)

• 朝6:00起床　皆が3完するなか0完する夢を見る　実に悪夢であった
• 6:30頃にレストランにいったが既に人がいてびっくり
• 競技前はプレッシャーのようなものに押しつぶされていた　首の後が冷えていた
• 競技が開始　どうやら4問セット
• 順番に問題文を読む　競技についての諸注意に忠実に従って滑り出し好調
• リアクティブの問題が簡単そうなので解く　AC
• 反転数を数えるっぽい問題が出る　やはりBITの問題が出た
• しかしWA　30点分の部分点を得たので誤解法ではないと思った
• すぐにコーナーケースを見つけて、テストケースが節穴だと悪態をつく
• コーナーケースを見つけても正しい解法が思いつかなかったので他の問題を解く
• ダイクストラっぽい問題があったので、ダイクストラしようと思ったが無理
• 心の底から「ダイクストラをしてはいけないDPをしよう」という声が届いたのでDPを組む
• AC
• 先ほどの反転数の問題も正しい解法を思いつき　AC　この時点で3完
• 残りの1問はさっぱり満点解法が思いつかず残り1時間になったので自明な部分点を得る
• Day1 340点
• たかゆた氏は普通に二時間半で全完していてつよい
• どうやら4完が2人っぽい　これは代表落ちワンチャンだなーと思う
• オリセンに帰ってutatakiyoshi氏による行列の話　線形回帰がよくわからなかったので質問しようと思ったが質問し忘れた
• 夕食　おいしい
• 本日の問題の解説　解けなかった問題は平方分割でデータ構造無しで解けるらしくて力不足を実感
• 寝る

Day2(3/21)

• 6:00起床 今日はレストランに約1番乗り
• 競技前やっぱりプレッシャーにおしつぶされる　首の後ろが冷える
• 競技開始。順番に問題を読む　3問目はすぐに解法がわかったので組む
• 2問目も実験していたら解ける
• 1問目もよく考えたら解ける
• 全完であたたまる
• オリセンで二分決定グラフの話　最適な変数順序を見つける問題がNP完全なのかNP困難なのかよくわからなかったので質問しようと思ったが質問し忘れた
• 夕食　おいしい
• 解説　わかる
• 寝る

Day3(3/22)

• 6:00起床 レストランに長い列があってつらい
• 競技前プレッシャーにおしつぶされる　首の後ろが冷える　2日目を全完してるのでそこまで冷えない
• 競技開始。順番に問題を読む１問目はいつでも解ける気がしたので後回し
• 2問目は絶対にやばいので最後　消去法的に3問目からときはじめる
• 解けない
• いつでも解ける気がした1問目も誤解法でWAをだす　つらい
• 得点が0のまま競技時間が半分すぎる　代表落ちワンチャンだなと再び思う
• トイレにいって帰ってきたら天からコーナーケースが降りてくる
• 3問目AC
• 1問目もAC
• 2問目は解ける気がしなかったのでさっさと部分点を得る
• Day3 215点
• オリセンで理論的に高速なアルゴリズムの話　O(r^98)も多項式時間である
• 多項式時間で解けることはわかっているがアルゴリズムは明示的に与えられないものもあるのだと実感する　P対NP問題やべぇなとおもう
• 夕食　おいしい
• 解説　2問目は怖いデータ構造を使わずに分割統治だけで解けると聞き便利さを再確認する
• 寝る

Day4(3/23)

• 6:00起床 レストランにいままでに無いくらい長い列があってつらい
• 競技前はプレッシャーにつぶされる　つぶれる
• 競技開始直後Constellation2という文字列が見えてひるむ
• 対話形式の問題もあって、やはりDay4は手強いなと思う
• 3問目が予選に出てもおかしくないくらい簡単だったので解く　AC
• Constellation2は全く思いつかなかったので最後に時間が余ったら部分点を得ようと計画する
• 対話形式の問題はやはり実装量が多く大量にエンバグしてしまう　パズルでズルズル時間を消費してしまう　なんとかデバッグして40点獲得
• 残り10分前後でConstellation2をACできるわけなく0点
• Day4 140点
• 合計で995点で1000点に及ばずつらい
• オリセンで正規表現とStarHeight問題の講義　オートマトンと正規表現の間の変換アルゴリズムが面白かった　Star-Freeで正規言語を表現するのもパズルっぽくて面白かった
• 夕食　おいしい
• 解説　対話形式の問題の想定解は完全に盲点で　あーこれは解けなかったなと思う　
• Constellation2があざやかれる　しかも特に変なデータ構造も使わない
• 今合宿では　いずれの想定解もセグメントツリーを使わないことに気づき時代の変化を感じる
• ワードウルフをするなどして寝る

Day5(3/24)

• 6:00起床　平日なのでレストランの列は短い
• 本日からhiromu氏が参加　うれしい
• シュタイナー木コンテストがある　全然首の後は冷えない
• 頑張って焼きなましを組むも2時間しかなかったので高性能なものはできなかった
• GUI上で手作業でシュタイナー木を使っていた人々が高得点を得る　yokozuna氏が手作業だけで2位をとりやばい
• 表彰式がある　ねむたい
• 隣に座っていたey氏が問題を作っていたので解こうとする　解けない
• tozan氏にこの問題を教えると　FFTでとけるのではないかと提案される
• rngさん曰く典型らしい　有益な情報を得た
• 代表になったらしい　うれしい
• 限界難題ふぐ太郎君
• 夕食会でコーラ茶を飲む　混ぜないほうが美味しい
• 談話室でCFのFFTを使う問題を解く　doubleは重いfloatで何とか通す
• 寝ようとする
• なんか面白いゲームを発見してプレーしていたら2時間立っていた

Day6(3/25)

• 6:00起床 レストランのQueueはempty
• 適当に部屋を掃除して変える準備をする
• 絵を書いてアルゴリズムを当てるゲームが楽しかった
• ND勢で万豚記に行く　辛くないものを注文する　おいしい
• 辛いものを食べた人々は汗をかいていて異次元にいた　いつか辛いものも美味しく食べれるようになりたいと思う
• 新幹線の時間まで少しあったので新宿でSetをする　ハラスメントがやばい
• 帰る

まとめ

代表ありがとうございます

計算量のはなし

どうも華麗なるキャッツパーです。キャットアッパーです。
この記事はCompetitive Programming Advent Calendar Div2013, 12/7の記事です。

私は過去に、暇に任せてこのようなスライドを作ってしまいました。

有名アルゴリズムとそれの計算量について列挙するのが楽しすぎて作ってしまいました。後悔しております。

本記事では「計算量ってどうやって計算するの？」みたいな話を競プロの観点からします。
計算量とはなんぞやということについては上のスライドを読んでください。

計算量の種類

競技プログラミングで気にする計算量は2種類あります。最悪計算量と償却計算量です。
最悪計算量というのは、ある処理にどのような入力を与えても、それ以上に速い計算量になる、というもので、一種の上界です。競技プログラミングでは作問者が最悪計算量になるテストケースをかならず入れてきますから、これを指標に考えることが主でしょう。
償却計算量というのは、同じ処理をN回行った時に、1回あたりどれくらいの計算量になるかというものです。競技プログラミングではクエリ処理の問題でお世話になります。Union-Findでもこの概念が重要になってきます。
似たものとして平均計算量というものがあります。これは全ての入力パターンの平均をとったものです。償却計算量とのちがいは独立に行った時の平均をとるか、連続して行った時の平均をとるかです。

最悪計算量

最悪計算量の計算は容易です。ほとんどのアルゴリズムで、最悪な実行時間を与える入力パターンを自明に考えることができます。
基本的に全てのループを完全に処理すると考えて計算するとうまく行きます。足し算と掛け算で概算できます。
ただ、再帰関数は少してごわいです。ある入力パターンをあたえるとそれより小さめのパターンで同じ関数を呼び出すわけですから、ややこしいことになります。
基本的には、サイズNの入力を与えた時の計算量をF(N)などと置いて、関数方程式をとくことになります。

問1.以下のアルゴリズム(マージソート)の最悪計算量がO(NlogN)よりはやいか求めよ

まず、sort関数に長さNのリストを与えた時の計算量をF(N)、combine関数に長さの合計がXである２つのリストを与えた時の最悪計算量をC(A+B)とします。
それぞれを中の処理の計算量の和で表すと
F(N) = O(N) + 2 * F(N/2) + C(N)
F(1) = O(1)
C(X) ≦ C(X-1) + O(1)
C(1) = O(1)
こんなかんじです。
C(X) = O(X)であることは自明だと思います。というわけでそれを代入してFについて詳しくときましょう。
F(N) = O(N) + 2*F(N/2)
F(1) = O(1)
ここで、真面目に漸化式を解いてもよいですが、競技プログラミングするときに厳密な計算量は必要ありません。通るか通らないかが肝心なので期待する計算量を当てはめてみてうまくいくか確認するだけでよいでしょう。今回はO(NlogN)より速いかどうかしか気にしていないので、F(N)=O(NlogN)として代入して、左辺が右辺以上になるか確かめればよいです。
O(NlogN) ≧ O(N) + 2 * O( (N/2)log(N/2) )・・・①
O(N) + 2 * O( (N/2)log(N/2) ) = O(N) + O(N(log(N)-1)) = O(NlogN)
よって①は真
実践の場面ではO(N^2),O(N√N),O(NlogN)あたりを試してみればよいでしょう。

問2.以下のアルゴリズム(クイックソート)の最悪計算量がO(NlogN)よりはやいかを求めよ

さきほどよりスッキリしていて計算が楽に見えますが実はそんなことありません。マージソートはsortの中で再帰するsortに与える入力のサイズが決まっていましたが今回は未知です。
F(N) = max{F(A)+F(B)+O(A+B) | A+B = N}
F(1) = O(1)
さて、F(N)=O(NlogN)として代入して確かめてみましょう
O(NlogN)≧max{O(AlogA)+O(BlogB)+O(A+B)|A+B=N}
O(AlogA)+O( (N-A)log(N-A) )の最大値は微分すればわかりますが, A=1もしくはA=(N-1)のときです。ただ微分しなくても、AとBの対称性から、Aのとりうる値の端っこか真ん中のどちらかでF(N)が極値になるのだなということがわかりますので、3つを調べて結果を観ても良いでしょう。
A=1のとき右辺は
O(1log1)+O( (N-1)log(N-1) )+O(N)
O(1) + O(N)+ O( (N-1)log(N-1) )
これは明らかに十分大きいNでO(NlogN)より大きくなります。よってO(NlogN)ではありません。なおO(N^2)を代入してみるとうまく等号成立します。つまり最悪計算量はO(N^2)です。
なお、ここでいう「十分大きいN」というのが入力の制約の外である場合があります。そのときはその範囲内でO(NlogN)が成り立つことになります。そのようなことはあまり無いですが実践では注意しましょう。

問3.「木をマージする一般的なテク」の最悪計算量がO(NlogN)よりはやいか求めよ。

APIO2012の第一問「忍者の派遣」などで必要となるテクニックです。
ともかく、式を立ててみましょう。マージ関数に大きさNの部分木を与えた時の計算量をF(N)としましょう。
F(N) = max{F(A) + F(B) + O(AlogB)| A+ B = N, A ≦ B}
F(N)=O(NlogN)を代入してみると
O(NlogN) ≧ O(AlogA) + O( (N-A)log(N-A) ) + O(Alog(N-A))
クイックソートの時と同様に右辺を微分するとN = 2A(Aの値域の端っこ）のときに最大値を得ます。
3*O( (N/2)log(N/2) ) = O(NlogN)
よってうまく行きます。

償却計算量

償却計算量が高級に使われているアルゴリズムといえば、spray木やUnion-findやfibonacci heapですが、どれも有名なんでわざわざ計算量を解析するのは一度だけでよいでしょう。ただどれも難しいです。ここで説明するにはアルゴリズムから記述する必要があって面倒くさいので他のページをあたってください。fibonacci heapは日本語版wikipediaに詳しくかかれております。
この記事では上記のアルゴリズムの償却計算量解析によく使われる手法ポテンシャル解析を解説したいと思います。
ポテンシャル解析ではデータ構造の状態にたいして値を対応付けるポテンシャル関数というものを使用します。
ある操作をすることで実際の実行時間O(N)で状態をAからBにかえたとします。ポテンシャル関数をPとすると、このときの償却計算量はO(N)+P(B)-P(A)です。
このようにすると何が嬉しいかというと、たくさんの操作をしても、最初と最後のポテンシャル関数の値さえわかれば、あとは償却計算量だけで計算できるということです。つまり、たとえば償却計算量がO(N)操作をして、状態Aを状態B,C,Dを経て状態Eにしたとします。そのときの実際の実行時間はわかりません。しかし式を立ててみると
(O(?) + P(B) - P(A)) + (O(?) + P(C) - P(B)) + (O(?) + P(D) - P(C)) + (O(?) + P(E) - P(D)) = 4O(N)
整理するとなかのポテンシャル関数の値が打ち消し合って
O(?) + P(E) - P(A) = 4O(N)
つまり、途中経過がどうであろうと、最初と最後と、途中で行った走査の償却計算量の和だけで実際の実行計算量を求めることができます。このときもしP(E)-P(A)が充分小さいとすると実際の実行計算量と償却計算量を同じとして考えることができます。　うれしい！

問1.つぎのデータ構造(動的にメモリを確保する配列)に値を追加するときの償却計算量を求めよ。

URL:https://gist.github.com/catupper/7838399
pythonっぽい擬似コードですが、ようするに

• 予め確保していたサイズより大きくなろうとしたら、その二倍のメモリを確保してから値を追加する。
• そうでないならば普通に値を追加する。

つまり
n = 現在持ってる値の数
N = 現在確保しているメモリの数として

• n=NならばNを二倍にして値を追加
• そうでないならば普通に追加

という処理をするものです。
最悪計算量はもちろんO(N)です。前者のタイプだとO(N)かかってしまいます。しかし時にはO(1)なので償却計算量はもう少し小さくなるかもしれません。
ここで配列の状態Xに対するポテンシャル関数を以下のように定義します。
P = 2n - N
それでは、add関数の各場合について償却計算量を求めてみましょう。
n=Nの場合
実際の計算量は先ほど出したとおりNです
ポテンシャル関数の値は 2N-N から 2(N+1)-2Nになりますので償却計算量は
N + (2(N+1)-2N) - (2N-N) = 2
n≠Nの場合
実際の計算量は1でnが1増えます
1 + (2(n+1) - N) - (2n - N) = 3
よってどちらの処理も償却計算量はO(1)となります。
さて、何もない状態からX個値を追加した時の計算量を考えてみましょう。
ポテンシャル関数の値は0から2X-Nに増えていますので最大でX増えることになります。
add関数の償却計算量はO(1)ですのでX回行うとO(X)です。
よって実際の計算量はX+O(X) = O(X)ということになります。
これの平均をとると、やはりadd1回あたりの計算量はO(1)ということになります。やったね！

これがポテンシャル解析です。競技プログラミングにおいてはしゃくとり法のようなアルゴリズムの計算量解析に使えると思います。探索終了前と探索終了後のポテンシャルの差と償却計算量で考えるのです。

計算量が厄介な問題

最後に計算量をうまく考えないといけない問題をいくつか載せます。みなさんもぜひ、計算量を意識して問題を解いてみてください。
NPCAJudge#26 私を月に連れてって・・・再帰関数の最悪計算量の漸化式を解くとうれしい。
JOI春合宿2012,Day1　ビルの飾り付け2・・・例のマージテクです。
第19回POI Stage1 Well・・・あるところで償却計算量がわかると速いです。

セキュリティキャンプにいってきたよ

2013年セキュリティキャンプ中央大会にいってまいりました。ソフトウェアセキュリティ組でした。
1日目　Nicterとかハッカー検事のお話が聞けて嬉ピー
2日目　SSの専門講義　BOFとかFSBとかをDEPやASLRが効いてる中で実施するCTFっぽいことをしましたー
3日目　企業見学　LACに行きました　地球防衛軍でした。　任意のシェルコードを作るのを実施しました、できませんでした。
4日目　専講はAdobeの脆弱性をつくExploitのリバースエンジニアリング。　そのあとCTF　ヘーwwwイェーwwイェwwwwイェイェwwwww　
5日目　発表

たのしかったです。

楽しいと言えば

たのしいバイナリの歩き方

この本よみやすい
とくにセキュキャンでもやったAdobeAcrobat9.x系に対してROPしてるExploitの解析の章はすごくをわかりやすく解説しております。
程よい密度で初心者にもお勧めですー
一読の価値ありー

他人に読んでもらいやすいコードは書きにくいので書かない方が楽な木がする

どうもきゃたぅぱーです。きゃっとあっぱーです。
もうそろそろJOIの本選ですね。予選は見事に提出ミスしてしまいました。落ちなかったものの木の緩みが生んだものだと思います。
そうそう、最近木構造にはまっているんですよ。NPCAの部誌も木構造でかくつもりです。ただちょっと読みにくいかなーという木もします。
背筋ぴーん！
閑話休題

JOI本選が近いということで, AOJvol05を全完しました. どうせなら部の後輩とかのために解説とかも保存していうたほうが、便利かなという木もしまして、githubにて保存してました。みなさまもご活用くださいまし。https://github.com/catupper/AOJans/tree/master/vol05

NPCA Contest

どうもきゃたぱです。きゃっとあっぱーです。
NPCA Programming Contest Alphaがありましたね。この記事ではそれの解説をうｐしたいとおもいます。
元々は部員のJOI対策のために部内向けに考えていたコンテストなのですが、様々な理由でDiv1とDiv2にわけて校外にも公開して開催しました。
Div1の解説はsnukeさんがブログにあげていますのでそちらをご参照ください。
この記事ではDiv2の解説のスライドを掲載していきます。

Div2はJOI予選4完レベルを意識して作ったためDiv1に対してDiv5くらいの簡単な難易度になっています。
ほとんどやるだけなので、slideshareへのリンクと一言解説を付けるだけにしたいと思います。あしからず。

黒い板

最小値を求めるだけです。

スペルチェック

文字列を比較するだけです。比較にはstd:stringやstrcmpを使えばよいでしょう。

鉛筆狩

百姓を中心に考えれば、ただ最適な役人を選ぶだけになります。

世界史ネットワーキングサービス

ある要素が含まれている区間の個数を数えるだけです。

プール掃除

ソートして2つづつ区切る貪欲法です。

宿題

シミュレートするだけなのですが、残り時間が思い出すのに必要な時間より短い場合は、やらずに、次の休み時間が始まってから始めたほうが速いです。それを把握してシミュレートしないといけません。

約数スマッシュ

数学ゲーかと思いきや、与えられる数が小さいので全探索で十分間に合います。N以上M以下の整数について約数の個数を数えるだけです。

昼ごはん

典型的なナップサック問題です。動的計画法で解けます。この問題がJOI予選4番を意識した問題です。