読者です 読者をやめる 読者になる 読者になる

CODE THANKS FESTIVAL A日程参加してきた #codefes

Python ProgrammingContest

CODE THANKS FESTIVALに参加してきました。

CODE THANKS FESTIVALは2014/11/8に行われたCODE FESTIVALに参加できなかった人たちのために開催されたオンサイトのプログラミングコンテスト+懇親会です。


CODE FESTIVAL2014 | RECRUIT HOLDINGS -リクルートホールディングス


最近CODE FESTIVALの様子が動画で公開されたんだけど、想像以上に面白そうでした。
サイトのほうでゲストの方々のトークライブが公開されているのはとても嬉しいですね。

本選はISUCON*1があって参加できなかったんだけど、
ISUCON終わって帰ってきたらTLでCODE FESTIVAL参加勢がTLでめっちゃ楽しそうにしててつらかったです・・・。

そんなわけでTHANKS FESTIVALに参加してきました。
THANKS FESTIVALには、最近競プロはじめたって人がたくさんいました。
私も去年の今頃競プロはじめて謎コンで初めてオンサイトに参加して、たくさんの競技プログラマーさんたちに会えてから一気に競プロが楽しくなったので、THANKS FESTIVALに来た人たちもそれがきっかけで競プロにはまってくれる人がいたら嬉しいなあと思いました。

