ABC06CとD問題

問題はhttp://abc006.contest.atcoder.jp/

C問題

解答の方針

N人すべてを利用しないといけない、4本が人単位でとれる値の最大値なので
2*N<M,M<4*Nの場合は不可能

a,b,c = （大人の人数、老人の人数、子供の人数）とする

老人二人と大人一人,子供一人は足の本数的に同値なので、
老人が0人と一人の時のみ考えればよい。
つまり、Mが奇数なら老人が一人必要で、偶数なら老人は必要ない。

M-3*b,Nは常に偶数となり、その差の数だけ、子供が必要だと考えられる。
よって子供の数を求めた後、N-b-cにより大人の数も求められる。

コード

abc06c.py

N,M = list(map(int,input().split()))

if 2*N>M or 4*N<M:
    a = -1
    b = -1
    c = -1
else:
    b = M%2
    c = int(((M-3*b)-2*(N-b))/2)
    a = N-b-c
print(a,b,c)

D問題

部分点1

解答の方針

配列cのそれぞれの値をどのように残すのかを全探索する。
深さ優先探索による再帰関数を作成して探索を行った。

コード

abc06dver1.py

N = int(input())
c = []
for i in range(N):
    c.append(int(input()))
v = []
res = 0


def dfs(v,k=0):
    global res
    if k == N:#kが最後尾に来た時にvの長さが前回の探索より長ければ更新
        if v == sorted(v):
            res = max(res,len(v))

    else:
        v.append(c[k])
        dfs(v,k+1)#k番目のcを含む配列としてk+1番目へ
        v.pop()
        dfs(v,k+1)#k番目は含まずにk+1番目へ

dfs(v)
print(N-res)

部分点2

動的計画法によって探索を行う。
左から順に、そのカードを使ってできる最大の列の長さを保持し、
次の値はその前の値から参照して最大値を計算する。

長さがNの配列vを作成する。
左から順に探索を行い、参照するc[i]、c[i]より左に存在するc[j]の中で、
c[i]-c[j](増加関係）にあるものの中から、もっとも大きなv[j]の値を取得し、
v[i]=v[j]+1とする

コード

abc06dver2.py

N = int(input())
c = []
for i in range(N):
    c.append(int(input()))
v = [1 for i in range(N)]

for i in range(1,N):

    for j in range(i):
        if 0 < c[i]-c[j]:
            v[i] = max(v[i],v[j]+1)



print(N-max(v))

満点解法

解答の方針

queue[n]がn個の部分増加列のうちの最後の要素の最小値となるようにデータを持たせる。
（解説を見たほうが分かりやすい,最長部分増加列という問題らしい）

自分の場合、配列を小さいものに書き換えるところが直感的な理解を妨げていたが、
長さのみを取得したいので、
1=>3=>5が1=>2=>5になったとしても情報は損失しないと考えると理解ができた。

書き換えの際のindexの探索にはbisectを使用したら楽だった。

コード

abc06dver3

from bisect import bisect

N = int(input())
c = []
for i in range(N):
    c.append(int(input()))
queue = [c[0]]

for i in range(1,N):
    if queue[-1] < c[i]:#最後尾よりもc[i]が大きいなら数列が大きくなる
        queue.append(c[i])
    else:
        n = bisect(queue,c[i])#queueの中でc[i]がある場所を探索
        queue[n] = min(queue[n],c[i])

print(N - len(queue))