https://bcu30-2018.contest.atcoder.jp/tasks/bcu30_2018_a
概要
1個ずつ数字が書かれた球がA個ある。これを1個ずつ数字が書かれたB個の球にしたい。ただし変換は以下の2種類。
- 数xと数yが書かれた2個の球を数x * yが書かれた1個の球にする
- 数xが書かれた1個の球を、(x%y==0となるような適当なyを選んで)数yと数x / yが書かれた2個の球にする
この条件で最終状態を達成できるか？AおよびBは9以下、書かれている数はそれぞれ100以下。
解法
- 探索…は必要ないです。乗算と余りのない除算のみで構成されるということは、素因数です。素因数の組が等しい…つまり、状態Aの数の積と状態Bの数の積が等しければYesです。
- 多分、制約は、積がint64に収まるようにってことなんだと思う。
感想
- 気づきづらい。
- 本当は「積が等しいかどうか判定せよ」という問題だったけど、がち勢が多かったので難しくしたらしい。
- おかげで体感300点ぐらいでした…つらいよぅorz
200829追記
- このコンテストは一生のうちで最後のオンサイトコンテストだと思っていたので、総合5位になってしまったことはとても残念だった(3位まで賞金)。