TonamiLog

ゆるキャン△とスノーボードとオタク

diverta 2019 Programming Contest 2(3完)

ハート

ヴェルタプロコン2をやりました。WAいっぱい出しながら3完しました。

1は出られなかったのでunratedになって2回めが行われたことでコンテスト1個得しましたね。
してないと思います


以下ネタバレがあります

A

考え

一瞬日本語に怯みましたがABCのAみたいなAですね。
K==1の場合だけ別処理にした方が楽そうと考えて素直に実装します。

書いたソース
N,K = map(int, input().split())
if K == 1:
    print(0)
else:
    print(N-K)

B

考え

問題文読んで思考停止、これ苦手なタイプの問題では?という雰囲気を感じる
制約が1≤N≤50なので3重ループまで許されていることが分かる。
まず全Nに対して、他のNとの距離をp,qと仮定する。
各p,qについて、自分からp,q先のマスにボールがあるNの個数を数え、その分コストが低いと考える……?
いまいち自信がないですが実装してみます。

書いたソース
N = int(input())
xy = [0] * N
for i in range(N):
    xy[i] = tuple(map(int, input().split()))

case = [N]
for x,y in xy:
    for xx, yy in xy:
        if x == xx and y == yy:
            continue
        score = N
        xs = xx - x
        ys = yy - y
        for xxx,yyy in xy:
            if x == xxx and y == yyy:
                continue
            if (xxx - xs,yyy - ys) in xy:
                score -= 1
        case.append(score)
print(min(case))

通った。嬉しい。ほんとうに?嘘解法じゃないのか自信がありません。
もし嘘である事を証明できた人いたら教えてください……。

C

考え

えー分からん無理という気持ちを50分ぐらいやり、結局これに90分+3WAかかりました。
どういう法則で消していけばいいのか全然わからなかったのですが最終的に

正の値の数列をP, 負の値の数列をMとする時、正の値pを1個、負の値mを1個取っておき
他の全ての負の値をpから引き(p=p - M[i])、他のすべての正の値をmから引く(m=m- P[i])をやれば
最後p-mすると最大の値になる。

という方針で解きました。
正の値と負の値のどちらかが存在しない(全部正or全部負の値)場合は、2つの値を使って無い方の値を1個生成すればOKです。

書いたソース
N = int(input())
A = [int(x) for x in input().split()]
p = []
m = []
for a in A:
    if a < 0:
        m.append(a)
    else:
        p.append(a)
was = []
if N == 2:
    print(max(A)-min(A))
    print(max(A), min(A))
    quit()
if len(m) == 0:
    p.sort()
    m.append(p[0] - p[-1])
    was.append((p[0], p[-1]))
    p = p[1:-1]
elif len(p) == 0:
    m.sort()
    p.append(m[-1] - m[0])
    was.append((m[-1], m[0]))
    m = m[1:-1]

mm = m[0]
m = m[1:]
pp = p[0]
p = p[1:]
for x in p:
    was.append((mm,x))
    mm -= x
for x in m:
    was.append((pp,x))
    pp -= x
was.append((pp, mm))
print(pp-mm)
for p,m in was:
    print(p,m)

ゴリゴリすぎる。クレバーな実装は結局できませんでした。
全部の数字が正or全部の数字が負のケースの実装が甘くて3WA。くやしい

この時点で100分たっておりD以降は殆ど着手できませんでした。
一応脳死ソースは投げてみたけどDのテストケース半分ぐらい死んでました。

結果

f:id:Thiroyuki:20190615232208p:plain
REとWAが多い。ウーム
順位表とかで他の人のCの解け具合を見るともうちょっと頑張れた気がしますね……。

f:id:Thiroyuki:20190615232541p:plain
なんとかパフォーマンスはそこそこ出て水色射程圏内という感じになりました。何故か?

f:id:Thiroyuki:20190615232727p:plain
実は前回のABCでちょっとレートが下がっていたのでした。険しすぎてブログに書いてないです。ハー
明日もコンテストあるし頑張って水色なってくぞ。やっていきましょう。

おわり