AtCoder Regular Contest 042 ◯◯◯- 1159->1180

54位 300点

Welcome to AtCoder Regular Contest 042 - AtCoder Regular Contest 042 | AtCoder

公式の解説

arc042 from AtCoder Inc.

www.slideshare.net

A: 掲示板 - AtCoder Regular Contest 042 | AtCoder

掲示板に\(1\)から\(N\)までのスレッドがある
スレッドに書き込みが行われると一番上に移動する
書き込みの一覧が与えられるので、最終的なスレッドの順番を答える

書き込みが新しいほうが上に来るので、書き込みの新しい順で出力した後に書き込まれなかったスレッドを出力すればよい

# -*- coding: utf-8 -*-
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys

def n():
    return int(raw_input())
def ln():
    return map(int, raw_input().strip().split())

N, M = ln()
A = [n() for i in xrange(M)]
s = set()

ret = []
for i in A[::-1]:
    if i not in s:
        s.add(i)
        ret.append(i)

for i in range(1, N + 1):
    if i not in s:
        s.add(i)
        ret.append(i)

print '\n'.join(map(str, ret))

ついでにRubyでショートコーディングしたのも載せておく

n,m,*a=*$<.read.split.map(&:to_i);puts u=a.reverse.uniq;puts [*1..n]-u

B: アリの高橋くん - AtCoder Regular Contest 042 | AtCoder

凸多角形の頂点と内部の点の座標が与えられる
内部の点から凸多角形の外側に行くのに最小の距離を求める

点と線分の距離を求めて、最小のものを求めた

平面幾何におけるベクトル演算 » 直線と線分

# -*- coding: utf-8 -*-
import math,string,itertools,fractions,heapq,collections,re,array,bisect

def n():
    return int(raw_input())
def ln():
    return map(int, raw_input().strip().split())

EPS = 1e-9

#http://www.deqnotes.net/acmicpc/2d_geometry/lines
def dot(a, b):
    return a.real * b.real + a.imag * b.imag

def cross(a, b):
    return a.real * b.imag - a.imag * b.real

def distance(a, b, c):
    if dot(b-a, c-a) <= EPS:
        return abs(c-a)
    if dot(a-b, c-b) <= EPS:
        return abs(c-b)
    return abs(cross(b-a, c-a)/(b-a))

x, y = ln()
N = n()

X = []
Y = []
for i in xrange(N):
    a, b = ln()
    X.append(a)
    Y.append(b)

ret = []
for i in xrange(N - 1):
    ret.append(distance(X[i]+Y[i]*1j, X[i+1]+Y[i+1]*1j, x+y*1j))

ret.append(distance(X[0]+Y[0]*1j, X[N-1]+Y[N-1]*1j, x+y*1j))

print '{:.7f}'.format(min(ret))

C: おやつ - AtCoder Regular Contest 042 | AtCoder

おやつの金額と満足度が与えられる
おやつの金額の合計が目標の金額をおやつ1個分まで超えてよい場合の満足度の合計の最大値を答える

金額の大きい順にソートしてから、動的計画法で普通にナップサック問題を解けば、目標の金額を超えたかどうかがわかる

Pythonで解いた版(TLEになる)

# -*- coding: utf-8 -*-
import math,string,itertools,fractions,heapq,collections,re,array,bisect,operator

def ln():
    return map(int, raw_input().strip().split())

N, P = ln()
AB = []
for i in xrange(N):
    a, b = ln()
    AB.append((a, b))

AB.sort(reverse=True)

dp = [[-1] * (P + 200) for i in xrange(N + 1)]

dp[0][0] = 0

for i in xrange(N):
    for j in xrange(P + 200):
        a, b = AB[i]
        
        z = dp[i][j]
        if z != -1:
            if z > dp[i + 1][j]:
                dp[i + 1][j] = z
            v = z + b
            if j <= P and v > dp[i + 1][j + a]:
                dp[i + 1][j + a] = v

ret = 0
for i in xrange(N + 1):
    for j in xrange(P + 200):
        v = dp[i][j]
        if v > ret:
            ret = v

print ret

C++版

#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>

using namespace std;

int main(void) {
    int N, P;
    cin >> N >> P;
    vector<pair<int, int>> AB;
    for(int i = 0; i < N; i++) {
        int a, b;
        cin >> a >> b;
        AB.emplace_back(a, b);
    }

    sort(AB.begin(), AB.end(), greater<pair<int, int>>());

    vector<vector<int>> dp;
    dp.resize(N + 1);
    for(int i = 0; i < N + 1; i++) {
        dp[i].resize(P + 200);
        for(int j = 0; j < P + 200; j++) {
            dp[i][j] = -1;
        }
    }
    dp[0][0] = 0;

    for(int i = 0; i < N; i++) {
        int a = AB[i].first;
        int b = AB[i].second;
        for(int j = 0; j < P + 200; j++) {
            int z = dp[i][j];
            if(z != -1) {
                if(z > dp[i + 1][j]) {
                    dp[i + 1][j] = z;
                }
                int v = z + b;
                if(j <= P and v > dp[i + 1][j + a]) {
                    dp[i + 1][j + a] = v;
                }
            }
        }
    }
    int ret = 0;
    for(int i = 0; i < N + 1; i++) {
        for(int j = 0; j < P + 200; j++) {
            int v = dp[i][j];
            if(v > ret) {
                ret = v;
            }
        }
    }
    cout << ret << endl;
    return 0;
}