問題文 : ジョイッター解法 : (1) 1の人がいる場合 (2) 1の人がいなくて, 2, 3の人がいる場合 (3) 3の人だけの場合で場合分けをする.(1) 1の人がいる時は, その人と他の人を全員友達にしてあげれば, 最小の辺数を達成できる.(2) N人の人がいれば, ある人と皆…

問題文 : ワニの地下都市(pdf注意)解法 : 出口につけばすぐに出ることが出来るので, 出口のノードのコストは0にしておく.そうでないすべてのノードについて, "出口までたどり着ける最短時間" "出口までたどり着ける2 番目の最短時間"を状態としてdijkstra を…

問題文 : Stack Maze解法 :dp[y1][x1][y2][x2] : 区間D : x ∈ [x1, x2], y ∈ [y1, y2] で宝石を置ける個数の最大値とすると, マス(y1, x1) から(y2, x2)に到達可能であれば, D' : x ∈ (x1, x2], y ∈ [y1, y2] などの, Dより小さい区間の最大値からこの値を計…

問題文 : 塗り箸解法 : dp[i][j] : 区間[i, j]を塗るためのコストの最小値, とするとdp[i][i] = 1, dp[i][j] = for(k = i...j - 1) min(dp[i][k] + dp[k + 1][j]) - (t[i] == t[j])となる. これは, 区間の幅を小さいものから計算すれば実現できる.コード : #…

問題文 : スキー解法 : 全体の平均速度について2 分探索を行う. ある平均速度vを決めると, その平均速度でt 秒間高原を滑るとtv [m] 進むこととなる. 通った道のりの総和S と, 滑った時間の総和Tについて, S ≦ Tvを満たせば, その平均速度vで高原を滑り抜け…

問題文 : 判子解法 : まず, この作業でスタンプを作ることは, スタンプからIOIOI...OIの形を復元することを考える. このとき, 境界条件を考えないために, IO と OI を文字列に連結する. このとき, "OOO"や"III"の形で連結されている箇所があれば, 真ん中を変…

問題文 : Sliding Window解法 :見た感じセグメント木でもよさそうだが, 蟻本でdequeを使うO(N) 解法が紹介されていたので, dequeの練習がてら書いてみた. dequeステキ, 便利. やはり書くと分かりやすい.dqでは, i dq2では, i a[j] となるようにdequeにデータ…

平衡2分探索木, いつか実装したいなあと思っていたので書いてみた. 疲れた.手元のアルゴリズムイントロダクションとか、ネットの資料を色々漁って書いた. やべえ.2-3-4木という木を2分探索木で表現すると赤黒木になるらしい. ただ、普通の赤黒木だと実装が結…

問題文 : 数当て解法 : 最初に, 1の数をO(N)時間で当てる. あとは, 1の情報を元に二分探索を行う. Σ[i = 2, 99] ceil(log_{2}i) ＝ 580 くらいなので, 最悪でも580 + 100 コード : #include <cstdio> #include <cstring> using namespace std; void print(int *p, int n) { fo</cstring></cstdio>…

問題文 : 足し算解法 : vectorを使って実際に足し算を行う. 繰り上がり/桁数が変わる位置のみに微妙な変化があり, 間の数の計算は省くことができる.コード : #include <cstdio> #include <climits> #include <vector> #include <algorithm> using namespace std; typedef long long lint; typedef</algorithm></vector></climits></cstdio>…

問題文 : 戦国時代解法 :見張り達の見張るエリアを, 左上と右上の線で分ける.まずは左上側の線の処理を以下のように行う.点P(x, y)を, 点P'(0, y - x)に移して, 簡単な場合分けでその点にいる見張りがどれだけの領地を見張っているかを求めることが出来る.右…

問題文 : 湖解法 :まず,dp[l][r] = 区間[l, r]での運行数の最大値, とすると dp[l][r] = max(dp[l][r], dp[l][s[i] - 1] + dp[s[i] + 1][t[i] - 1] + dp[t[i] + 1][r]);となる. ただし, s[i], t[i]はそれぞれ船の来航する地点の座標で, s[i] これは, t[i]に…

問題：k<=100, N<=10^18, M<=1,000,000,007のとき、1^k+2^k+…+N^k mod M を１秒で求めるプログラムを作成せよ— 編集の都合上省略さん (@semiexp) 12月 19, 2011昔semiexpさんがこんな問題をつぶやいていたので、解いてみました. 結論から言うと, 僕の環境だ…

問題 : 巡回セールスマン問題解法 : 与えられたグラフは,(validなものであれば) 問題の制約通り, 有向木に辺をいくつか(最大501本)足したものとなる. また, 枝分かれや併合・子がある(となる)頂点が, 述べ 1000 個程度より多くあると, validなグラフが構成で…