俵言

しがない社会人が書く、勉強とかのこと。最近は機械学習や kaggle 関連がメイン。

CODE FESTIVAL2015 決勝 (当日編) (A~E)

code-festival-2015-final.contest.atcoder.jp

なんか今更感ありますが、当日の決勝参加記をば。

本番ではA~Eまでの5問しか解けなくて悔しかったです。復習は復習編で。

A - コード川柳 (2:17でAC)

与えられた文字列の長さが順に5・7・5になってるか確かめるだけ。なのですが焦りすぎて1WAを出す失態を犯しました。

S,T,U = raw_input().split()
print "valid" if len(S) == len(U) == 5 and len(T) == 7 else "invalid" 

B - ダイスゲーム (16:44でAC)

解法聴いてそっかーってなったやつ。ちゃんと考えれば良かったんですが、 1 \leq N \leq 256なのでO(N^2)でも行けるやろってことでDPしました。ただこれもバグる要素ないはずなのに変に単一リストでやろうとして(そして結局やらない)時間かかってしまった。勿体無い。

N = int(raw_input())
dice = [[0]*(6*N+1) for i in xrange(N)]
for i in xrange(6):
    dice[0][i+1] = 1
for i in xrange(N-1):
    for j in xrange(6*(i+1),-1,-1):
        for k in xrange(6):
            dice[i+1][j+k+1] += dice[i][j]
print max(xrange(N,6*N+1), key= lambda x: dice[N-1][x])

C - 寿司タワー (26:01でAC)

シミュレーションしました。タワーの順番を前から見ていって、シャリ・ネタまたはネタ・シャリの順番になっていたらスルー、シャリまたはネタが連続しているときは、既に分解しているパーツがあればそれを使い、なければ寿司を一個分解して使わなかった方のパーツをストックします。

N = int(raw_input())
S = map(int,list(raw_input()))
n = s = cnt = inc = 0
while inc < 2*N-1:
    if S[inc]^S[inc+1]:
        inc += 2
    else:
        if S[inc] == 1:
            if n > 0:
                n -= 1
            else: 
                cnt += 1
                s += 1
        else:
            if s > 0:
                s -= 1
            else:
                cnt += 1
                n += 1
        inc += 1
print cnt

if文多い。解説の解法は頭良いしすっきりしてて良いですよね。

D - 足ゲームII (102:31でAC)

問題見た直後にとりあえずいもす法で累積和取ったんですが、そのあとどうすれば良いか分からない..「絶対 O(N)解あるやろ!」と思ったんですが思いつかず、パーカー欲しさからセグメントツリーで殴ることを決断。

N-1点とるために必要な人数はあるボタンをスルーしたときに必要になる人数の最小値なので、セグツリーで時間の区間ごとの必要人数を管理し、各ボタン(  S_iから T_iの間押し続けると得点がとれる)についてそのボタンをスルーしたときに必要になる人数、すなわち

  • 区間  0 \leq t \lt Sで必要な人数の最大値
  • 区間  S \leq t \lt Tで必要な人数の最大値 - 1
  • 区間  T \leq t \lt 10^5で必要な人数の最大値

の3つのうちの最大値を求めます。その最小値が答えです。計算量は O(NlogN)なのでC++なら余裕で間に合います。

しかしながらバグらせたせいで75分も時間取られました。しかもバグじゃなくて単にinit()呼び出してないだけだったんでめっちゃ悔やまれる..

int n;
int tree[100000*4];
int s[100000];
int t[100000];
void init(int N){
    n = pow(2,int(ceil(log2(100000))))-1;
    rep(i,(n+1)*2) tree[i] = 0;
}
int update(int h){
    if (h < n) tree[h] = max(update(h*2+1),update(h*2+2));
    return tree[h];
}
int query(int a, int b, int h, int l, int r){
    if (r <= a || b <= l) return 0;
    if (a <= l && r <= b) return tree[h];
    return max(query(a,b,h*2+1,l,(l+r)/2), query(a,b,h*2+2,(l+r)/2,r));
}
int main(){
    int N,ans,tmp;
    cin >> N;
    init(100000);
    rep(i,N){
        cin >> s[i];cin >> t[i];
        s[i]--; t[i]--;
        tree[n+s[i]]++;
        tree[n+t[i]]--;
    }
    rep(i,100000) tree[n+i+1] += tree[n+i];
    update(0);
    ans = N;
    rep(i,N){
        tmp = 0;
        tmp = max(tmp,query(s[i],t[i],0,0,n+1)-1);
        tmp = max(tmp,query(0, s[i], 0, 0,n+1));
        tmp = max(tmp,query(t[i], 100000, 0, 0, n+1));
        ans = min(ans,tmp);
    }
    cout << ans << endl;
    return 0;
}

E - ショートコーディング(133:00でAC)

これに関しては順当に考えたというか、--は+になる、!!!は!になる、-のあとに!が来ると-が無効化されるってのを考えて行って、それをそのままシミュレーションした感じです。順番に処理しないとまずいかと思ってわざわざスタックを用意してごちゃごちゃやってます。無効化された場合はポップし、最後まで残ったものを添字順にならべてます。

S = raw_input()[::-1]
m = e = 0
mstk = []
estk = []
for i,s in enumerate(S):
    if s == "-":
        if m == 0: 
            m += 1
            mstk.append(i)
        else: 
            m -= 1
            mstk.pop()
    else:
        if m == 1:
            m -= 1
            mstk.pop()
        if e < 2:
            e += 1
            estk.append(i)
        else:
            e -= 1
            estk.pop()
order = [(j,False) for j in mstk]+[(j,True) for j in estk]
order.sort(key = lambda x: x[0])
print "".join("!" if v else "-" for i,v in order)[::-1]

なんかCでもこんなコード書いたなあと思いつつ提出。AC出てパーカー獲得確定したときすごく嬉しかったです。

解説見てこんな長々と書いて順に処理する必要はないと知ってちょっとショックでしたが、解けたので良しということで。

残り時間

F,G,Hを眺めて、Fが解けそうな気がしたので取り組んでたんですが解けず。結局そのまま時間切れで終了しました。

まとめ

セグメントツリー勉強してて本当に良かったと思いましたね(バグッたけど)、おかげでパーカー取れました。ただ、区間系来てよくわからなかったときにとりあえずせグツリー持ち出しちゃうのは良くない気がする..

6問目解きたかったんですが5問で終わったのは残念でした。ここで6問目を解ける実力を付けたい。