Atcoder Beginner Contest #015

前回参加分。ログとして記事化。pythonの実行速度に苦しめられながらもなんとか全完できた。問題はこちら。

A: 高橋君の研修

２つの文字が与えられるので、長い方を答える問題。

A = raw_input()
B = raw_input()
print A if len(A) > len(B) else B

B: 高橋君の集計

N個のソフトウェアのバグの数が与えられるので、その平均個数を答える問題。ただしバグの数０のソフトウェアは調査母数に入れないこと。整数同士の割り算をしないように注意。

import math
N = int(raw_input())
A = map(int,raw_input().split())
A = [i for i in A if i != 0]
print int(math.ceil(sum(A)*1.0/len(A)))

C: 高橋君のバグ探し

N行にわたってK個の数字が与えられる。各行から1つずつ数字を選びXORをとったときに値が0になる組み合わせがあるかどうか答える問題。普通は再帰関数を用いるのだろうが、itertoolsを使えばそのまま書ける。itertools万歳。

import itertools
N,K = map(int,raw_input().split())
T = [map(int,raw_input().split()) for i in range(N)]
for ls in itertools.product(range(K),repeat=N):
    ans = reduce(lambda a,b:a^b, [T[i][ls[i]] for i in range(N)])
    if ans == 0:
        print "Found"
        break
else:
    print "Nothing"

D: 高橋君の苦悩

N枚の画像の幅とその画像の重要度が与えらえる。これを一枚の表に横一列にはりつけていく。合計幅W以下、貼り付け枚数K以下の条件のもと画像貼り付け作業を行った場合の合計重要度の最大値の最大値を答える問題。

典型的なDP問題で、dp[i][j] (i は合計幅、j は貼り付け枚数) を更新していけば答えが得られる。pythonだとTLEになってしまい、苦労してC++に書き換えた。

#include <iostream>
using namespace std;
int main(void){
    // Here your code !
    int W,N,K;
    cin >> W;
    cin >> N >> K;
    int A[N];
    int B[N];
    for (int n = 0; n < N; n++){
        cin >> A[n];
        cin >> B[n];
    }
    int dp[K+1][10101];
    for (int k = 0; k < K+1; k++)
        for (int w = 0; w < 10101; w++)
            dp[k][w] = 0;
    for (int n = 0; n < N; n++){
        int a = A[n];
        int b = B[n];
        for (int k = K-1; k > 0; k--){
            for (int w = W-a; w > -1; w--){
                dp[k+1][w+a] = max(dp[k+1][w+a], dp[k][w]+b);
            }
        }
        dp[1][a] = b;
    }
    int ans = 0;
    for (int k = 0; k < K+1; k++)
        for (int w = 0; w < W+1; w++)
            ans = max(ans, dp[k][w]);
    cout << ans << endl;
    return 0;
}