ABC194の感想
AtCoder Beginner Contest194に参加しましたのでその感想を書いていきます。問題はこちらから。
結果はこんな感じでした。
4完（1WA）
順位：2122 / 7892
パフォーマンス：1062
実力通りの結果という感じでしょうか。前回のコンテストで失敗してちょっとドキドキしながら臨みました。特に今回のコンテストはAとBがなんか解きにくいといいますか、読みにくいといいますか、、いきなり出鼻をくじかれてしまって焦りました。その中でもまずまずの結果に収めることができましたのでまあ及第点としましょう。よくがんばりました。
ではいきます。
A問題
アイスの種類を判定する問題です。これ問題文が頭に入ってこなくて焦りました。まず大事な単語として「乳固形分」「乳脂肪分」「無脂乳固形分」の3つが登場します。いきなり頭がパニックになりました。これらの成分の割合から、アイスの種類を判定します。
やることは if 文にて分岐を書いてあげるだけなのですが、もう一つ困りました。一つ引用します。
乳固形分が15パーセント以上、乳脂肪分が8パーセント以上含まれるものを「アイスクリーム」とする。
これの「、」は「かつ」なのか「または」なのか悩みました。他の文章と一緒に見ると、おそらく「かつ」なんだろうなーと思いましたが、ACと出るまではドキドキしました。これ思った方ほかにもいますかね。
B問題
2つの仕事を判定する問題です。これも少し悩みました。まずO(N)で解こうとすると
・aの最小値と人の番号
・bの最小値と人の番号
が必要で、番号が同じときにはa+bになって、もしかしたら2番手を起用するともっと早いかも
みたいなことを考えてしまって、結構時間を使いました。
結局、制約を見てにっこり。
全探索しました。おしまい。
C問題
差の二乗の和を計算する問題です。こんな感じの問題は他にも見たことあるので、まあすぐ解けるだろ、って思いました。実際わりとすんなりと解けました。
まずは、入力例を使って実際に計算過程を書きながら手計算をしました。そうすると、まとめられそうなところがいくつか出てきました。あとはそれらを累積和で表現してあげればおしまいです。
累積和をとるときに「インデックスを合わせること」と「逆方向から計算する」ことに気を付ければなんとかなるでしょう。そこがややこしくてよくバグらせてしまうのですが、、、
D問題
グラフの問題か、と思いきや確率の問題です。問題文をぱっとみてこう言い変えました。
「1~nまでのサイコロがあります。全部の目を出したい。もう1は出てるよ」
このときのサイコロを振る回数の期待値を求めます。確率 p と期待値 X はpX = 1の関係がある（この1はその面が出る、出ないの0,1）ので、X =1/pです。新たな面が出るごとに、まだ出てない面が出る確率は下がっていくので、それを更新しながら足し合わせれば答えです。1はもう出てるので、100%でる1に1回消費したと考えて1を引きましょう。
E問題
ある区間に出現してない数の非負整数の最小値を求める問題です。
これは解きたかったなーと思ってます。まず、BITかセグ木で無理やり殴れないかなーと2次元座標に点を打って考えましたが、いったん保留。その後、制約が4sであることに気づいて、set<pair<個数,数字>>みたいに愚直にやろうかなと手を動かしました。個数が0のものが先頭に来るので、一番前に来たやつの数字（second）でいけるな。と。まず、0~mまでに出現する数をカウントして、setに入れました。出現しない数も個数が0としてsetに入れました。
そのあと、先頭を取る。区間がずれたことによる個数の変化を反映（eraseしてinsert）。また、先頭を取る。の繰り返しです。
setはこれらの操作をだいたいlog(N）でできるので制限時間 4s なのも加味してなんとか間に合わないかなーと淡い期待をしてました。ダメでした。
計算量（正しい自信はありません）は初めにすべての数字を入力するところで Nm = 1.5*10^6としてNmlog(Nm)かMにもよりますが、(N-M)log(Nm)の定数倍ですね。間に合わないか、、
F問題
見ることも能わず。
あとがき
満足！とはいきませんが、現状こんなもんでしょう。最近、精進をばっちりとさぼってますので伸びないのも当たり前です。今日問題を読んだ時も、なかなか頭に入ってこなくて、何回か読み直す、情報が整理できないという感覚がありました。慣れてないという感じです。おそらくこれは演習量が足りてないせいですね。楽しくやるのはもちろんですが、ある程度は自分を律したいです。ということで今週は毎日1問は絶対解きます。最後となりますが、参加したみなさま、お疲れさまでした。
この記事が気に入ったらサポートをしてみませんか？