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

codeforces#37

codeforces

今回はやたら長文でBとかスルーしました...



0:48:39 C pretest 通過

0:55:57 A pretest 通過

あとはDでゴニョゴニョやってて結局解けなかったorz



Aについて.

問題理解できません.

そのうち読み直すことにしましょう(遠目

例を見て次のようなのを投げたらAcceptedです.

N = input()
l = map(int, raw_input().split())
print '%d %d' % (max([l.count(i) for i in l]), len(set(l)))





Cについて.

情報源符号化の問題.

しばし解説(そのうち自分が多分忘れるから

文字の列を, 01で表した01列は, どういう場合に素早くデコードできるでしょうか?

例えば次のような符号を考えます.

   A : 00

   B : 01

   C : 10

   D : 11

これは, 流れてきたデータを二つずつに区切って文字に直してけばOK

では

   A : 0

   B : 10

   C : 110

   D : 1110

これは, 0が来たら区切るというルールでOK

でも, こんなのでもいいんだよね

   A : 0

   B : 10

   C : 110

   D : 111

1が三つ来た段階で, Dと決定できちゃうから.

今挙げたようなのは, 来たデータを順番に処理していってリアルタイムにデコードできるもの.

これを瞬時符号と言います.(もちろん一意復号可

問題文ではno word was a prefix of another oneと書かれているのがこれに相当します.

これに対して

   A : 0

   B : 01

   C : 011

   D : 1111

みたいなのを, 非瞬時符号といいます.

後から見れば完全にデコードできるけど, 送られてくる順に見ると, どっちつかずな時間がある.

瞬時か非瞬時かは符号の木の構造が大きく異なります.

後はどこかのサイトをご参照を.



...というわけで次のコードでAccepted.

最初にクラフトの不等式を使ったら判定は一瞬だよね.

え? そんなの知らない?

私も問題読んでからググって知りましたよ.

N = input()
l = map(int, raw_input().split())
arr = ['' for i in xrange(len(l))]
if sum([2 ** (- p) for p in l]) > 1:
  print 'NO'
else:
  s = '0'
  while '' in arr:
    try:
      i = l.index(len(s))
      l[i] = 0
      arr[i] = s
      while s[-1] != '0':
        s = s[:-1]
      s = s[:-1] + '1'
    except:
      s = s + '0'
  print 'YES'
  print '\n'.join(arr)