ABC390 参加結果・感想
こんにちは、茶色コーダーの「さわーくりーむおにおん🧅」です。
今日も精進してますか？？
昨日開催されたABC390に参加しましたので、コンテスト中に考えていたことや感想をまとめてみました。参考になれば幸いです‼‼
2025/01/26 10:00
投稿を優先して記事を書いています。一部テキトーな箇所もありますが適時更新していきます。
A問題
【問題】
1~5を並べた配列がある。この内隣り合う要素を一度だけ入れ替えて昇順に並べ替えることが出来るか判定する。
【考察・感想】
昇順の配列を用意して位置が違う場所が2か所であること＋その位置が隣り合っていることが条件と思ってコードを作成。もう少し簡潔に書けそうだなと思ってしまった。
【提出コード】
コンテスト中：https://atcoder.jp/contests/abc390/submissions/62040788
B問題
【問題】
配列Aが与えられる。等比数列であるか判定する。
【考察・感想】
公比が全て一致するか判定するだけ。単純に次の項を前の項で割るとWA×1(いわゆるAtCoder最高の瞬間)になった。割り算の精度の問題だと思ったので整数内での計算かDecimalを使うことを思いつき、後者でAC。
【提出コード】
https://atcoder.jp/contests/abc390/submissions/62046630
割り算の精度に関しては下記の記事を先週読んでいたので、参考にさせてもらいました。公式解説のように式を変形するのが定石な気もしますが。
C問題
【問題】
グリッドがあり、マスが「黒」「白」「どちらにも塗られていない」の3種類ある。塗られていないマスを適切に塗りつぶして黒マス全体が長方形になるか判定する。
【考察・感想】
黒マスのx座標とｙ座標の最大値と最小値を記録し、その範囲内に白マスがないことだけ判定すればいいと思ったが、先にＤ問題に時間かけてしまい間に合わず…
【提出コード】
https://atcoder.jp/contests/abc390/submissions/62112196
D問題
【問題】
N個の袋が存在し、各袋にはAi個の石が入っている。二つの袋を選び、片方の袋に石を全て移動する操作を何度でも繰り返してよい。この時、各袋の石の個数Biについてすべての排他的論理和を取ると、何種類の値が得られるか？
【考察・感想】
Nの数が12と少ないので全探索できそうだなと思った。すべての場合を列挙するには、「N個の袋をN個以下のグループに分ける総数(ただしグループは区別しない)」で求められそうと思い、列挙してみたが重複がありTLE。コンテスト後にmore_itertoolsのset_partitionsを使ってAC。制限時間ギリギリなので、解説の解法も勉強します。
【提出コード】
https://atcoder.jp/contests/abc390/submissions/62105467
E問題
【問題】
N個の食材があり、それぞれビタミン1,2,3のうち一つが含まれている。高橋君が摂取するカロリーが合計X以下になるようにN個のうちいくつか選んで食べることが出来る。このとき「ビタミン1,2,3のうち最も摂取量が少ないものの摂取量としてありえる最大値」を出力。
【考察・感想】
問題文を読んで動的計画法だな…とは思ったがビタミン3種類を管理＋最小値を判定する方法がわからずに諦めました…コンテスト後に解説＋他の方の解答読んでupsolveしました。
【提出コード】
https://atcoder.jp/contests/abc390/submissions/62112540
まとめ
今回はA,Bの2完という厳しい結果になってしまいました…(レートもごっそり持っていかれる)。diffを見てみると時間をかけたD問題が青、問題を見て諦めたＥ問題が水なのでコンテスト内に解くのは難しかっただろうなという印象です。
知識が増えるほど「これも解けそう」という問題は増えるのですが、結局解き切れないということも増えてきました。コンテスト内での立ち回りも考えなくてはなぁ…と思った土曜の夜でした。
また粛々と精進していきます！
ではでは