Div.2ということではりきった
時間的にはこんな感じ
0:10:33 A Wrong answer on pretest 2
0:15:47 A pretest 通過
0:24:07 B Wrong answer on pretest 3
0:26:17 B pretest 通過
0:41:57 C pretest 通過
1:47:45 D pretest 通過
E めんど
2:00:00 終わり
結果は
A Accepted
B Accepted
C Wrong answer on test 12
D Runtime error on test 18
E やってない
まずAから.
数字を円形に並べて, それぞれのお隣さんとの差の絶対値が最小になるのはどの二つか?
円形ということで, 最初っから初めの数字をappendしておいた.
その代償に表示のところでいじらないといけないけどね.
n, a = raw_input(), map(int, raw_input().split()) a.append(a[0]) m = min([abs(a[i] - a[i + 1]) for i in xrange(len(a) - 1)]) print '%s %s' % [(i + 1, ((i + 2) if i + 2 < len(a) else 1)) \ for i in xrange(len(a) - 1) if abs(a[i] - a[i + 1]) == m][0]
Bは数列の中で, m個以下を選び(m個選ぶ必要はない), その最小となるものの大きさ(多分そんな感じ
(n, m) = map(int, raw_input().split()) a = sorted(map(int, raw_input().split())) print - sum([i for i in a[:m] if i <= 0])
Cは, 本の中で参照したいページの列が与えられて, それを簡単にフォーマットせよという問題.
ソートしただけではダメで, 差が1のページはまとめなきゃいけない:
1,2,3,1,1,2,6,6,2 → 1-3,6
まだこのレベルなら簡単に書ける.
と思いきや...間違ってる...
a = map(str, sorted(list(set(map(int, raw_input().split(',')))))) try: for i in xrange(len(a) - 1): if a[i][-1] == str(int(a[i + 1]) - 1): a[i], a[i + 1] = ('0', a[i][:-1] + a[i + 1]) \ if len(a[i]) == 3 else ('0', a[i] + '-' + a[i + 1]) except: pass print ','.join([s for s in a if s != '0'])
Dは, 木とその中心が与えられて, 中心からあるノードまで行く時にそのノードの直前のノードの番号は?という問題.
結構いけたと思ったのに...Runtime error on test 18ってなってしまった.
これどういうことだろう...?
(n, r1, r2), a = map(int, raw_input().split()), map(int, raw_input().split()) a = a[:r1 - 1] + [r1] + a[r1 - 1:] arr = [[] for i in xrange(n)] for i in xrange(len(a)): arr[a[i] - 1].append(i) arr[i].append(a[i] - 1) for i in xrange(len(arr)): arr[i] = list(set(arr[i])) ans = [-1 for i in xrange(n)] def g(c): if any([ans[i] == -1 for i in arr[c]]): for i in arr[c]: if ans[i] == -1: ans[i] = c g(i) ans[r2 - 1] = -2 g(r2 - 1) print ' '.join([str(p + 1) for p in ans if p != -2])
後日談
Cのミスはすぐに気が付いた.
二桁以上になったらこれじゃダメだ...
ってことで, 次のコードでAccepted.
a = [[i] for i in sorted(list(set(map(int, raw_input().split(',')))))] for i in xrange(len(a) - 1): if a[i][-1] == a[i + 1][0] - 1: a[i], a[i + 1] = '', a[i][:-1] + a[i + 1] if len(a[i]) == 3 else [a[i][0], '-', a[i + 1][0]] print ','.join([str(''.join(map(str, s))) for s in a if s != ''])
一行目で何やっているか少し書いとくと,
raw_input() 入力
split(',') カンマで区切って文字の配列に
map(int, 整数の配列に
ここまではいつも通り.(いつもはカンマじゃないからmap(int, raw_input().split())を使うけど)
set 集合型に(ここで重複削除)
list リスト型に戻す
sorted ソートする
[[i] for i in ...] それぞれの要素をちっちゃなリストに入れておく.
最後の作業はリストに統一性を持たせるため.
つまり, 途中で[1, '-', 3]みたいなのとお隣さんになるからね...
これしなくても書けると思うけど, 出力の所が面倒くさくなると思う.
でもこれいっぱい括弧があって見にくい...(からのHaskell!
ということで, 次のコードでもおk
_=lambda x,*f:reduce(lambda y,g:g(y),f,x) a = _(raw_input(), lambda x: x.split(','), lambda x: map(int, x), set, list, sorted, lambda x: [[i] for i in x])
これならまだマシかな
ついでに176文字のワンライナー.
Solution Sizeでソートしたらitchynyが大量に...www
自分で言うのも何だけど, なかなか上手いこと書いてる.
print''.join(map(str,reduce(lambda x,y:(x+[',']if y[0]-x[-1]-1 else x[:-1]if len(x)>1and x[-2]=='-'else x+['-'])+y,[[i]for i in sorted(set(map(int,raw_input().split(','))))])))||< <!--ああ, Aは次の196文字.<br> あまりいじってないので, もうちょっと短くなるのかもしれない. >|python| l=len;n,a=raw_input(),map(int,raw_input().split());a.append(a[0]);r=range(l(a)-1);m=min([abs(a[i]-a[i+1])for i in r]);print '%s %s'%[(i+1,i+2if i+2<l(a)else 1)for i in r if abs(a[i]-a[i+1])==m][0]||< --> <br> <br> Dは, 再帰の深さ.<br> 1000回越えちゃったんだろうね.<br> import sys<br> sys.setrecursionlimit(5000)<br> ってやったらtest 18は通過するよ! やったね! <br><br> じゃなくて...<br> 苦労してAcceptしてもらったコードがこれ<br> >|python| (n, r1, r2) = map(int, raw_input().split()) r1 = r1 - 1 r2 = r2 - 1 a = map(lambda x: int(x) - 1, raw_input().split()) a = a[:r1] + [r1] + a[r1:] # where r1 is the previous capital arr = [[] for i in xrange(n)] for i in xrange(len(a)): arr[a[i]].append(i) arr[i].append(a[i]) for i in xrange(len(arr)): arr[i] = list(set([j for j in arr[i] if j != i])) ans = [-1 for i in xrange(n)] def g(): global c r = [a for a in arr[c[0]] if ans[a] == -1] if r != []: c += r for i in r: ans[i] = c[0] del c[0] c = [r2] ans[r2] = -2 # where r2 is the new capital while c != []: g() print ' '.join([str(p + 1) for p in ans if p != -2])
時間1080 msかかってる...
この問題で学んだこと: 入力の数字で, インデックスとして使われるものは最初に1引いておく.