Toy と帽子と ADP BE

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

AtCoder Beginner Contest 126

ABCEの4完、そしてDが20/22WAで固まってました。(コンテスト終了時点)

(追記)結局今回もUnratedという判断になった模様です。個人的にはかなりレートを失っていることになり正直痛いのですが、データは消えても実力は消えないという言葉を胸に今後も精進していこうと思います。

各問題

A - Changing a Character

K番目の文字に、大文字と小文字の文字コードの差分である32('a' - 'A')を足して、その文字列を出力すればOKです。 C++だとs[k - 1] += 'a' - 'A';こういう感じで。文字列操作の超頻出テクニックです。

B - YYMM or MMYY

editorialでは入力を素直に整数として扱っていて、その方がよさげですね。

わたしは一文字ずつ区切って文字として判定してしまいました。落ち着け・・・。

くそ格好悪い私の提出コードを晒します(戒め)→https://atcoder.jp/contests/abc126/submissions/5452774

C - Dice and Coin

出力例1を見れば確率の計算方法はわかりますよね?あとはそれをコードにするだけです。

何回連続で表を出せばいいかを求めるための計算量はO(logK)で、全体でもO(NlogK)なのでC問題なのに深く考えなくても間に合います。

D - Even Relation

何がしかの木構造で解くんだろうなということは容易に想像がつくのですが、知識不足でどうにもならず・・・。

E - 1 or 2

  • Ziが偶数のとき、Ax+Ayは偶数、Ziが奇数のとき、Ax+Ayは奇数
    • 前者の場合Axが1ならAyは1、Axが2ならAyは2
    • 後者の場合Axが1ならAyは2、Axが2ならAyは1
      • これはAxとAyが入れ替わっても同じ

というわけで、どちらかがわかればもう一方も必ずわかります。 さらに

1 2 1
2 3 2
3 4 2

こういうのがあった場合、1がわかれば2がわかり、2がわかったので3もわかり、3がわかったので4もわかります。

要するに、同じ連結成分のどれか一つの数がわかると、それに対応するものすべての数がわかるというわけです。

なので、Union-Findにすべて突っ込んで、出来上がった連結成分の数がそのまま答えです。

個人的にはD問題より分かりやすかった(というかそもそもD問題できてない)ですし、実際ABCEの4完の人が結構いる模様。

F - XOR Matching

問題を読んで、回れ右しました。

まとめ

木を、グラフを、勉強しないといけない!!