AtCoder Beginner Contest 123で(2分足りず)2完でした
久しぶりに昨日ABCに参加することができました。
まだ2回のABCしか参加してないので灰色の下の方です。頑張らないといけないのですがTWICEの名古屋ドームライブが良すぎて、開始に遅刻した上にてんやわんやな回答をしてしまいました。
TWICEはとても良いので是非ハマってください。これは9人の良さ総合点が一番高い超神回です。
youtu.be
C問題でWA出てて終始唸ってたのですがギリギリに閃きました(間に合わず)。終わった2分後にAC通すことができたので悠長におにぎり食べてた時間...。
あと解説読んでみたら、本番中時間をかければDも解けたのでは、という感触なので復習も終わった後はマジで結構悔しかったです...。まあ終わってからでは何とでも言えますね。
いつもの第一印象
A：いつものAよりむずくない？？
B：いつものBよりむずくない？？？？
C：待機してる人>キャパ、の場所だけ注目すればいいのでは
D：愚直に実装するとTLEだ(ここがポイント)
ここがポイント！
計算量に関する先人のQiitaを少し読んでみたおかげで、「このくらいの数字ならこのくらい工夫しないとだめだな」みたいな考察か少し出来るようになっていました。D問題に立ち向かう意思と少しの力が芽生えたことを確認できて(結果はともかく)良かった回でした。
A - Five Antennas
直線状に並んだ5つの点のうち、距離kを超えてしまう2点はあるか、という問題。
愚直にすべて距離を計算するコードを自信満々で送ったら3つWAを出してしまい狼狽えました。落ち着いて再考することで「一番遠い2点の距離だけ見たらええやん」と気づいたので
- 落ち着いて真に検証する必要があるポイントを捉えてからコード化に移ること
- 考え及ばずな愚直実装であろうとせめてWAは出すなよ
という2つの再確認ができました。下はAC通った方のコードです。
input_list = [int(input()) for _ in range(6)] poles = input_list[:-1] k = input_list[-1] if poles[-1] - poles[0] > k: print(':(') else: print('Yay!')
Yayって何だ。
B - Five Dishes
最後の数字以外は一の位を切り上げる条件下で整数5つの最小和を求める問題。
今回のA問題とB問題、「出来るけどちょいしんどいな」っていう第一印象じゃなかったですか？？
menu = [int(input()) for _ in range(5)] mods = [food % 10 if food % 10 != 0 else 10 for food in menu ] max_food = mods.index(min(mods)) times = 0 for i, food in enumerate(menu): if i == max_food or food % 10 == 0: times += food else: times += (food // 10 + 1) * 10 print(times)
後から時間に追われず見返すと「変数名...笑」とか「無駄な部分あるな...」とか「この変数結局使ってへんやん」とか反省します...。
C - Five Transportations
要約がムズい。
待機人数がキャパよりデカい場所でのみ、(待機人数)÷(キャパ)の商の数だけ多く時間かかるな、と初手で思いました。
例) 7人待ちで次の交通手段が3人しか乗れないなら7 // 3 = 2分よけいにかかる
この余計にかかった時間を5(=全員が一発で最初から最後まで移動できるときの所要時間)に加えればいいと考え実装してみたのですが、1/3ぐらいのケースでWA...。
終了2分前に「最初の人数」と「一番のボトルネックになる場所」だけ比較すればいいじゃん！という閃き虚しく100分経過で終了。
めちゃくちゃ悔しがりながらおにぎり片手に実装したのが下のコードです。
people = int(input()) ways = [int(input()) for _ in range(5)] minimum = min(people, min(ways)) minutes = 5 if people % minimum == 0: minutes += people // minimum - 1 else: minutes += people // minimum print(minutes)
この問題、いつもブログ読ませていただいているu++さんの回答がマジで良いので見てください。最近ただのファン。
Bの回答もすげぇわ...。
D - Cake 123
3つの整数リストからそれぞれ1つずつ数を選んで取った和たちの中からデカい順にK個表示する、という問題。
この問題は少し計算量の話が見えやすい気がしますが
「各リストの長さがマックス1000だから全部計算してから並べなおして出力する愚直実装ではTLE食らうやつだ」
という見積もりが出来ました。始めたころを思い出すと勉強の成果を感じます。少しの成長も積極的に褒めていくスタイルで自分のペースを守りつつ頑張ります。
C問題で唸っていたので手を付けられませんでしたが、解説記事を読んで実装してみたらACでした！
初めてD問題で書いてみたコードをAC通せたのでとても満足です。
num_x, num_y, num_z, k = map(int, input().split()) x_list = sorted(list(map(int, input().split()))) y_list = sorted(list(map(int, input().split()))) z_list = sorted(list(map(int, input().split()))) xy_list = sorted([x + y for x in x_list for y in y_list], reverse=True)[:k] xyz_list = sorted([xy + z for xy in xy_list for z in z_list], reverse=True)[:k] for xyz in xyz_list: print(xyz)
