2017年4月8日のAtCoderの記録。言語はRubyです。
問題はこちら：AtCoder Beginner Contest 058
私の回答一覧はこちら：自分の結果
35分で全問完答。 1回ミスったのでタイムは40分相当。4位です。一桁順位だ!やった!
#A問題
a+c = b*2 が成り立つか否かで場合分けして終わり。簡単だ。と思ってコードテストせずに提出したら**==の代わりに=と書く**という初歩的なミスのせいでWA1回。情けない。
#B問題
文字列の奇数文字と偶数文字を与えられたときに全体の文字列を出力する。例えば奇数文字がabcで偶数文字がxyzならば、axbyczと出力すればいい。
何かスマートな解き方がありそうな気がしたけど、思いつかなかったので愚直にループ。
終了条件が少し難しい。文字を書いたあとに終了判定するのではなく、文字を書く前に位置を見て終端位置に達していれば終了と判定している。
o = gets.chomp!
e = gets.chomp!
ol = o.length
el = e.length
ans = ""
i = 0
while(1) do
break if i == ol
ans += o[i]
break if i == el
ans += e[i]
i += 1
end
puts ans
#C問題
複数の文字列が与えられる。どの文字列S_iに対してもS_iの部分文字列の並び替えになるような文字列のうち、最長のものを求めよ。複数存在するときは辞書順で最初のもの。
考え方は以下。
- 文字ごとに考えれば良い。入力例1だとaの含まれる個数が上から2個、2個、3個なので、解答にaは2個まで入れられる。最長のものなので、2個入れる。min(2, 2, 3)を計算する。
- 辞書順の最初のものである。なのでアルファベット順に出力すれば良い。「解答にはaが3個、cが2個、eが1個含まれるな」と分かったら、解答はそのまま並べてaaacceである。
- つまりaから順に調べながら、解答となる文字列の後に順次追加していけばよい。
実装
- 「aからzのそれぞれに対して」はRangeオブジェクトの
'a'..'z'が使える。1..10のように数字だけしか使えないのかと思ってた。eachはArrayクラスのメソッドなので、to_aで変換する必要がある……と思って書いたが、実際にはRangeクラスにもeachメソッドがあり、to_aは必要ない。 - 「文字列中に何回aが出現するか」はcountメソッド。毎回忘れる…… 公式ドキュメント
- 最小値を求める部分は前回の上手い解答を見た反省を活かして、mapで書いた。スッキリ書ける。
N = gets.chomp!.to_i
input = []
N.times do
input << gets.chomp!
end
ans = ""
('a'..'z').to_a.each do |char|
arr = input.map do |i|
i.count(char)
end
mi = arr.min
ans += char * mi
end
puts ans
#D問題
定石となるアルゴリズムを知っている必要はなく、頭を使って計算量を上手く減らす問題。大得意。
- 縦と横で話は完全に独立しているので、(縦の合計)×(横の合計)で良いだろう。(ここは厳密な証明をしたわけではなく推測。)
- では横だけ考えると、横幅の合計はどう求めるか。M本の縦線から2つ選ぶのを全通り考えると時間オーバー。小さな例として下の場合を考えると縦線の選び方は6通りあり、横幅の合計は3×a1 + 4×a2 + 3×a3になる。
| 横幅a1 | 横幅a2 | 横幅a3 |
|---|
- a2の左側に2つ、右側に2つ縦線があるので、a2を含むような縦線2つの選び方は2*2=4である。他も同様。
ここまで来れば実装量はとても少ない。
N,M = gets.split(" ").map{ |v|
v.to_i
}
xs = gets.split(" ").map{ |v|
v.to_i
}
ys = gets.split(" ").map{ |v|
v.to_i
}
mod = 100_000_007
yoko = 0
0.upto(N-2) do |i|
yoko += (xs[i+1] - xs[i]) * (i+1) * (N-i-1)
yoko = yoko % mod
end
tate = 0
0.upto(M-2) do |i|
tate += (ys[i+1] - ys[i]) * (i+1) * (M-i-1)
tate = tate % mod
end
puts (yoko * tate) % mod
(レート更新について追記予定)