AtCoder ABC157 参加記
お久しぶりです。
AtCoder ABC157 に参加したので参加記を書きたいと思います。
所感
今回は実装重めセットだったと思います。
個人的には A, B, C, D の 4 完でこんな感じでした。
まぁまぁ温まったのでこの調子で精進していこうかなと思います。
では解説の方にいきましょう！！
A 問題
高橋君は、全 N ページから成る書類を両面印刷します。両面印刷では、1 枚の紙に 2 ページ分のデータを印刷することが出来ます。 最小で何枚の紙が必要か求めてください。
解答
2 で割って切り上げ演算をしてあげれば良いです。
ある数 x を n (≠ 0) で割った際の切り上げ演算は次の式のようになることを使えば解くことができます。
切り上げの式 :
提出したコード
B 問題
3×3 のサイズのビンゴカードがあります。上から i 行目、左から j 列目の数は
です。 続けて、 N 個の数
が選ばれます。選ばれた数がビンゴカードの中にあった場合、ビンゴカードのその数に印を付けます。 N 個の数字が選ばれた時点でビンゴが達成されているか、則ち、縦・横・斜めのいずれか 1 列に並んだ 3 つの数の組であって、全てに印の付いているものが存在するかどうかを判定してください。
解答
もうすでに実装重め感が出てますね。。。
入力を取ったら、あとはビンゴの判定をするだけなのです！
ビンゴの判定の実装が少し面倒ですが頑張りましょう。
ここで縦と横のビンゴのパターンを for 文で調査して、斜めのパターンは直打ちしました。
提出したコード
C 問題
以下の条件を満たす 0 以上の整数が存在すれば、それらのうち最小のものを出力してください。そのような整数が存在しなければ、 -1と出力してください。 十進表記で丁度 N 桁である。(0 は 1 桁の整数とする。その他の整数については、先頭に 0 をつけた表記は認めない。) 左から数えて
桁目は
である。(i=1,2,⋯,M)
解答
三井住友信託銀行プログラミングコンテスト2019 の D 問題の Lucky PINと似ているなというのが最初の感想でした。
ですが、全探索だとプログラムを書くのが面倒そうだったので条件を 1 つずつ処理していく方針をとりました。
が！！！ N = 1, M = 0 のパターンの処理を書き忘れて 1 WA を出しました。。。
提出したコード
D 問題
とあるSNSに、人 1、人 2、⋯、人 N が登録しています。 この N 人の間には、M 組の「友達関係」と、K 組の「ブロック関係」が存在します。 i=1,2,⋯,M について、人
と人
は友達関係にあります。この関係は双方向的です。 i=1,2,⋯,K について、人
と人
はブロック関係にあります。この関係は双方向的です。 以下の 4 つの条件が満たされるとき、人 a は人 b の「友達候補」であると定義します。 a≠b である。 人 a と人 b はブロック関係に無い。 人 a と人 b は友達関係に無い。 1 以上 N 以下の整数から成るある数列
が存在し、
であり、
であり、i = 0, 1, ⋯, L−1 について、人
は友達関係にある。 人 i = 1, 2, ..., N について、友達候補の数を答えてください。
解答
これに 70 分近く時間を溶かしました。。。
まず条件の最後が非常にわかりづらい。これは人 a と人 b の友達を辿ることで互いに辿り着けるということだと解釈しました。
最初にグラフで関係を管理しようと考えたのですが、友達候補の表現が難しそうだったので集合と言えばということで Union Find Tree で管理することにしました。
方針としては友達関係を Union Find Tree で管理し、各人iのブロックに関しては隣接リストで保持、また、各人の友達の数を把握しておきます。
各人i に対してその人が所属するUnion Find Tree の大きさから友達の数と自分自身を引きます。
さらにその人と同じ Union Find Tree に所属するブロックしている人の人数を引いてあげたものが答えになります。
提出したコード
