読者です 読者をやめる 読者になる 読者になる

codeforces#34

codeforces

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引いておく.