AtCoder Beginner Contest 038 参加記

atcoder

はい。 oo-x(0/0)
http://abc038.contest.atcoder.jp
退勤して急ぎながら帰ってきたけど15分程度遅刻して参加。A,Bは緩い難易度。Cは問題文の意味すら。。。Dは部分点狙ったけど提出後に穴があることに気づき部分点ならず。。

A - お茶

python

print ['NO','YES'][raw_input()[-1]=='T']

末尾が'T'であるかを確認して'YES','NO'を振り分ける。

B - ディスプレイ

python

a,b=map(int,raw_input().split())
l=map(int,raw_input().split())
print 'YES' if a in l or b in l else 'NO'

\(H_1\)が\(H_2\)と等しければそのままで高さが揃う。\(H_1\)が\(W_2\)と等しければ2つ目のディスプレイを回転で高さが揃う。 \(W_1\)が\(H_2\)と等しければ1つ目のディスプレイを回転で高さが揃う。\(W_1\)が\(W_2\)と等しければ両方のディスプレイを回転で高さが揃う。 　　

C - 単調増加

コンテスト中は問題文の解読に撃沈。。
l<=i<rが、例1の｢条件を満たす(l,r)は(1,1),(1,2),(1,3),(2,2),(2,3),(3,3),(4,4),(5,5)の8つです。｣のことが、(a[0],a[0]),(a[0],a[1]).....
a[i]を始点にしてa[i+x] までの区間が単調増加になっているかを見る？ a[0]からa[0]まではそのまま増加扱い、a[0]からa[1]まではa[0]<a[1]で増加区間、a[0]からa[2]まではa[0]<a[1]でかつa[1]<a[2]なので増加区間。。。というのを見ていくのだと思う。

python

n=int(raw_input())
#n,k=map(int,raw_input().split())
l=map(int,raw_input().split())
ans=chk=cnt=0
for i in l:
    if chk<i and chk!=0:
        cnt+=1
        ans+=cnt
        chk=i
    else:
        cnt=1
        ans+=cnt
        chk=i
print ans

a[0]が始点のときにa[i]の増加区間まで、a[1]が始点のときにa[i]の増加区間まで...で数えようとすると多分TLEになる。端から端まで一度見れば増加区間を数えられるのでそれで済ませる。
入力例1で考えるとa[0]を見た時はa[0]とa[0]で1つ、a[1]を見た時はa[0]が始点でa[0]<a[1]とa[1]が始点のa[1]とa[1]も数えて2つ、a[2]を見た時はa[0]が始点のa[1]<a[2]とa[1]が始点のa[1]<a[2]とa[2]が始点のa[2]とa[2]を数えて3つ...という風にしていくとO(n)で出来るはず。

D - プレゼント

せめて部分点だけでもと思ったが撃沈。

python

#WAです
import bisect

def lis(A):
    p=len(A)
    L=[0]*p
    L[0]=A[0]
    length=1
    for i in xrange(1,p):
        if L[length-1]<A[i]:
            L[length]=A[i]
            length+=1
        else:
            L[bisect.bisect_left(L[:length],A[i])]=A[i]
    return length
 
n=int(raw_input())
l=range(n)
hw,wh=[],[]
while n:
    n-=1
    a,b=map(int,raw_input().split())
    hw.append((a,b))
    wh.append((b,a))
hw.sort()
wh.sort()
tmp1,tmp2=[],[]
for i in l:
    tmp1.append(hw[i][1])
    tmp2.append(wh[i][1])

print max(lis(tmp1),lis(tmp2))

hだけを見てソートしたものでwの、wだけを見てソートしたものでhの最長増加部分列で入れ子関係を探せると思ったがh,wの大きさに重複がありえるのでWA。。

とりあえず他の人のコードを参考にして、改変しながら色々試してACになりました。
参考先様： http://abc038.contest.atcoder.jp/submissions/746747

python

# -*- coding: UTF-8 -*-
 
import bisect
IS=float('inf')
##746747 roto_37さんをパクリ
 
n=int(raw_input())
l=range(n)
wh1=[]
for i in l:
    w,h=map(int,raw_input().split())
    wh1.append([-w,h])
wh1.sort()
wh=wh1[::-1]
dp=[IS]*n
for i in l:
    dp[bisect.bisect_left(dp,wh[i][1])]=wh[i][1]
print len(set(dp))-1 if IS in dp else len(dp)

入力例

9
1 1
1 2
1 3
2 2
2 3
2 4
3 3
3 4
3 5

前回までの方法で昇順ソートして処理をすると、(1,1), (1,2), (1,3), (2,4), (2,5)を使おうとしてしまう。 h,wが入れ替わっていた場合は(1,1), (2,2), (3,3)を使って偶然に3になるっぽいですけど。。
初めに入力受取後にwを昇順、hを降順でソートされるようにする。 ソート例： [[-1, 3], [-1, 2], [-1, 1], [-2, 4], [-2, 3], [-2, 2], [-3, 5], [-3, 4], [-3, 3]] (正負を反転させたりしているので昇順、降順がややこしいかもしれない。)
この状態で最長増加部分列(LIS)の長さを求めると、

処理の流れ

[3, inf, inf, inf, inf, inf, inf, inf, inf]
[2, inf, inf, inf, inf, inf, inf, inf, inf]
[1, inf, inf, inf, inf, inf, inf, inf, inf]
[1, 4, inf, inf, inf, inf, inf, inf, inf]
[1, 3, inf, inf, inf, inf, inf, inf, inf]
[1, 2, inf, inf, inf, inf, inf, inf, inf]
[1, 2, 5, inf, inf, inf, inf, inf, inf]
[1, 2, 4, inf, inf, inf, inf, inf, inf]
[1, 2, 3, inf, inf, inf, inf, inf, inf]

wを昇順、hを降順というふうに事前にデータを処理しておくことで　後で続きを書きます。