問題文 : 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]に…