Codeforces Round #293 (Div. 2) の参加記
はい。 oo---x(0/0)
B問題がちょろそうに見えて問題誤読してて時間ギリギリまでかかってようやく通った。全体ではHack祭りになってたようだ。
http://codeforces.com/contest/518
A. Vitaly and Strings
ざっくりと大意
・同じ長さの文字列sとtがある。
・文字列sを辞書順で今より大きい文字列にしつつ、かつtよりは小さい文字列を作る。
方針のようなもの
・sを大きくしてtと比較する。
s=list(raw_input()) t=raw_input() x=len(n) if n.count('z')==x: print 'No such string' else: age=0 for i in range(-1,-x-1,-1): if n[i]=='z': n[i]='a' age=1 else: n[i]=chr(ord(n[i])+1) break ns=''.join(n) if ns<k: print ns else: print 'No such string'
sが全てzであると辞書順で大きく出来ないし、tより小さくもならないので'No such string'になる。それ以外の場合はsの末尾を1つだけ大きくして比較する。1つだけ大きくしてる時にzだと繰り上がりのような感じになるのでaの戻して左側を1つ大きくしに行く。先に全てがzのパターンを排除しているので先頭まで行っても繰り上がりが終わらないことはないです。
1つだけ大きくし終わったらs,tを比較して回答を出力する。文字列を辞書順で大小比較が上手く機能して良かったけど、実はコーナーケースがあるとか他の言語では比較がどうなるかとかはわからないです。
Hack成功できるチャンスだった群
http://codeforces.com/contest/518/submission/9985163
http://codeforces.com/contest/518/submission/9984103
文字列を左から見たりとかtを小さくしてsより大きい文字列を作ろうとしてる人とか結構いたっぽい。。多分それ自体は繰り上げ/繰り下げと作った後の文字列の確認がしっかり出来てれば問題無いと思う。。言語圏によって違うのかもしれないけど小さくするとか左からとかは直感的でない気がする。自分ではsを1つだけ大きくしてtと比較以外は考えなかった。
B. Tanya and Postcard
ざっくりと大意
・文字列sのお手紙の文章を文字列tの新聞などから切り抜き集めた文字列で作り上げたい。
・文字種「ABC」があってて大文字小文字もあってれば"YAY!"、文字種「ABC」があってるが大文字小文字が違うと"WHOOPS"。
・"YAY!"を優先度が上で"WHOOPS"は下にしてsをつくろうとした時に"YAY!"と"WHOOPS"の数を出力する。
方針のようなもの
・文字をまとめて調べる。
s=raw_input() t=raw_input() def cnt(l): big=[0 for i in range(26)] sml=[0 for i in range(26)] for i in l: chk=ord(i) if 65<=chk<=90: big[chk-65]+=1 else: sml[chk-97]+=1 return (big,sml) def syori(bs,ss,bt,st): a=b=0 for i in range(26): a+=min(bs[i],bt[i]) a+=min(ss[i],st[i]) bs[i],bt[i]=max(0,bs[i]-bt[i]),max(0,bt[i]-bs[i]) ss[i],st[i]=max(0,ss[i]-st[i]),max(0,st[i]-ss[i]) b+=min(bs[i]+ss[i],bt[i]+st[i]) return (a,b) bigs,smls=cnt(s) bigt,smlt=cnt(t) x,y=syori(bigs,smls,bigt,smlt) print x,y
通ったけど提出6回目までぐりぐりと無駄に修正を重ねたので凄い汚いので書きなおした。。先頭から若しくはソートしてからでも1文字ずつ見ていくと大文字小文字のYAY!優先のためには探し方が凄いめんどくさくて時間がかかるかバグるかだと思う。 大文字小文字一致するものを先にカウントして後で余ったのを数えた。問題文を読むのに無駄に色々苦戦したけどpositionが文字種(A,B,Cとかの種別)だったんだと思う。全然分からなかった。 あと大文字小文字はcaseのことだったと思う。こっちはupperとかlowerとかあるからすぐわかったけど。。