はてなダイアリーにPKUの解答をアップロードするのをやめようと思います。 理由はTokyoTechCoderと重複してアップロードするのが面倒になったためです。 今後はTokyoTechCoderのみにアップロードして行きたいと思います。

強連結成分分解 グループの定義が問題から読み取りにくい 実はちゃんとわかっていない Spaghetti Source - 強連結成分分解 http://www.prefield.com/algorithm/graph/strongly_connected_components.html int main() { int N, M; cin >> N >> M; Graph g(N +…

動的計画法 左上と右上の値のうち大きい方を伝搬していく int main() { int N; cin >> N; int dp[2][512]; memset(dp, 0, sizeof(dp)); int front = 1; int back = 0; int bestAnswer = INT_MIN; for (int row = 1; row <= N; ++row) { for (int column = 1;…

二分探索 整数部分を固定すると、小数部分は単調増加になる 整数部分をループで回して二分探索をすると通る long double TENS = 1.0; int saturate(long double value) { value -= (int)value; value *= TENS; return (int)value; } int main() { int L; cin…

やるだけ パターンは空気を読めばおｋ int main() { int N, S; cin >> N >> S; --S; REP(i, N) { int value = S++; REP(j, N) { if (j) { cout << " "; } if (i > j) { cout << " "; } else { cout << value + 1; } value += j + 1; value %= 9; } cout << e…

枝刈り探索 計算量は不明 int N, C; ll weights[1024]; ll sumWeights[1024]; ll bestAnswer = 0; void dfs(int i, ll value) { if (value + sumWeights[i] <= bestAnswer) { return; } bestAnswer = max(bestAnswer, value); if (i == N) { return; } if (v…

動的計画法 時間->コスト の表をmapでsparseに持たせている 牛で2重ループを回しても間に合うらしい struct Cow { int T1, T2, S; bool operator < (const Cow& rh) const { return T1 != rh.T1 ? T1 < rh.T1 : T2 != rh.T2 ? T2 < rh.T2 : S < rh.S; } }; i…