ABC304 振り返り

東京海上日動プログラミングコンテスト2023(AtCoder Beginner Contest 304)

コンテスト自体はジャッジシステムが詰まってUnrated扱いになった。
ABC完はしているので個人的にはRatedでいいんだけど…(いつもこれだ)
ただ、最近Unratedになりまくってるのでがんばえー…という気がする

A - First Player****

データを読み込みながら最小の年齢の人を見つけて、見つけた人のインデックスを覚えておいて
NAMES[index:] と NAMES[:index] をprintすればおっけー!
配列の操作ミスってなんか妙な出力を出したりしてうわーって感じだった。

https://atcoder.jp/contests/abc304/submissions/41945232

B - Subscribers

Subscribers… なんだろうと思ったらもしかして:youtube
10のn乗以下だったら 10の n-3 乗以下を0にしちゃう感じで解いた。
もしかして、Aより簡単…?なんならif文の羅列してもいいわけだし。

ちょっとアレなんだけど、同じコードをPythonとPyPyで提出しちゃって、結果を比べてみたらPythonのほうが早くて省メモリだった。あれ・・・やっぱりPythonで提出で良いのでは… ダメならPyPyを試すみたいな感じで。
https://atcoder.jp/contests/abc304/submissions/41954680

C - Virus

なんとなく、前に爆弾の爆発的な感じで似たような問題があったような…
でも、こっちの方が事故率が低そうな問題だなという感じ。
なお、この問題を解いているあたりからジャッジシステムが詰まって、コードテストが30分返ってこなくなったりして正直萎えた。
が、そもそも、AtCoderの問題はローカルで動かしやすいようになっているのだからローカルでテストすれば早いではないか。ということに気がついた。 簡単に成果を書くと、python3 code.py < in.txt とやればいいだけ。次からはこれで高速化できそう。

で、肝心の問題。
解き方、思いつきませんでした。なんとなく近所のやつだけを処理する必要があるのかなぁみたいなことは思ったものの… それを絞るためにはなんかDBのindex的なのを用意しないとダメかー面倒だなぁ…みたいな感じになり、とりあえず素直に書いて、TLEしたら処理数を絞るような実装を入れようという戦略で行くことにした。

結果。普通にACしてしまった。
最初に感染した人の近くにいるか全員チェックしつつ、感染していたら感染した人リスト(検索に使うのでsetだけど)とdeque(次にチェックする人キュー)に入れておいて、一人ずつスキャンしていく感じ。チェック時に、すでに感染していたらチェックする必要がないのでスキップ。っていう処理を入れていたのが決め手だったかも。

なお、提出が119分という滑り込み。20分くらいWJになっていたけど、無事に判定されてACに変わりましたとさ。滑り込み提出は有効らしい。

まとめ

そろそろDP(動的計画法)を学んでD問題以降にチャレンジできるようにしたほうが良い気がしてきた。しかし、今回もC問題の提出が119分だったわけで(ジャッジが詰まったのを除外しても60分は経過してそう)そもそも問題を解く速度が遅いという疑惑がある。
まあ、とにかく今は茶色を目指して続けることが大事。

最終更新 2023/07/23 15:48:00 JST
Yakumo Saki
Built with Hugo
テーマ StackJimmy によって設計されています。