ferinの競プロ帳

競プロについてのメモ

2018-04-02から1日間の記事一覧

AOJ2601 Evacuation Route

問題ページ Evacuation Route | Aizu Online Judge 考えたこと そのマスから各出口へ到達できる最後の時刻を求めたい その出口に右から入るとき、その出口よりも右にある防火扉が閉まる前に超えられればok dp[i] = (区画iから左へ進んだときに出口に到達可能…

AOJ1248 The Balance

問題ページ The Balance | Aizu Online Judge 考えたこと aグラムがi個、bグラムがj個のとき ai + bj = d, ai + d = bj, ai = bj + d を満たせばdグラムを測れる iを決め打てばjは自動的に決まる iは何通りくらいあるのか? a=1,b=2,d=50000みたいなときに5*…

AOJ2303 Marathon Match

問題ページ Marathon Match | Aizu Online Judge 考えたこと i人目が走るのにかかる時間は (休んだ回数)*T[i] + L/V[i] 休憩所M個中r個で休む確率は C(M,r) P(i)^r (1-P[i])^(M-r) になる したがってi人目がj回休む確率とそのときのタイムを求められる i人目…

AOJ2157 Dial Lock

問題ページ Dial Lock | Aizu Online Judge 考えたこと 状態数が最大10^10あるから愚直は無理 回転させる数だけ気にすればいい気持ちになる i桁目について (t[i]-s[i]+10)%10 回回せばいい +1 +2 +4 +2 みたいなのが来たときに+2から+2の区間をまとめて回せ…

AOJ1320 City Merger

問題ページ City Merger | Aizu Online Judge 概要 要素数がNの文字列集合Sが与えられる。連続した部分文字列にSの要素を全て含むような文字列のうち最短のものを求めろ。 N<=14、(文字列の長さ)<=20 考えたこと suffixとprefixが一致しているような文字列の…