Toy と帽子と ADP BE

主にプログラミングに関わる話をゆるくエモくやっていきます

キーエンスプログラミングコンテスト2023夏(AtCoder Beginner Contest 315)

5完2WA1TLE。

各問題

A - tcdr

S を 前から読んでいき、a, e, i, u, o なら何もしない、それ以外なら出力する、でよいです。

B - The Middle Day

まず D の合計を求めて、それに 1 を加えてから半分にします(以下これを r とします)。あとは一つ目の月から 順番にみていって r 以下であればその月の r 日が求める月日です。r より大きければ、r からその月の日数を引いて次の月へ行きます。

C - Flavors

map<int, priority_queue<int>> とかで、味ごとのおいしさを管理します。

同じ味から美味しさが上位の二つを選んだ時の満足度をすべての味について求めたもの、および別の味の一番美味しいものの集合の上位二つを足して求めた満足度、のうちで一番満足度が高いものが答えです。

D - Magical Cookies

行と列について、残っているクッキーを map<char, int> で管理します。まず行について見ていき、mapsize が 1 (かつその値が 2 以上)ならば、その行に残ったクッキーはすべて同じ色なので取り除けます。取り除いた色については map で数を保存しておきます。列についても同じことをします。

最後に、各行について列で取り除いた色を取り除いた数だけ減算、各列について行で取り除いた色を取り除いた数だけ減算、をします。

これを操作ができなくなるまで繰り返して残ったクッキーの数が答えです。(行のマップに残ったものを集計すればよいです。)

E - Prerequisites

本iからその前提となる本へと辺を張った有向グラフを作ります。本1からdfsをして帰りがけに本を保存していけばそれが読むべき順になります。すでに読んだ本はスルーすることに注意です。(これで TLE をくらいまくり)

トポロジカルソートっぽいとは思ったんですが、もう長いことトポロジカルソート実装してなくてですね...。

まとめ

D が先に解けたのに全人類は E を通していたので焦りまくりましたが、なんとか E も解けたので got kotonaki。