【ABC344】ABC344をRubyで解いた振り返り【AtCoder】
ABC344の参加しましたのでその感想を
この度ABC344に参加した結果緑レートに上がることが出来ましたので記念にABC344を振り返りたいと思います
結果としては2WAの4完でした。時間切れにはなりましたが頑張ればE問題も解けそうという感じでした
E問題は解けていませんがA~E問題までを振り返っていこうと思います
色変記事ももちろん書きます
A - Spoiler 150点
文字列が与えられるので2つの|で囲まれた文字と|を消して出力せよというもの
問題文をぱっと見て実装したものの誤読してしまいWAを出してしまいました
|を消すだけでいいやなどと考えて提出してました(もちろんサンプルも通っていない)
解き方
|の個数をカウントし1でなければansに追加するという方法で解きました
def main
s = strary
ans = []
count = 0
s.each do |i|
if i == "|"
count += 1
next
end
next if count == 1
ans << i
end
puts ans.join("")
end
自分の解答はこちら
B - Delimiter 150点
N個の整数が一行に一つずつ与えられるので逆順に出力するもの
AtCoderにしては今回珍しかったのですが N は入力では与えられません。
取得する個数を誤るとREになってしまうというのがこの問題の難しいところですね
解き方
N個目の整数は0と制約で決まっているので取得した値が0なら取得するループから抜け出すだけですね
def main
ans = []
while true
n = int
ans << n
break if n == 0 # 0なら無限ループから抜ける
end
ans.reverse.each do |i|
puts i
end
end
自分の解答はこちら
C - A+B+C 250点
A, B, Cの三つの数列から一個ずつ要素を選びXの数列の要素一つずつ(Xi)と等しくなるかという問題
問題文通りに計算すると
Aの個数(N) * Bの個数(M) * Cの個数(L) * Xの個数(Q) です
最大ケースを考えると 100 * 100 * 100 * 2 * (10 ** 5) = 2 * (10 ** 11)なので余裕でTLEになります
解き方
あらかじめ A + B + Cを全パターン列挙しておきます
その後にXiと一致するものがあるか見つけるだけで計算量は問題なくなります(100 * 100 * 100 + 2 * (10 ** 5))
※A + B + Cを全パターン列挙をただの配列に突っ込みincludeで探す方法だとTLEになります。配列でやるなら二分探索で見つけるか、またはSetを使うようにしましょう
def main
n = int
a = intary.sort
m = int
b = intary.sort
l = int
c = intary.sort
q = int
x = intary
set = Set.new([])
# A + B + Cの全列挙
a.each do |i|
b.each do |j|
c.each do |k|
set.add(i + j + k)
end
end
end
# A + B + Cの全列挙したset内の要素と一致するか判定
x.each do |i|
if set.include?(i)
puts "Yes"
else
puts "No"
end
end
end
自分の解答はこちら
D - String Bags 425点
まず空文字Sを持っています
文字列がいくつか入った袋がN個あり各袋に対し2つの行動のうちどちらかを行います。
- 1 円を支払い、袋 i からちょうどひとつの文字列を選択して S の末尾に連結する。
- 何もしない
最終的に文字列Sが文字列Tと一致するときの最低金額をこたえる問題
問題文を見てDPの文字列版だなとすぐ気が付きました
N回の内文字列Sに連結するかしないかなんていかにもDPです
このDPの特徴として持つ状態が文字列ということ
解き方
入力例1をもとにやってみます
はじめは空文字です dp[0] = {"" => 0円}
今回は3袋あるので3回袋内の各文字列を追加した場合の状態について考えます
1回目には "ab" "abc" "abcd" の3つの文字列が与えられますのでdp[0]の各値に対し追加した場合としない場合をの最小値をそれぞれ計算します。すると以下のようになります
dp[1] = {"" => 0円, "ab" => 1円, "abc" => 1円, "abcd" => 1円}
2回目には "f" "c" "cd" "bcde" の4つの文字列が与えられますのでdp[1]の各値に対しに対し追加した場合としない場合をの最小値をそれぞれ計算します。すると以下のようになります
dp[2] = {"" => 0円, "ab" => 1円, "abc" => 1円, "abcd" => 1円}
追加しても元の値段より高くなってしまうので更新はありません
※文字列Tに一致しない文字列になってしまう場合は状態として追加しないようにします("f"を追加して"abf"になる場合など)
私の場合はこの処理を追加し忘れてTLEになりました
3回目には "e" "de" の2つの文字列が与えられますのでdp[2]の各値に対しに対し追加した場合としない場合をの最小値をそれぞれ計算します。すると以下のようになります
dp[3] = {"" => 0円, "ab" => 1円, "abc" => 1円, "abcd" => 1円, "abcde" => 2円}
"abc"に"de"を追加した場合の2円と"abcd"に"e"を追加した場合の2円と状態として得られますがどちらも2円なので"abcde" => 2円になります (本来はより小さい方の値が採用される)
各袋の計算が終わったら最後の状態の中でkeyが文字列Tの値を出力して終わりです
もしの状態の中で文字列Tのkeyがない場合は-1を出力します
def main
t = str
n= int
a = []
n.times do |i|
a << strary
a.last.shift
end
dp = [{"" => 0}] # 初期化 はじめは"" => 0のみ
a.each.with_index do |v, i|
dp[i + 1] = dp[i].dup # ひとつ前のDPの値をコピー
v.each do |j|
dp[i].each do |k|
next unless t.start_with?("#{k[0]}#{j}") #文字列Tに一致しない場合は処理しない
if dp[i+1][k[0]+j] == nil # 新規の値なら素直に + 1 する
dp[i+1][k[0]+j] = dp[i][k[0]] + 1
else
dp[i+1][k[0]+j] = [dp[i+1][k[0]+j], dp[i+1][k[0]] + 1].min # すでにある状態の値段か今回追加する場合の値段の内やすい方を採用する
end
end
end
end
if dp[n][t] == nil # 文字列Tのkeyがない場合は-1を出力
puts -1
else
puts dp[n][t]
end
end
自分の解答はこちら
E - Insert or Erase 475点
数列Aが与えられます
Q回のクエリを実行した後の数列Aを出力しろというもの
クエリの内容は以下の2つ
- 数列Aの要素xの直後にyを挿入する
- 数列Aの要素xを削除する
解き方
数列Aの各要素の前後の値を保持すれば解けるかなと思い実装しました
入力例1の数列A(2 1 4 3)の場合は以下のようにしました
{2 => [nil, 1], 1 => [2, 4], 4 => [1, 3], 3 => [4, nil]}
追加する場合削除する場合をそれぞれの前後の値と結びつくようにしました
結果とてはACとREで時間切れでした
ちゃんとデバックすれば解けそうなので解けたら追記します
後から知りましたがこういうのをLinkdListというそうです
自分の解答はこちら
今後
緑になったことだし違う言語を使ってみたりしようと考えてます。
また継続してこんな感じで振り返り記事を書けたらなと思います。(はじめるタイミングを探してました)
Discussion