Codeforces Round #338 (Div.2) - 君はまるで砂漠に咲く、一輪の花。

A. Bulbs

ざっくりと大意

・m個のクリスマス電球は最初はオフで点いていない。n行で各行にx個のボタンがある。ボタンの電球を点灯させられる?
・各行のボタンを使って電球を全て点けられるか?なお、一度点いた電球はボタンをどうしようと点いたままである。
・サンプル1は1行目2個のスイッチで1,4番目を、2行目3個のスイッチで1,3番目を、3行目1個のスイッチで2番目を点灯させて1から4番までm個の電球を点灯させられる。

python

n,m=map(int,raw_input().split())
s=[1]*m
for i in range(n):
    l=map(int,raw_input().split())
    tmp=set(l[1:])
    for j in tmp:
        s[j-1]=0
print 'NO' if sum(s) else 'YES'

初めは電球を点いていない状態を想定で長さmの数列を用意して、n行に渡ってあるボタンたちを使って電球の状態を更新していく。最終的に電球がどうなったかでYES/NOを出力すれば大丈夫っぽい。
上記の解法では初期状態を1、判定条件を総和が0以外であるか？という感じにしているが、初期状態は0でも1でもどちらでも使えます。判定条件も総和を見るのではなく0 in 〜や1 in 〜とかでも出来ます。というか書きやすいやり方でいいと思います。

B. Longtail Hedgehog

ざっくりと大意

・n個の頂点とm個の辺の情報が与えられる。
・m個には同じペアの頂点を結ぶものや、自身と繋がるような辺は含まれない。
・単調増加になる部分の長さ？と単調増加の終わりの頂点の辺の数の積が美しさの点数になる？？
・サンプル1は単調増加は1,2,5で長さ3、終わりの頂点5の辺の数は3で3･3の積で9。
・サンプル2は単調増加は1,2,3,4で長さ4、終わりの頂点4の辺の数は3で4･3の積で12。

python

n,m=map(int,raw_input().split())
d={}
for i in range(m):
    u,v=map(int,raw_input().split())
    if u-1 in d:
        d[u-1].append(v-1)
    else:
        d[u-1]=[v-1]
    if v-1 in d:
        d[v-1].append(u-1)
    else:
        d[v-1]=[u-1]
ans=chk=1
dp=[1]*n
for i in range(n):
    if i in d:
        for j in d[i]:
            if j>i:
                dp[j]=max(dp[i]+1,dp[j])
for i in range(n):
    if i in d:
        ans=max(ans,dp[i]*len(d[i]))
print ans

はい。グラフ問題という要素よりdp要素のが濃い気がする。頂点dpの配列を0からn-1番目にしてる都合で辺の入力受取もすべて-1して処理した。頂点0からnまで順番に見ていく。頂点iから出ている辺で頂点jがiより大きいならばdp[j]にdp[i]+1かdp[j]の大きい方を代入する。dp[i]+1はiからjに繋がる辺を使った場合の情報、dp[j]のほうが既に大きいというのはiより若い頂点からすでに大量につながっている場合である。各頂点により若い頂点がいくつ繋がっているかが確定した後は全ての頂点を調べて自身から出ている辺の数と若い頂点数の積の最大値を調べる。