コンテストでは、最初オープンコンテストの方にでてたり、
コンテスト開始後にID登録されてないことに気づいてコンテストのページに入れなかったりで、参加する前からもう負けてる感じでした(´・ω・`)

結果は散々で悔しい思いをしましたが、この悔しさを忘れずに問題演習に励もうと思います。

Githubに解答は公開してありますが、参加してた方でブログで解答を公開していた方が多かったので私も書いてみようかと思います。
基本全部PythonでEだけC++(っぽい何か)です。

A問題

カメには足が 4 本、ツルには足が 2 本あります。
カメが A 匹、ツルが B 羽いるとき、足は合計で何本あるでしょうか。

n, m = map(int, raw_input().split())
print n * 4 + m * 2

B問題

とりあえずソートする問題

n = int(raw_input())
a = int(raw_input())
b = int(raw_input())
c = int(raw_input())
m = [a,b,c]
m.sort(reverse=True)
t = 0
nn = 0
while nn < n:
    nn += m[t % 3]
    t += 1
print t

C問題

indexが1~なので、間違えないようにする

n, m = map(int, raw_input().split())
score = map(int, raw_input().split())
ans = map(int, raw_input().split())

s = 0
for a in ans:
    s += score[a - 1]
print s

D問題

minとmaxどっちがどっちかわかんなくなったので何も考えずとりあえず条件で分岐させた

N, Q = map(int, raw_input().split())
for i in xrange(Q):
    a,b,s,t =  map(int, raw_input().split())

    if s <= a <= t and s <= b <= t:
        print ((t - s) - (b - a)) * 100
    elif a <= s and s <= b <= t:
        print (t - b) * 100
    elif s <= a <= t and t <= b:
        print (a - s) * 100
    elif a <= s and t <= b:
        print 0
    else:
        print (t - s) * 100

本当はこれでいい

N, Q = map(int, raw_input().split())
max(0, min(b,t) - max(a,s))

E問題

Pythonで適当にかいたらTLE.
ちょっと整理したところで間に合うか自信がなかったのでC++に書き直す。(C++かけない)
めちゃくちゃ汚い。

#includeとかは省略

int main(int argc, const char * argv[]){
    int R,C,M,N;
    cin >> R >> C >> M >> N;
    int v[R][C];

    for (int r = 0; r < R; ++r){
        for (int c = 0; c < C; ++c){
            v[r][c] = 0;
        }    
    }

    int r1,r2,c1,c2;
    int rc[N][4];
    for (int i = 0; i < N; ++i){
        cin >> r1 >> r2 >> c1 >> c2;
        rc[i][0] = r1 - 1;
        rc[i][1] = r2 - 1;
        rc[i][2] = c1 - 1;
        rc[i][3] = c2 - 1;
    }

    for (int i = 0; i < N; ++i){
        for (int r = rc[i][0]; r <= rc[i][1]; ++r){
            for (int c = rc[i][2]; c <= rc[i][3]; ++c){
                v[r][c]++;
            }
        }
    }

    for (int i = 0; i < N; ++i){
        int tmp[R][C];
        for (int r = 0; r < R; ++r){
            for (int c = 0; c < C; ++c){
                tmp[r][c] = v[r][c];
            }
        } 

        int count = 0;
        for (int r = rc[i][0]; r <= rc[i][1]; ++r){
            for (int c = rc[i][2]; c <= rc[i][3]; ++c){
                tmp[r][c]--;
            }    
        }

        for (int r = 0; r < R; ++r){
            for (int c = 0; c < C; ++c){
                if (tmp[r][c] % 4 == 0){
                    count ++;
                }
            }
        } 
        if (count == M) {
            cout << i + 1 << endl;
        }
    }

    return 0;
}

帰ってきてから二次元累積和を使った解法で解き直した(in Python)
全方向転換を終わらせた後に、南をむいてる銅像と西をむいてる銅像の累積和を持っておいてうにうにする。

def partial_sum(table, r1, r2, c1, c2):
    s = table[r2][c2]
    if r1 > 0:
        s -= table[r1 - 1][c2]
    if c1 > 0:
        s -= table[r2][c1 - 1]
    if r1 > 0 and c1 > 0:
        s += table[r1 - 1][c1 - 1]
    return s


R, C, M = map(int, raw_input().split())
N = int(raw_input())

array = [[0 for _ in xrange(C)] for _ in xrange(R)]

rcs = []
for i in xrange(N):
    r1, r2, c1, c2 = map(int, raw_input().split())
    rcs.append([r1 - 1, r2 - 1, c1 - 1, c2 - 1])
    for r in xrange(r1 - 1, r2):
        for c in xrange(c1 - 1, c2):
            array[r][c] += 1

table_0 = [[0 for _ in xrange(C)] for _ in xrange(R)]
table_1 = [[0 for _ in xrange(C)] for _ in xrange(R)]

for r in xrange(R):
    for c in xrange(C):
        total_0 = 0
        total_1 = 0
        if c != 0:
            total_0 += table_0[r][c - 1]
            total_1 += table_1[r][c - 1]
        if r != 0:
            total_0 += table_0[r - 1][c]
            total_1 += table_1[r - 1][c]
        if c != 0 and r != 0:
            total_0 -= table_0[r - 1][c - 1]
            total_1 -= table_1[r - 1][c - 1]
        table_0[r][c] = total_0 + (1 if array[r][c] % 4 == 0 else 0)
        table_1[r][c] = total_1 + (1 if array[r][c] % 4 == 1 else 0)

base = table_0[R - 1][C - 1]
count = 0
for i, rc in enumerate(rcs):
    if base - partial_sum(table_0, rc[0], rc[1], rc[2], rc[3]) + partial_sum(table_1, rc[0], rc[1], rc[2], rc[3]) == M:
        print i + 1

コードが汚い。

F問題

この問題よくわからなくて、グラフで考えればよかったのに、
なんか一生懸命ソートしようとして頑張って1時間半溝にすてた。
ソートするには情報が足りないからソートは出来ない。
自分より弱い人リストみたいなのをつくって、そこに0番(高橋くん)を含んでる人が何人いるか数えた。

n, m = map(int, raw_input().split())
win = [set() for i in xrange(n)]
for i in xrange(m):
    a, b = map(int, raw_input().split())
    win[a - 1].add(b - 1)

for k in xrange(n):
    for i in xrange(n):
        w_set = set()
        for w in win[i]:
            for ww in win[w]:
                if ww != i:
                    w_set.add(ww)
        if w_set:
            win[i] |= w_set

rank = 1
for i in xrange(1, n):
    if 0 in win[i]:
        rank += 1

print rank

G問題

F説いた時点であと15分しかなくて、急いで書いたけど間に合わなかった。
ここまでは解きたかった・・・。
典型的なダイナミックプログラミンッな問題。
最初メモ化再帰で書こうとしたけどこの問題はDPで書いたほうが楽だった。

普通に書いたらTLEして、確率が0%の時は何もしないっていうの入れたら通った。
本番中だったらこれは思いつかなかったしやっぱPythonで競プロやってるけど強くなりたい人はもう1言語使えなきゃつらいと思う。
C++早く書けるようになりたいしちゃんと演習しよう。

N, K = map(int, raw_input().split())

pp = []
for i in xrange(N):
    pp.append(int(raw_input()))

dp = [[[0.0 for _ in xrange(K + 1)] for _ in xrange(K + 1)] for _ in xrange(N + 1)]
dp[1][1][0] = 1.0

for n in xrange(1, N):
    for j in xrange(K + 1):
        for i in xrange(j / 2 + 1):
            if dp[n][j][i] == 0: # これないとTLE
                continue
            #seat
            p = pp[n] / 100.0
            if i > 0:
                dp[n + 1][j][i - 1] += p * dp[n][j][i]
            elif j + 1 <= K:
                dp[n + 1][j + 1][i] += p * dp[n][j][i]

            #skip
            if j + 2 <= K:
                dp[n + 1][j + 2][i + 1] += (1 - p) * dp[n][j][i]
            else:
                dp[n + 1][j][i] += (1 - p) * dp[n][j][i]

s = 0
for i in xrange(K + 1):
    for j in xrange(K + 1):
        p = (i + K - j) * dp[N][j][i]
        s += p
print s

H問題

ロリハっ◟( ˘•ω•˘ )◞
いつか解きたい。

さいごに

オンサイトのコンテストは達成感も悔しさも楽しさも10倍ですね。
THANKS FESTIVALでもDDR太鼓の達人(自宅用)あってびっくりしました。(THANKS FESTIVALではDDRは不人気でした。)
楽しいコンテストを開いてくださったリクルートホールディングスさんには本当に感謝しています。
B日程に参加予定のみなさんはがんばってください!