夜中までCodeforcesやっていたら盛大に寝過ごしてしまった。CODE FESTIVALより難易度は下がってはいるが、初心者にとっては簡単な問題セットではない。F, G 問題以外は自力で解けた。問題はこちら。

A: カメツル算

カメとツルの個体数があたえられるので、足の数を答える。やるだけ。

a,b = map(int,raw_input().split())
print 4*a+2*b

B: バッジ

バッジを n 個生産したい。３つのバッジ製造機はそれぞれ1分間に a, b, c 個製造できる。ただし、それぞれ１分の稼働後に冷却時間が2分必要。目標のバッジ数を生産するのにかかる最小時間を答える問題。

a,b,c の大きい方から生産数にぐるぐる足していき、目標値を超えたときの時間を答えればいい。

n = int(raw_input())
abc = sorted(int(raw_input()) for _ in range(3))[::-1]
a,b,c = abc
budge = 0
ans = 0
while budge < n:
    if ans%3 == 0: budge += a
    if ans%3 == 1: budge += b
    if ans%3 == 2: budge += c
    ans += 1
print ans

C: コンテスト

コンテストの問題配点と正解番号が与えられるので獲得点数を答える問題。やるだけ。

n,m = map(int,raw_input().split())
p = map(int,raw_input().split())
s = map(int,raw_input().split())
print sum(p[i-1] for i in s)

D: 定期券

ある駅の区間aiからbiにいくとき、1駅100円の運賃がかかるとしていくらの運賃になるかを答える問題。ただし、siからtiは定期券により無料となる。

場合分けをするか min, max を使って答えればよい。

n,q = map(int,raw_input().split())
for roop in range(q):
    a,b,s,t = map(int,raw_input().split())
    if   a <= s <= t <= b: print 0
    elif a <= s <= b <= t: print 100*(t-b)
    elif s <= a <= t <= b: print 100*(a-s)
    elif s <= a <= b <= t: print 100*(t-s-(b-a))
    else: print 100*(t-s)

E: 儀式

R x C の各ブロックに、石像が南を向いて置かれてある。N 回の各手順で、ある四角の範囲の石像の向きを左に90度回転させる。最終的に M 個の石像が南を向いていたが、これはすべての手順を行った場合とは合わず、手順の１つを飛ばしてしまったことがわかっている。それでは飛ばしてしまった可能性のある手順の番号をすべて答えよ、という問題。

単純に、まずすべての手順にそって石像を回転させる。そのあと各手順について逆の操作を施してみて、南を向いた石像が M 個にあうかどうかをチェックしていけばいい。

#include <iostream>
#define FOR(i,a,b) for(int i=(a); i<b; i++)
#define REP(i,a) FOR(i,0,a)
using namespace std;

int R,C,M,N;
int A[50][50]={0} ; // 0,1,2,3 : S,W,N,E

int main(void){
    cin >> R >> C >> M >> N;
    int ra[N],rb[N],ca[N],cb[N];
    REP(i,N)
        cin >> ra[i] >> rb[i] >> ca[i] >> cb[i];
    REP(i,N)
        FOR(y,ra[i]-1,rb[i])
            FOR(x,ca[i]-1,cb[i])
                A[y][x] = (A[y][x]+1)%4;
    int south = 0;
    REP(y,R) REP(x,C) south += (A[y][x] == 0 ? 1:0);
    REP(i,N){
        int tmp = south;
        FOR(y,ra[i]-1,rb[i]){
            FOR(x,ca[i]-1,cb[i]){
                if (A[y][x] == 0) tmp -= 1;
                if (A[y][x] == 1) tmp += 1;
            }
        }
        if (tmp == M) cout << i+1 << endl;
    }
    return 0;
}

F: 順位表

あるコンテストに参加したが、きちんと順位を確認していなかった。コンテストの結果をM人に聞くと、それぞれが「番号Aiの人はBiの人より順位がいい」と情報をくれた（矛盾する情報は無いとする）。自分の参加者番号を１とした時、ありえる自分の順位のうち最高順位を求める問題。最低順位は興味ないです。

自分より上の順位の人たちが気になるので、まず自分より順位が高いという人たちの番号を集める。そのあと自分より順位が高い人たちよりもさらに順位が高い人たちの番号をすべて集めると、集めた番号の個数 + １が答えとなる。

N,M = map(int,raw_input().split())
AB = [map(int,raw_input().split()) for _ in range(M)]
high = set([a for a,b in AB if b == 1])
while 1:
    adds = set([])
    for i in high:
            adds |= set([a for a,b in AB if b == i and a not in high])
    if len(adds) == 0: break
    high |= adds
print len(high)+1

G: 通勤電車と気分

N人が座席数Kの電車の前に列をなして並んでいる。座席は車両の奥の方から1から順番に番号付けされている。N人は先頭から順番に電車に入り、席に座っていくが、それぞれの気分により次のような席どりをする。

1．「とにかく座りたい気分」:　番号の一番小さな空いてる席に座る。

「余裕があれば座りたい気分」:　両隣が空いてる席に座る。端の場合、端側は空いてるとみなす。

もちろん座れずに立つ場合もある。今、i 番目の人がpi%の確率でとにかく座りたい気分、100-pi%の確率で余裕があれば座りたい気分の時、N人全員が電車に入った後、空いている席の個数の期待値を答える問題。

個人的に苦手な確立・期待値問題。Nが最大100なので、ある人の座る場合と座らない場合の２つについて探索を広げていくとO(2^N)でTLEしてしまうことはすぐに分かる。これは典型的なDP問題で、dp[i][j] (合計 j 人の人が座っていて i 番目の席が埋まっている確率）の表を更新していくとO(NK²)で全状態の確率を求められる。各確率に対応する空いている席数を掛けあわせたものをsumすれば答えが得られる。

#include <iostream>
#include <stdio.h>
#define FOR(i,a,b) for(int i=(a); i<(b); i++)
#define RFOR(i,a,b) for(int i=(a); i>(b); i--)
#define REP(i,a) FOR(i,0,a)
using namespace std;
 
int main(void){
    double dp[201][201] = {};
    dp[0][0] = 1.0;
    int N,K;
    cin >> N >> K;
    
    double p;
    REP(i,N){
        cin >> p;
        p *= 0.01;
        RFOR(i,K,-1){
            REP(j,i+1){
                double c = dp[j][i];
                if (i < K){
                    dp[j + 2 - (i == j)][i+1] += c*p;
                    dp[j][i] -= c*p;
                }
                // 両隣が空いてる席の場合
                if (i == 0 || 2*i-j+1 < K){
                    dp[j + (i == 0)][i+1] += c*(1.0-p);
                    dp[j][i] -= c*(1.0-p);
                }
            }
        }
    }
    double r = 0.0;
    REP(i,K+1) REP(j,N+1) r += dp[i][j]*(K-j);
    printf("%.8f",r);
    return 0;
}