Toy と帽子と ADP BE

主にプログラミングに関わる話をゆるくエモくやっていきます

AtCoder Beginner Contest 131

5完で、初の青パフォ。前回のレート減少をのしつけて返してやりました。

各問題

A - Security

単純に隣り合う文字を比較していって、同じものが一つでもあるなら"Bad"、一つもないなら"Good"です。 ループを回してもいいし、4文字限定なのでif文3つ並べてもOKですね。

B - Bite Eating

ひとつだけ抜くリンゴは絶対値が一番小さいものにすると題意を満たすので、それを探して、すべてのリンゴの味の和から抜くリンゴの味を引けばいいです。

C - Anti-Division

「割り切れないもの」の数は全体の数から「割り切れるもの」の数を引けばいいです。

「割り切れるもの」の数は、Cの倍数の数 + Dの倍数の数 - CとDの公倍数の数、です。Cの倍数の数 + Dの倍数の数だけでは、CとDの公倍数についてダブって数えてしまうことに注意。(包除原理)

求めるのはA以上B以下の整数についてなので、B以下についてとA「未満」についての「割り切れないもの」の数を求めて、前者から後者を引けばいいです。A「未満」にしないとちょうどAのときが抜け落ちてしまうので注意です。(私はサンプルに該当するケースがなかったらやらかすところでした・・・)

D - Megalomania

締切時間でソートしてから、前からひとつずつ確認していけばOKです。

ソース見てもらったほうがわかりやすいかも -> https://atcoder.jp/contests/abc131/submissions/6062745

これ、Cの300でもいいのでは?

ちなみに、editorialの実装のようにAとBを逆に格納するとsortの比較関数を書かなくて済むのですが、私はあとで混乱する可能性があるので避けるようにしています。 変数名をわかりやすく付ければいいだけの話なんですけど、競プロの場合その手間を惜しんじゃうんですよね。

E - Friendships

Kが取りうる最大値はN * (N - 1) / 2 - (N - 1) です。これがどういう状態かというと、例えばN=5のとき

  2
  |
3-1-4
  |
  5

こういう状態です。(いわゆるスター) この場合、2-3, 2-4, 2-5, 3-4, 3-5, 4-5 の6つの距離が2です。 あとは、ここから辺を一つ足すごとに距離が2の2点が一つ減っていくので、与えられたKに合うように辺を適当に足せばよいです。

結構最近に、すべてのN * (N - 1) / 2個の辺がある状態から題意に合わせて間引いていくという問題が出題されていたのを覚えていたので、割とすんなりこの発想に至れました。復習は大事ですね。

F - Must Be Rectangular!

私はx座標ごととy座標ごとのmapを用意して愚直に探す、ということをやろうとしたのですが、おそらく嘘解法な上にTLEも出ていました。とほほ。

あとでeditorial読んで勉強します。

まとめ

当たり前ですけど、復習は大事。超大事。

初の青パフォで超回復達成。次回も同程度のパフォならレート水色になるので、昇格戦ということになります。頑張る。

f:id:mdstoy:20190622230041p:plain