AGC032 -A/B

AtCoder Grand Contest 032

Grand Contestなので上手く行っても
A,B問題ぐらいしか出来ないだろうと思ったけど出た
A問題はなんとかAC
B問題間に合わなかった。
せめてB問題ぐらいまで取れるように精進しましょうということで
ブログにアウトプットして記憶したい。

A - Limited Insertion

atcoder.jp

問題文はN回操作して与えられた数列と一致させる事ができるかどうか
と書いてあるけど、与えられた文字列を抜いていく
と逆操作の手順を考えれば良いだけで、
ここまでたどり着いたらすぐできた。
あと「考えられる操作手順が複数存在する場合は」
と書いてあるけど試すと実際は存在しないのでここに大分惑わされた。

n = int(input())
ls = [int(i) for i in input().split()]
ans = [0]*n    
if len(ls) >= n:
    for i in range(n,0,-1):
        for j in range(i,0,-1):
            if ls[j-1] == j:
                ls.remove(j)
                ans[i-1] = j
                break
if ls == []:
    for s in range(len(ans)):
        print(ans[s])
else:
    print(-1)

最後は全部取り除けたらリストが空になるので答えを出す雰囲気で書いた。

B - Balanced Neighbors

atcoder.jp

コンテスト中に間に合わなかったのが悔しい。
問題分の意味が分からなくて時間をかなりロスした。
隣接する頂点の番号の和（自分の番号を含まず）
という意味だった事が分からず混乱してた。

図にするとこんな感じになるハズ（？）

つまり、この問題はこういう性質のグラフの辺の本数と
辺の接続している頂点を書き出せ
って事らしい。

なので扱いやすいように表を書いた。

表に書くまで出来てれば後はコードにするだけでOK
表の○+×の合計数はN個から二つ取った組み合わせ

で計算できる
偶数奇数で扱いを変えて×の箇所を求めて出力。
偶数の時は対角線上の要素だけ省く
奇数の時は対角線が一つずれるイメージ

itertools.combinationで○+×の組み合わせ全部作ってしまって、
×だけ出力しないって形で作った。
おそらくかなり冗長だけど自分的にはこっちの方が分かり易かった。

N = int(input())
ls = [i for i in range(1,N+1)]
import itertools
plist = list(itertools.combinations(ls,2))
all_pattern = len(plist)
if N % 2== 0:
    print(all_pattern-(N//2))
    idx_x = N
else:
    print(all_pattern-(N-1)//2)
    idx_x = N-1
idx_y = 1
for p in plist:
    if p[0] == idx_y and p[1]==idx_x:
        idx_x = idx_x -1
        idx_y = idx_y +1
    else:
        print(p[0],p[1])