mayoko’s diary

プロコンとかいろいろ。

2015-11-26から1日間の記事一覧

CODE FESTIVAL 2015 あさぷろ Middle C - 一次元オセロ

あさプロの時はものすごく混乱してて結局解けなかったんだけど, 今やったらめっちゃあっさりだった。 問題 code-festival-2015-morning-middle.contest.atcoder.jp 解法 N は奇数なので, 最後にすべてのコマが同じ色になる時コマは絶対に白色になっています…

CODE FESTIVAL 2015 あさぷろ Middle B - ヘイホー君と削除

いつ追加されるんだろうとずっと思ってたけどやっと追加されたので解きます。 問題 code-festival-2015-morning-middle.contest.atcoder.jp 解法 繰り返す文字列は左側と右側に分かれるので, 左からの i 文字と残りの右側 n-i 文字でなるべく長い, 一致する…

JAG Practice Contest for ACM-ICPC Asia Regional 2015 F - Modern Announce Network

この問題好き(だけどプロの人は典型とか言いそう)。 問題 jag2015autumn.contest.atcoder.jp 解法 考えやすくするために「1年生の集合」「2年生の集合」「3年生の集合」という集合を表した頂点(これらを A, B, C とする)を考えます。すると, 求めるべきなの…

Codeforces Round #333 (Div. 1) C. Kleofáš and the n-thlon

問題 codeforces.com 解法 Kleofáš のランクの合計が S であるとしましょう。すると, 結局求めるべきなのは n 試合終わった後にランクの合計が S 未満であるような人の数の期待値です。ということで, 以下のような dp を考えます。dp[i][j] = (i 試合終わっ…