2017-09-12から1日間の記事一覧

C: ウサギとカメ | AtCoder Regular Contest 025

ダイクストラ法っぽいことをする。 (時間、誰(ウサギ、カメ), 場所, 始点) のようなタプルを優先順位付きキューに入れていく。 まず、 場所=始点、時間0で両者をすべての頂点からスタートさせる。 以降、各始点からの最短経路だけを考える。 今いる場所と始…

C: 蛍光灯 | AtCoder Regular Contest 026

蛍光灯が途切れずに照らしている範囲を左端から右端へ伸ばしていこう。 最適解では、手前で使った蛍光灯をi、次の蛍光灯をjとすると、l[i]<l[j] が成り立つ。なので、事前に蛍光灯をlの昇順にソートしておく。 dp[x] = 0からxまでが途切れずに照らされているときの最小コスト とする。dp[L]が解。 はじめ dp[0] = 0である。 蛍光灯をソートされた順にみよう。いま、i番目の蛍光灯の使用を考る。dp[r[i]]が更新されるかもしれない。 蛍光灯は[l[i], r[i]] の範囲を照らすので、 前の範囲 => (重複) => [l[i], r[i]] のようになっていれば、左端からr…</l[j]>

yukicoder #563 : 超高速一人かるた large

解説付き const int MO = (int)1e9 + 7; string S[2001]; RollingHash rh[2001]; int f[2001][2001]; mint ans[2001], fact[2001]; int main(){ ios::sync_with_stdio(false); cin.tie(0); int N; cin >> N; rep(i, N) { cin >> S[i]; } // 接頭辞の問題=>…