AtCoder Beginner Contest 166(ABC166) A~Eの復習
3日坊主ならぬ3回坊主の2回目です。
連日開催はテンションも上がるしありがたいですね。
当時のお気持ちなどなどを書いて復習記事とします。
A - A?C
入力が「ABC」なら「ARC」と出力、
入力が「ARC」なら「ABC」と出力する問題です。
2文字目(S[1])で判断する方法もありますし、
もうちょっと小洒落た書き方がありそうですが、
ここはおとなしくやることにします。
S = input() if (S == "ABC") : print("ARC") else : print("ABC")
B - Trick or Treat
問題を理解するのに時間がかかってしまいました。
K種類のお菓子と、それをもっているすぬけ君のリストが与えられるので
最終的にお菓子をもっていないすぬけ君を調べる問題です。
制約もかなりゆるいので、だいたい何しても良さそうです。
「お菓子を持ってるすぬけ君」を調べて、その数を全すぬけ君の数から引く方針としました。
N,K = map(int,input().split()) all_snuke = [0] * N have_snuke = [] for i in range(K) : d = int(input()) li = [i for i in input().split()] for snuke in li : if (snuke not in have_snuke) : have_snuke.append(snuke) print(len(all_snuke) - len(have_snuke))
all_sunukeは最後でlen()を取るために使っていますが、Nでいいですね。
余計な計算をしてしまいました。
C - Peaks
かなり手間取ってしまった問題で、2WAでACとなってしまいました。
各展望台の高さと、展望台のfrom-toで道の情報が与えられるので、
「1本の道を使ってたどり着ける展望台よりもこの展望台が一番高いかどうか」 (文中では「良い展望台」)
を調べれば良いと理解しました。
制約はN,M < なので、二重ループは怪しいなという感触です。
「道がつながっていない展望台が存在しないとき」は、そのへんで一番高い(良い展望台)として扱うので、
条件に合致しない(良くない展望台)を探すこととしました。
以下は、コンテスト時に最初に提出したTLEのコードです。
N,M = map(int,input().split()) H_list = [int(i) for i in input().split()] not_good_list = [] AB_list = [] for i in range(M) : AB_list.append([int(i) for i in input().split()]) AB_list = list(set(list(map(tuple,AB_list)))) # for i in range(M) : for t in AB_list : A = t[0] B = t[1] if (A in not_good_list) : continue if (H_list[A-1] <= H_list[B-1]) : not_good_list.append(A) continue for t in AB_list : A = t[1] B = t[0] if (A in not_good_list) : continue if (H_list[A-1] <= H_list[B-1]) : not_good_list.append(A) continue print(N - len(not_good_list))
まず、パッと見でキモいのが以下です。
AB_list = list(set(list(map(tuple,AB_list))))
サンプルケースと回答が合わなかったのでとりあえず重複を省きました。
結果を見るとおそらくいらなかったのですが、その残骸が残っているのが上記の箇所です。
実際はそうではなく、入力データの前後を入れ替えたケースでも判断する必要がありました。
(forブロックの後半の部分です)
2 4と入力されても、2に対して検証することと、4に対して検証することが必要になります。
サンプルが通ったのでとりあえず提出しましたが、TLEとなってしまいました。
上記箇所がもしかして余計かと思ったので、削除して再提出しましたが、これもTLEとなってしまいました。
ACしたコードは以下です。
N,M = map(int,input().split()) H_list = [int(i) for i in input().split()] # not_good_list = [] not_good_set = set() not_good_count = 0 AB_list = [] for i in range(M) : AB_list.append([int(i) for i in input().split()]) for t in AB_list : A = t[0] B = t[1] if (A not in not_good_set) : if (H_list[A-1] <= H_list[B-1]) : not_good_set.add(A) not_good_count += 1 if (B not in not_good_set) : if (H_list[B-1] <= H_list[A-1]) : not_good_set.add(B) not_good_count += 1 continue print(N - not_good_count)
listに対してinをかけるのが重たい仮設があったので、とりあえずググりました。
調べてみたところ、setにすれば高速ということがわかったのでsetを採用したところACとなりました。
参考にしたのは以下の記事です。
前に見た記憶はあったのですが、助かりました。
qiita.com
こういうやつは簡単にデータ生成できるようなツールとか、
プロンプトに貼り付ける上限で詰まるとか、
そういうことがあるので環境はいい感じに整えておくと便利なのかなと思いました。
答えの正誤はさておき、TLEかどうかはデータ量で殴ってみればわかるような気がします。
ここまでで51:31でした。ちょっと悩みすぎましたね。
D - I hate Factorization
なるXが与えられるので、当該のA,Bの組み合わせを1つ答える問題です。
2乗の5乗は10乗なんだから、というノリでぐらいを調べればいいという
非常に雑な考察をして実装しました。
以下はWAのコードです。
X = int(input()) for a in range(-100,101) : powa = pow(a,5) for b in range(-100,101) : powb = pow(b,5) if (powa + powb == X) : print(a,b) exit()
論外なのが足し算と引き算を間違えていることです。
シラフでこういう凡ミスをかますあたり、
さすがセンター爆死Fラン朝寝坊常習犯勢という感じです。 何をやらせてもダメ。
足し算と引き算を直したあともWAとなりましたが、
さすがにこの長さのコードにバグをはらんでいる感じもなかったので
探索範囲を広げてみることとしました。
手元では遅かったのですが、±100を±1000ぐらいにして
制約上は大丈夫なはず、という気持ちでとりあえず提出しました。
ACでした。
大した考察もしてなくてごめんなさいという感じですが、
とりあえずレートが欲しかったのです……
X = int(input()) for a in range(-1000,1001) : powa = pow(a,5) for b in range(-1000,1001) : powb = pow(b,5) # print(a,b,powa,powb) if (powa - powb == X) : print(a,b) exit()
E - This Message Will Self-Destruct in 5s
解説ACです。
どうでもいいですが、問題文に出てくるAlDebaran はおうし座のα星です。クイズに出そうですが、星座は苦手です。
冬のダイヤモンドを形成する恒星の1つとして覚えておきたいと思います。
googleで愚直に調べると六本木のハンバーガー屋が出てきました。
六本木は全体的に飯も酒も高いですが、食べてみたいですね。
さらにどうでもいいですが、六本木といえばアントンビーというビアバーに時々行っていました。
制約がなので、愚直に書いたらダメそうです。
おそらく想定解はO(logN)とか、O(NlogN)とか、logが入る系のやつだと思いました。
手持ちのネタがなかったのでなんとか簡単な速度改善で済ませようとしましたが、
どうにもならずTLE、そして撤退という運びになりました。
enumerateを使うと多少早いとう情報は得たので、試してみましたがダメでした。
以下、TLEのコードです。
import sys input = sys.stdin.readline def main(): N = int(input()) height_list = list(map(int,input().split())) # print(height_list) match_count = 0 for a_i, a_height in enumerate(height_list) : for b_i, b_height in enumerate(height_list[a_i+1:], a_i+1) : # print(a_i,b_i, b_height) # b_height = height_list[b_i] height_sum = a_height + b_height no_diff = b_i - a_i if (height_sum == no_diff) : match_count += 1 print(match_count) if __name__ == '__main__': main()
そもそもheight_list[a_i+1:],が遅そうですね。
配列のスライスではまあまあ痛い目にあっています。
ACしたコードは以下です。
import sys input = sys.stdin.readline def main(): N = int(input()) height_list = list(map(int,input().split())) L = {} # i + Ai R = {} # j - Ai for i,Ai in enumerate(height_list) : l = i + Ai if (l not in L.keys()) : L[l] = 0 L[l] += 1 r = i - Ai if (r not in R.keys()) : R[r] = 0 R[r] += 1 count = 0 for l_key in L.keys() : if (l_key in R.keys()) : count += L[l_key] * R[l_key] print(count) if __name__ == '__main__': main()
式変形して、別々にパターン列挙しつつ
最後に組み合わせを計算する、というやり口のようです。
こういうのは今までのC問題でちょいちょい合った気がしますが、
あまり得意としないところで発想の引き出しにないので
覚えておきたいと思います。
結果
順位4338、パフォーマンスは797でレーティングは+36でした。
Highestを更新して531となりました。
クソWAがあって出来はどうなんという気持ちはありますが、
とりあえずパフォーマンスがまあまあ良いので良しとします。
もう今年もそろそろ半分が終わりますが、緑タッチか見据えられるぐらいの位置には行きたいですね。
ユーザも増えているので、厳しい戦いになりそうです。
お酒に酔ったので、以上を復習記事とします。
(ABC165 Dが簡単らしいので解説ACしましたが、コンテスト中では無理だろうなという気持ちになりました)