この記事はCompetitive Programming Advent Calendar 2015の６日目の記事として書かれました。 この記事は、C++初心者が頑張って編み出した、C++初心者の競技プログラマ向けの実装テクニックを紹介するものです。 筆者自身がC++に詳しいわけではないため、仕組み等の解説は避け、「こう書けばいい感じに動くよ」みたいな部分だけを書いていきます。 「競プロでの応用例」という点に注目して読んでいただければと思います。 目次 ・range-based for（前菜） ・lambda式（メイン） ・コメントアウトの小技（おまけ） まずは、C++11の新機能を使ったテクニックから紹介します。 range-based for これはよく知られていると思います。以下のように書くとvectorとかmapとかを舐められるやつです。 for (型 変数名 : 舐める対象) 使用

昨日の記事の続きです。 Z algorithm 文字列が与えられた時、各 i について「S と S[i:|S|-1] の最長共通接頭辞の長さ」を記録した配列 A を O(|S|) で構築するアルゴリズムです。 例えば、 aaabaaaab 921034210 こんな感じです。 Z algorithmのテクニックはManacherとよく似ています。ですので、以下の解説記事を読む前に少し考えてみると分かるかもしれません。 さて、結論から言うと、Z algorithmのコードは以下のようになります。 A[0] = S.size(); int i = 1, j = 0; while (i < S.size()) { while (i+j < S.size() && S[j] == S[i+j]) ++j; A[i] = j; if (j == 0) { ++i; continue;} int k

昨日の記事の続きです。 Manacher 文字列が与えられた時、各 i について「文字 i を中心とする最長の回文の半径」を記録した配列 R を O(|S|) で構築するアルゴリズムです。半径というのは、(全長+1)/2です。 例えば、 abaaababa 121412321 こんな感じです。 結論から言うと、Manacherのコードは以下のようになります。 int i = 0, j = 0; while (i < S.size()) { while (i-j >= 0 && i+j < S.size() && S[i-j] == S[i+j]) ++j; R[i] = j; int k = 1; while (i-k >= 0 && k+R[i-k] < j) R[i+k] = R[i-k], ++k; i += k; j -= k; } このコードが何をしているのかを見ていきます。 と

この記事はAdvent Calendar 2014の12/1の記事として書かれました。 はじめに KMP、Manachar、Z algorithm の３つについて書きたいと思います。 １アルゴリズム／１日で追記して行きます。 これらのアルゴリズムでは「求めたいものの特性を生かして、既に計算した結果を上手に利用する」という点で共通しており、いずれも「なるほどなぁ」と言わされました。 この美しいアルゴリズムたちを是非紹介したいと思い、この記事を書くことにしました。 ・記法について |S|：文字列 S の長さを表す。 S[i,j]：文字列 S の i 文字目から j 文字目までを取り出した文字列を表す。 KMP ※これは正確にはKMPではなくMPです。KMPについてはこちら。 文字列 S が与えられたときに、各 i について「文字列S[0,i-1]の接頭辞と接尾辞が最大何文字一致しているか」を記

幾何コンに参加してました。 幾何苦手なんですが、３位でしたおどろき A,Bはほとんど幾何の実装力要らなくて、Cは凸包が書ける程度の幾何力しか要らなかったし、ICPCを意識した幾何のコンテストというよりは幾何を題材にしたコンテストという感じだった。ただしDはICPCっぽい。 A えっ ソートするだけ・・・？ B 右側と左側に分けて重み付き二部マッチング 辺の重みは、対称形にする時と二つともY軸に持ってくる時のminを取る。 右側と左側の個数が釣り合わない場合は「Y軸に移動」みたいな頂点を作る。 最初、同じサイド同士の２つを対称に並べることに意味があると思い込んでいてかなり時間を取られた・・・両方Y軸に持ってくるよりも良くなると思いこんでた・・・ C ちょっと考えると凸包を取ればいいと言うことが分かる。 x座標が区間に含まれる辺を見つけて来て、上下関係を調べたりする。 頂点の削除・二分探索が必

SRM580のwriterをしていました。 点数はsolveまでの時間にも依存するので必ずしも600が激ムズという訳では一応ないです。 Div2 Easy 概要：区間が与えられるので重なってるペアの個数を数えよ。 解法：区間が50個しかないので全ペアについて試す。 Div2 Medium, Div1 Easy 概要：うなぎが区間として与えられるので、２点を選んでそれらのうちどちらか又は両方を含む 区間を最大化せよ。 解法：tから２つ選ぶのを全て試す。 Div2 Hard 概要：コストまたは通れないマスが書かれたgridがあるので、うまく横方向の壁を置いて左上のマスから下の段までの上移動を使わないpathのコストを最大化せよ。 解法：dp[i][j] = i段目に初めて到達したマスが左からj個目である時のコスト Div1 Medium 謝罪：TCでO(N^2)という制約はこういう入力にするし

薄々感づいてた(or確信してた)人もいると思いますが、SRM570のwriterをやっておりました。 問題を調整してるうちに変則セットになりました。すみません・・・ CF頑張ってください！ まあまあ、とりあえず簡単な解説でもどーぞ Div2easy N本の箸の長さが与えられるので、同じ長さの箸のセットを何個作れるか。 ソートしてペアを取っていくなど。 Div2medium N個のコマンド「a[i]歩進んでa[i]*90度右に回る」からなるメソッドAをT回繰り返したときの座標を求めよ。 各コマンドをO(1)くらいで処理しながら露骨にシミュレーションすれば良い。 最近はD2mを簡単にしようという動きがあるらしく、簡単にした。 Div2hard Div1mediumの簡単バージョン(設定わりと違うけど)。サーバがどうとか書いてあるけど要するに、 ある木の部分木の個数を求めよ。 典型問題っぽい雰囲