一年前に 2014年 今年の目標 - (#・∀・) という記事を書きました。残念ながら全く目標を達成できませんでした(CFに関してはgood bye 2014で達成できたはずなのにくだらないミスでチャンスを逃しました)来年はかならず目標を達成して見せます(目標は来年発表…

問題概要 N頂点のDAGが与えられる(多重辺アリ).入次数0のノードからN番目のノードまでの全てのパスを考える. それらのなかに最も多く含まれている辺の、含まれている回数を求めよ 辺a->bが含まれる回数は(始点からaまでのパスの総数)*(bから終点までのパスの…

問題概要 [Start,Finish]で、二進数で表記した時に0の数が1の数以上になるような数の個数を求めよ桁DP。やるだけ。なんでこれが8なんだろう(この前8のad-hocが自力で解けなかった) dp[i][j][k][l]:=今上からi桁目で、0の個数-1の個数がjでkはずっと上限でき…

問題概要 N種類の曲があり、それらを順番に流す。聞いている側が曲名が分かり次第流す側に伝える。 流す側は伝えられたらすぐに次の曲を流す。 各曲には認知度p[i]があり毎秒ごとにp[i]%の確率で、そこから1秒で曲名がわかる。 また、各曲の歌詞には曲名がは…

クリスマスですね。日本語の解説記事がなかったので。 まずは普通に dp[i][j]:=i番目のポールを高さjにする時のそこまでのペナルティの合計の最小値 (不可能なときはINF)として漸化式をたててみると dp[i][j] = min{dp[i-1][k]+abs(k-j)*C | 0 となりますが…

はい、というわけでもちろん今年も参加しました。 が、残念な結果に終わったので本選まで今まで以上に精進しようと思います。 適当な解説を書きます。テンプレはいつも通り省略してます 1.水道料金 (Water Rate) やるだけ。 int A,B,C,D,p; int main() { cin…