AtCoder-Typical DP Contest C問題をやりました

プログラミング 備忘録

C問題もやりました。
以下問題文
C: トーナメント - Typical DP Contest | AtCoder

Problem Statement
2K 人が参加するトーナメントがある。このトーナメントでは以下の形式で試合を行う。

第 1 ラウンドでは、1 と 2、3 と 4、…　が試合を行う。
第 2 ラウンドでは、(1 と 2 の勝者) と (3 と 4 の勝者), (5 と 6 の勝者) と (7 と 8 の勝者), …　が試合を行う。
第 3 ラウンドでは、((1 と 2 の勝者) と (3 と 4 の勝者) の勝者) と ((5 と 6 の勝者) と (7 と 8 の勝者) の勝者), ((9 と 10 の勝者) と (11 と 12 の勝者) の勝者) と ((13 と 14 の勝者) と (15 と 16 の勝者) の勝者), …　が試合を行う。
以下同様に第 K ラウンドまで行う。

第 K ラウンドの終了後に優勝者が決定する。人 i の Elo Rating が Ri であるとき、人 i の優勝確率を求めよ。

ただし、Elo Rating RP の人 P と Elo Rating RQ の人 Q が対戦した場合、人 P が勝つ確率は 1⁄(1+10(RQ−RP)⁄400) であり、異なる試合の勝敗は独立であるとする。
Constraints

1≤K≤10
0≤Ri≤4000

Input Format
入力は以下の形式で標準入力から与えられる。

K
R1
…
R2K

Output Format
答えを 2K 行出力せよ。i 行目は人 i が優勝する確率であり、絶対誤差が 10−6 以下のとき正当と判定される。

書いたソースは続きから↓

続きを読む

AtCoder-Typical DP Contest B問題をやりました

プログラミング 備忘録

前回に続いてB問題も解いてみました。
問題文以下
B: ゲーム - Typical DP Contest | AtCoder

Problem Statement
すぬけ君とすめけ君がゲームをしている。最初に、二つの山がある。左の山には A 個の物が積まれており、上から i 番目のものの価値は ai である。左の山には B 個の物が積まれており、上から i 番目のものの価値は bi である。すぬけ君とすめけ君は、すぬけ君からはじめて交互に次の操作を繰り返す。

    両方の山が空であれば、ゲームを終了する。
    片方の山が空であれば、空でないほうの山の一番上のものをとる。
    両方の山が空でなければ、好きなほうの山を選び、一番上のものをとる。

両者が最善を尽くしたとき、すぬけ君の取るものの価値の合計を求めよ。
Constraints

    1≤A,B≤1000
    1≤ai,bi≤1000

Input Format
入力は以下の形式で標準入力から与えられる。

A B
a1…aA
b1…bB

ソースは続きから

続きを読む

AtCoder-Typical DP Contest A問題を解きました

プログラミング 備忘録

AtCoderのTypical DP ContestのA問題を解いてみました

AtCoderというのは、毎週アルゴリズム系のプログラミングコンテストを開催している所謂競プロの主催者です。
このコンテストの問題は、コンテスト後も公開されているので練習がてら解くことができます。
その中でもTypical DP Contestというのは、動的計画法(Dynamic Programming)と呼ばれるアルゴリズムを用いて
解ける典型的な問題を集めたコンテストとなっています。といえども、初心者のうちは、DPで自分でパラメータを設定することが難しく、典型的とはいってもなかなか骨のある問題集となっています。

今回解いたのはTypical DP のA問題です。問題文は以下
A: コンテスト - Typical DP Contest | AtCoder

Problem Statement
N 問の問題があるコンテストがあり、i 問目の問題の配点は pi 点である。コンテスタントは、
この問題の中から何問か解き、解いた問題の配点の合計が得点となる。
このコンテストの得点は何通り考えられるか。
Constraints

    1≤N≤100
    1≤pi≤100

Input Format
入力は以下の形式で標準入力から与えられる。

N
p1p2…pN

書いたソースは続きより

続きを読む