ABC188の感想

AtCoder Beginner Contest 188に参加しましたので、その感想を書いてきます。問題はこちらから。

Tasks - AtCoder Beginner Contest 188

結果はこんな感じでした。

a-dの4完（0wa）

順位：2646 / 7831
パフォーマンス：942（緑）

今回も緑パフォーマンスを出すことができました。これで、晴れて緑コーダーとなりました（気が向いたら振り返りもかねて色変記事を書きます）。嬉しいといえば嬉しいのですが、今回のD問題もうちょっとうまいことできたなーっていうなんか心残りがあるのが悔しいですね。なんか灰色から茶色のときもにたようなこと言ってた気がしますが、、、

とりあえず、今回の感想をば。

A問題

3ポイントを決めて逆転できるかの問題です。問題文をみて

小さいほう→+3→勝てるか？

っていう流れが頭に浮かんだのでそのまま書きました。こういうとき、私はswapを使います。シンプルにかけて私は好きです。

B問題

内積が0かを求める問題です。問題をみたときに、内積=0だから直角？三角比でも使うんですかね、、と少し身構えましたが計算方法が書いてありました。AtCoder様は優しいですね。

ということで計算式をそのまま実装しちゃいましょう。オーバーフローの判定が面倒だったので一応long longにしましたが、たぶんintに入りますね。

C問題

トーナメントの問題です。トーナメントといえばarc109cでじゃんけんトーナメントに打ち砕かれているので、嫌な気持ちで問題文を読み始めました。

制約をみるとn=16でした。ということで、人数は2^16≃6*10^4です。これを見た瞬間に勝利を確信しました。愚直にやろう。

ということで、1回戦第一試合から準決勝第二試合まで全部判定しました。これも特に問題なく解けましたとさ。

D問題

こいつが曲者でした。少なくとも私にとっては、、、

考察した順番に書いてきます。

まず、この問題をどこかで見たことあるなと思い、過去問漁りを始めました。その結果、abc183dの「water heater」と大変似ておりましたのでこの解法になぞらえて解こうと決意しました。

183dではimos法という解法を用いて解いていますので、当然「これはimos」を実装すれば解けると思います。私はそう思いました。ただ、問題なのが時間の制約が

a<=10^9

であったことです。imosでは時間に関して入出力を管理するのですが、10^9までを管理すると時間が間に合いません。ということで、この方法は断念。

次に、183dの別解として時間でソートしてシミュレーションをかけてあげるというものがありましたので、そちらで解こうと試みます。

nはそんなに大きくなかったため時間的には大丈夫だろうと思って実装したのですが、如何せん答えが合わなくて困りました。

このとき、a,b+1で管理してました。

原因は何だろなって思ったところ、同じ時間のクエリを分けて処理してるのがいけないという結論に至りましたので、

map<int,vector<int>> m

として、keyに時間、要素をvectorで管理して同じ時間を一括で管理できるようにする。というデータ構造で殴る作戦に出ました（結論からするとこの処理必要ありませんでした。）。

ただ、これでも結果が合わない、合わない。だいぶ焦ってました。

次に、最後のbの処理がおかしい、b+1してるんだから、最後は+1だけ余分な時間がある。というわけわからないことを考え始めて沼に嵌ってました。

さすがにやばいと思って、自分でテストケース

4 100000
1 3 10
1 5 20
2 3 30
3 5 40

を絵をかきながらやりましたところ、どうやら時間は

a-1とb

にする必要がありそう、、？ってなりました。この時点で残り9分でした。

上記の通りに修正したらあっという間に通りました。残り4分の出来事です。

なんとか解くことができましたが、もうちょっとすんなりと通したかったという気持ちが拭えません。まだまだ頑張らねば。

今回で緑になりましたが、頭打ちも見えてきてしまいました。ここからが本番ですね。ひとまずはレートを維持しつつ、少しずつ水色パフォを出せるように精進していきたいと思います。