サクサク読めて、アプリ限定の機能も多数!
トップへ戻る
大谷翔平
snuke.hatenablog.com
ダイクストラ法、正しく書けてますか? ダイクストラは少しのミスですぐ計算量が壊れたりするのですが、テストケースによっては意外に落ちにくく間違いに気づかないこともあります。 この記事では、よくあるミスとその撃墜ケースを紹介していきます。 この記事はどちらかと言うと問題準備をする方に読んでほしい記事です。 writerをする際は、ここで紹介する撃墜ケースをテストケースに入れるようにすると良いと思います。 SではなくTを始点にするという小手先技が考えられるので、逆向きバージョンも入れておくと尚良いでしょう。 ジェネレーターも置いておきます。 コード中の定数を書き換えたり入力で取れるようにしたり、出力形式を変えたりして使ってください。 念の為生成されたテストケースにもちゃんとvalidatorをかけて下さい。 目次 既に見た頂点のcontinue忘れ: 最大ヒープを使う: 負辺のあるグラフで使う:
前編はこちら 前編は汎用性も高い話題でしたが、後半は少しマニアックで雑学的です。 予習 全方位木DPについて予習します。 全方位木DP、有向辺に関するDPだと思うのが分かりやすい。 1. 青い矢印は普通の木DPで下から順に求まる 2. 根から出る矢印は全部求まっているので、根に入る矢印も求められる(ここの計算量改善に総和とって引き算とか左右からの累積和とかが出てくる) 3. 同様に赤い矢印を上から順に求めていく pic.twitter.com/p4bl6rXzGn— ꑄ꒖ꐇꌅꏂ🐾 (@snuke_) 2019年1月6日 補足として、以下の問題を解く具体的な実装も置いておきます。 N 頂点の木が与えられる。 頂点 v を含む部分木の個数を全ての v について求めよ。 制約:1 ≦ N ≦ 10^6 こういう、根を全部試して根付き木の問題を一括で計算する、的な状況で全方位木DPが活躍します。
この記事はCompetitive Programming Advent Calendar 2018の46日目の記事として書かれました(嘘) 最近、木上のアルゴリズムの面白い計算量解析が2つ話題になったのでまとめておきます。 予備知識 まず、https://web.archive.org/web/20150819082918/https://topcoder.g.hatena.ne.jp/iwiwi/20120428/1335635594 について復習します。 iwiさんのブログとは違う、より直感的な解析方法も紹介します。 以下の問題を考えます。 N 頂点の木が与えられる。 頂点 1 を含む頂点数 K の根付き木の個数を求めよ。 制約:1 ≦ K ≦ N ≦ 3000 典型的な木DPの問題です。 解法は以下の通りです。(解法の細かい説明は本題ではないので追わなくて大丈夫です) 頂点 1 を根
ARC092C - 2D Plane 2N Pointsの証明が話題になってたっぽいので問題を見てみたら、最大マッチング系貪欲の証明テクが詰まった問題だなぁと思ったので書いてみた。 問題概要 平面上に赤い点と青い点がある。 赤い点が青い点の左下である(つまりxもyも小さい)とき、それらはペアにできる 何ペア作れるか 解法 青い点をxの昇順に見て、マッチングできる赤い点があればそのうちyが最大のものとマッチングさせていく貪欲。 証明テク1:マッチングできるときはしてもよい つまり、あえてマッチングさせないことによって答えが増えることはない。 なぜなら、ある青い点 A と赤い点 X をマッチングできるとき、 マッチングさせる:残りの点集合から A と X が消える メリット:答えが 1 増える マッチングさせない:残りの点集合から A が消える メリット:X を残せる で、「X を残せる」こと
最近 Mo's Algorithm - Codeforces をよく目にする気がします。 興味深いアルゴリズムではありますが、より良いアルゴリズムがあります。 追記:「上位互換」と煽っていますが、実装量・定数倍の面から、Moが使えるときはMoを使ったほうが良いでしょう Mo まずはMo's algorithmの概要を説明しておきます。 Mo's algorithmは以下のような問題に適したアルゴリズムです。 長さNの数列に対し、Q回の区間クエリを処理する。 ただし、[l, middle) と [middle, r) の結果をマージすることはできない。(できるならsegtreeでいい) ・値の追加操作ができる。([l, r) から [l-1, r) や [l, r+1) が求まる) ・値の削除操作ができる。([l, r) から [l+1, r) や [l, r-1) が求まる) つまり、区間
この記事はCompetitive Programming Advent Calendar 2015の6日目の記事として書かれました。 この記事は、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 の3つについて書きたいと思います。 1アルゴリズム/1日で追記して行きます。 これらのアルゴリズムでは「求めたいものの特性を生かして、既に計算した結果を上手に利用する」という点で共通しており、いずれも「なるほどなぁ」と言わされました。 この美しいアルゴリズムたちを是非紹介したいと思い、この記事を書くことにしました。 ・記法について |S|:文字列 S の長さを表す。 S[i,j]:文字列 S の i 文字目から j 文字目までを取り出した文字列を表す。 KMP ※これは正確にはKMPではなくMPです。KMPについてはこちら。 文字列 S が与えられたときに、各 i について「文字列S[0,i-1]の接頭辞と接尾辞が最大何文字一致しているか」を記
SRM580のwriterをしていました。 点数はsolveまでの時間にも依存するので必ずしも600が激ムズという訳では一応ないです。 Div2 Easy 概要:区間が与えられるので重なってるペアの個数を数えよ。 解法:区間が50個しかないので全ペアについて試す。 Div2 Medium, Div1 Easy 概要:うなぎが区間として与えられるので、2点を選んでそれらのうちどちらか又は両方を含む 区間を最大化せよ。 解法:tから2つ選ぶのを全て試す。 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の簡単バージョン(設定わりと違うけど)。サーバがどうとか書いてあるけど要するに、 ある木の部分木の個数を求めよ。 典型問題っぽい雰囲
数学が好き? Herbert をやりましょう! プログラミングが好き? Herbert をやりましょう!! パズルが好き? ニコリ依存症? Herbert をやりましょう!!! Advent Calendar からいらっしゃった方、こんにちは。 snuke と申します。(twitterは @the_nikaidoes です。) ではさっそく、2007年から2009年まで Imagine Cup の公式競技だった「Herbert」について語ろうと思います^^ 「Herbert」はmap上のTargetを全て回収するようなプログラムを、いかに短く書けるかを競う競技です。 Herbertで使われる「H言語」という言語は "おもちゃ" のような言語ですが、"おもちゃ" をあなどってはいけません。 レゴで船やロボットなどの様々なものが作れるように、 「H言語」でもまた、フィボナッチ数列、素数判定、放
このページを最初にブックマークしてみませんか?
『あなたは嘘つきですかと聞かれたら「YES」と答えるブログ』の新着エントリーを見る
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く