今回はやたら長文で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)
