ABC199の感想
AtCoder Beginner Contest 199（Sponsored by Panasonic）に参加しましたのでその感想を書いていきます。問題はこちらから。
結果はこんな感じでした。
ABC(42:27+3WA)
順位：3534/8716
パフォーマンス：777
パフォーマンスがジャックポッドですが、まだまだですね。全然レートが上がりません。今回のようないわゆる「はやとき」の会は苦手です。どうやらそうとう解くのが遅いようです。ただ、難しい問題に十分時間をかけて臨むことができたので、その点は良かったのかなと。
なんだかんだで楽しかったです。
では感想いきます。
A問題
数式が与えられてますのでそれを書きましょう。オーバーフローの心配もありませんので、かけばおしまいです。
B問題
ちょっと悩みました。はじめ何を思ったか、max(A)<=x<=min(B)と勘違いをしまして、全然サンプル合わないなーとかやっていました。
結局、制約が小さいので、Ai~Biの全てを+1することを全クエリ分行って、全部で+1された、つまりその値がnのものの数を数えました。
なんとかACよかった。
C問題
文字列を入れ替えたりする問題です。
愚直にやってネックになるのはT=2のときですね。全ての文字を一つずつ入れ替えていては、間に合いません。
ですので、T=2の時には、前半部分と後半部分を一気に入れ替えられるように、前半部と後半部で分けて保持しました。そうするとT1のときにインデックスがちょいとややこしくなりますので、後半部の際には-=nとしました。
あとはなんでしょう。完全に別の文字にするとifの分離がめんどくさいので、配列の0と１のインデックスに入れました。
ただ、この配列の要素をなぜかn個分確保してました。n*n要素になりますので、実行時エラーが発生します。これに気づかず、3WA。悲しいです。
それに気づいてようやくAC。とってもじかんがかかりましたので、Dを解かねば！気合が入ります。
D問題
グラフの着色問題です。Eも見ましたが、グラフの方がとっつきやすいのでこっちを選びました。
パッと見てまず思ったのがNの小ささです。N<=２０でしたので、これ全部見ればとけるんじゃないのかとなりました。ということで、全部試す感じで、まずBFSを書きましたが、tupleにvectorを突っ込むところでつまづいたため、DFSに変更。一応書き終わりましたが答えが合わないのなんの。
色々と考えてたところであることに気がつきます。サンプル３の答え大きいなあ。
着色をしていき、全部塗れたら++ansをしていますので、答え分のループは最低限必要です。これでは間に合わない。困りました。
しかもここでさらに気づきます。全部連結してるわけではありません。
途方にくれました。ここでグーグル先生に聞くと、次数の大きい順にやるとなんかいいらしいよ、と教えてくれました。ごちゃごちゃと書きますがここで時間切れ。
悔しいですね。
E問題
ちょっとだけ見ました。Dでいいや、となりました。
F問題
ちょっとも見てません。
あとがき
REに苦しみました。まあ完全に私が悪いのですが、、
以前に、速解きか問題数かみたいな診断があったのですが、私はかなりのんびりな方らしいです。自分でも自覚しています。ですので、3完速解きみたいなコンテストだとどうもパフォーマンスが出ないですね。こればかりは、早く解けるようにするしかないので、練習あるのみです。
でもだからといって、つまんなかったか、といわれると全くそんなことはなく、わっかんないよーとかぼやきながら一時間弱グラフを書きながら考えるあの時間、明確な制限時間に追われながら早く早くと焦ってしまうあの時間はとっても好きです。このくらいの方が解けた時嬉しいですもんね。少しずつでいいので、問題をこなしていき、このくらいのレベルの問題に太刀打ちできるようになりたいものです。
あとは、解説記事についてです。ABC198でわかりました。解答記事の執筆は平日にはできないです。頑張ればできるのですが、家に帰ると眠くて眠くて、、幸いなことに明日は日曜日ですので、可能な限り書き終えてしまうつもりでいます。応援のほどよろしくお願いします。
ABC１９９に参加した方も、都合が合わなくて見送った方も、そもそも競技プログラミングをやっていない方もここまで読んでいただきありがとうございました。私は今から公式解説を見ながら解けなかった問題考えたいと思います。
この記事が気に入ったらサポートをしてみませんか？