olpheの競プロ帖

競プロ問やアルゴリズム等の考察します

Codeforces(MemSQL Start[c]UP 3.0 - Round 1)

5完122位でした!すごい!Round2も頑張るぞ!

A問題

本選に25人参加できるコンテストがあり、それらの参加者のうち何人かの予選での順位が与えられる。本選参加を辞退した人は最小で何人かな?

http://codeforces.com/contest/859/submission/30389464

 

B問題

ブロックがN個与えられるので、それらを並べてできる多角形の周の長さを短くしたい!

基本的には正方形を目指して並べる。欠けていても周の長さは変わらないが、一辺が1短い長方形を作れる場合があることに注意

http://codeforces.com/contest/859/submission/30389970

 

C問題

パイを順番に配っていく。お互いが最善を尽くしたときに得られるパイの大きさの総計を求める。まず先攻が配る権利を持っている。パイを自分に配ったとき、相手に配る権利が移る。

DP[次に何枚目のパイを配るか][また、配る権利を持っているのはどちらか]

でメモ化再帰を行った。

http://codeforces.com/contest/859/submission/30394617

 

D問題

トーナメントを行う。各参加者同士では勝率が定められている。i回戦で相手に勝った時、その勝利が発生する確率*2^(i-1)の点を得られる。また、相手が貯めこんでいる点も得られる。どのように進行したら優勝者の持つ点が最大になるかな?

まず各参加者についてi回勝ち残る確率を計算しておき、

DP[i回目に][jが勝ったときの]得点の最大値

を回す。

http://codeforces.com/contest/859/submission/30397238

 

E問題

席替えをする。各人について今の席と希望する席が与えられる。また、各人は席替え中に席を移動しない、若しくは希望した席に移動する。の二種類しか行動をとりえない。

まず、今の席から希望する席に向かって辺を伸ばし、有向グラフだと考える。

各連結成分についてループが存在しない場合、移動の仕方は連結成分の頂点数通り存在する。ループがある連結成分については、2通り存在する。

それらを掛け合わせてやればよい。

http://codeforces.com/contest/859/problem/E

 

レート変動は1910->2038でhighestを更新した。やったぜ。