Codeforces Beta Round #57 (Div. 2)
初参加してきた。
全体102位、out of competition除くと17位、rate1707の黄色になりました。
Div1に上がってしまったらしいので、きっと次で落ちるでしょう。
木とかグラフ系の問題にも弱いのが露呈している･･･
点数高いのはそういう系が多い気がするので、なんとかしたい所。
あと、Hackが出来るようになりたい。
どの言語でもソースをぱっとみてやってる事が理解出来るとか、計算量だけでも把握出来るとか、その辺りが重要そう。
Eとか、よく見てみたら自分のroomでは、自分以外みんなO(n^3)っぽくて、一人が凄いHackしていた。
そのHackしてた人もO(n^3)で、嘘解法→Hackで点数上げという方法もあるんだなーとか。
あと、CでRじゃ無いときの0の入力で何も出力しない人が凄く多かったらしい。
Aはまだいいけど、B、CとかはC++で解ける気がしない。Ruby万歳。
以下ソースとか。
テンプレは省いてます。
A Ultra-Fast Mathematician
問題文よく読めてなくて設定が解らん。
とりあえずXORを出力しろって事らしい。
書くよりも、問題文を読むことをやめるのに時間がかかった気がする。
XOR取るとnbit出力するのが面倒そうなので、文字列のまま。
a=gets.chomp
b=gets.chomp
a.each_byte.zip(b.each_byte){|a,b|
print a==b ? 0 : 1
}
puts
B Hard Work
問題文の長さに滅入ってCを先に解いた。
どうやら、最初の三つの入力の順列と、その後の入力を、-_;の三つと大文字小文字を無視して比較しろ。という事らしい。
a=gets.chomp.gsub(/;|-|_/,"").upcase b=gets.chomp.gsub(/;|-|_/,"").upcase c=gets.chomp.gsub(/;|-|_/,"").upcase d=[a+b+c,a+c+b,b+a+c,b+c+a,c+a+b,c+b+a] n=geti n.times{ s=gets.chomp.gsub(/;|-|_/,"").upcase puts d.include?(s) ? "ACC" : "WA" }
うん、gets.chomp.gsub(/;|-|_/,"").upcaseが多すぎるよね。関数化すべきだった。
あと、d=[]の所が美しくない。
まぁACすれば正義という事で許して下さい･･･
C Capture Valerian
A進数で入力された物を、Bが"R"ならローマ数字で、Bが数ならB進数で出力しろという問題。
f=gets a,b=f.split(" ") n=gets.to_i(a.to_i) if b=="R" puts n.roman else puts n.to_s(b.to_i).upcase end
やっててよかったProjectEuler。
Integer::romanの部分は、過去のProblem 89のソースの一部をぺたっと。
ソース漁ってたら二つ出てきたので綺麗な方を使ったけれど、
綺麗すぎるし多分他の人の解答みながら書き直してるなと思って検索かけたら、やはりそうだった模様。
これは非常に宜しくない気がする。自分で書いたらしき汚い方を使うべきだったか。
ちなみにRじゃ無いときのupcase忘れて一回WAった。
D Eternal Victory
脳内でなぜか木ではないと思い込み、正解のアルゴリズムを考えから消去してしまった。
どちらかというとTSPみたいな物かと思ってしまったという。
全ての都市を通って根に戻ってくるには、全ての道を2回通る必要がある。
最終的に別の都市で終わって良いので、一番遠い所で終わるようにし、そこまでの道のりは1回だけ通る事にすればいい。
つまり、道路の長さの合計*2-一番遠い都市までの長さでOKだと思う。
とか考える事は出来ても、どうせ実装で詰まるのがオチなんだけど。
E Enemy is weak
入力された数列{ai}に、
a[i]>a[j]>a[k]かつi
提出したのは
n=geti
a=getia
a.each.with_index.to_a.sort.each.with_index.to_a.map{|a|a.flatten}.sort_by{|b|b[1]}.map{|a|a[3]}
a=a.reverse
t1=[]
t2=[]
sum=0
a.each{|b|
t1[b]=1
m1=0
m2=0
for i in 0...b
m1+=t1[i]||0
m2+=t2[i]||0
end
t2[i]=m1
sum+=m2
}
puts sum
3行目がやばい。
一度テスト通してから、省メモリのために追加した所。
やってる事は、入力をそれぞれソートした時の順序、つまり集合の中で何番目に小さいかに置き換えてるだけ。
(ex:{10,8,3,1}→{3,2,1,0} {1,5,4,3}→{0,3,2,1})
その後、i
