AtCoder Beginner Contest 155に参加しました
ABC155のコンテストサイト
atcoder.jp
A問題
問題
数が3つ与えられるので、「ある2つが同じで残り1つがそれらと違う」かどうかを判定する問題。
人間の目で見られれば簡単なのだが、プログラムを組むとなるとちょっと面倒。
10秒ほど方針を悩んだ結果、この条件は3つの数が2種類であることと同値であるという天才的発想に至り、3つの数をsetにぶち込んで無事AC。
B問題
問題
N個の数が与えられて、それら全てが「偶数ならば、3または5で割り切れる」を満たしているか判定する問題。
コードは、N個の数を順番に見ていって条件が満たされなかったらそこで打ち切る方針で書くので、この命題の否定を考える必要がある。
元の命題は「全ての数について『奇数 または 3の倍数 または 5の倍数』」なので、否定は「ある数について『偶数 かつ 3の倍数でない かつ 5の倍数でない』」となる。
C問題
問題
文字列の集合S(|S|≦200000)が与えられて、この集合の最頻値を(複数個あるなら辞書順で)求める問題。
文字列の個数についての問題なので、とりあえずmap<string, int>に突っ込んでおく。
提出したコードでは出現回数の最大値とその最大値回出現する文字列を同時に求めているが、先に最大値だけ求めて後から文字列を求めるのでもいいと思う。
D問題
問題
N(≦200000)要素の数列Aが与えられる。この数列の要素の全ペアN(N-1)/2個のそれぞれの積のうち、K番目に小さいものを求める問題。 過去のARCで既出
個人的に大詐称問題、実装難易度も考察難易度も500相当かそれ以上はあると思う。
解法のベースは二分探索で、「ペアの積のうちx以下のものがK個以上であるような最小のx」が求められれば良い。
ペアの積のうちx以下のものは、
⑴ xが0以上の時、「ペアの積が0のもの」「ペアの積が負のもの」は全部数えて、「ペアの積が正のもの」は一個を決めればもう一個の範囲が決まるからにぶたん。
⑵ xが0未満の時、「ペアの積が負のもの」だけ数えればよく、これはさっきと同じように一個を決めればもう一個の範囲が決まるからにぶたん。
にぶたん in にぶたんで計算量にlogが2個かかって怖かったけど、612msで通った。流石C++、爆速。
しゃくとりとか使えばlogが1個落ちるのかもしれないけど、これでも通ったしACは正義ってことで。
E問題
問題
10の累乗円玉のみが使える世界でN(≦101000000)円の商品を買いたい時、支払いに使う小銭とお釣りに使う小銭の合計枚数を最小化する問題。 yukicoderで既出
Nがすっごい大きいので、まず桁DPかなっていうインスピレーションが浮かんだ。
払う金額と貰う金額を計算しながら桁DPをしていくのがよさそうなのだが、ここでセオリー通り桁DPを上の桁から計算していくと繰り下がり計算が面倒になってしまう。
繰り下がりといえば筆算、ということで普段筆算する通りに桁DPを下の桁から計算していくことにすると、上手く行く。
普段の桁DPでは「今見ている数がNより小さいか」というis_lessのような引数を持つが、今回も同じようにis_lessを使えばよい。(提出したコード中ではis_lessの代わりに「今見ている数がN以上か」というis_largeを使っているが)
絶対500点ではないと思う。公式解説が天才だった。脱帽。
このDPは現在の桁(1000000通り)、is_less(2通り)、繰り下がり中かどうか(2通り)の3つの引数持っていて、遷移が0-9の10通りあるので、1000000*2*2*10=4*107通り。
うっひゃーギリギリ、と思ったが、爆速C++さんは206msで通してしまった。余裕しかなかった。
F問題
問題
数直線上にN(≦100000)個の爆弾があり、それぞれがオン/オフのどちらかである。M(≦200000)個のコードがあり、各コードは切られると数直線上のある区間内の爆弾のオンオフを反転する。爆弾を全てオフにできるか反転し、できるならコードの切り方を求めなさい、という問題。 有志コンで既出
とりあえず最大109の座標は扱いづらいので爆弾は位置でソート、コードは座圧して爆弾の区間にする。
区間を反転する問題も扱いづらいので、隣接する爆弾のオンオフのXORを考えると、区間内の爆弾を反転させるという操作はこのXORを2個反転させるということに置き換えられる。
よって、問題は次のように言い換えられる。
・長さN+1のbit列と、1≦x<y≦N+1を満たす整数のペア(x, y)がM個与えられる。
・ペア(x, y)を一つ選び、x番目のbitとy番目のbitを反転させる操作を何回でも行える。
・bit列を0のみにすることができるか。
ここで唐突だが、i番目のbitを頂点iに、(x, y)のペアを頂点xと頂点yを結ぶ辺に対応させ、N+1頂点M辺の(無向)グラフを作る。
頂点iはi番目のbitが1なら黒に、0なら白に塗る。
この時、ある辺の両端の頂点に対応するbitを反転させる操作は、両端の頂点の色を反転させる操作だといえる。(この操作を以降は「辺を反転させる」と呼ぶ。)
ここで、辺を反転させても黒頂点の個数の偶奇は変わらない。なので、黒頂点の個数が奇数であるようなこのグラフの連結成分があった場合、その連結成分内の黒頂点はずっと奇数個のまま。
この場合は即OUTで、-1を出力して解散。
全ての連結成分内の黒頂点の個数が偶数個の場合、連結成分内の辺を上手く反転してあげると連結成分内の全ての頂点の色が白くなる。具体的には、次の手順のように反転する辺を選ぶ。
1. 連結成分の適当な全域木を取る。
2. この木の適当な頂点を根とする。
3. この根付き木の各辺について、根から見てその辺より奥にある黒頂点の個数が奇数ならこの辺を反転し、偶数なら反転しない。
ちなみに未証明で提出したが、提出したらACが返ってきた。ACは証明。
最後に
後半3問がかなり詐称してた気がする。
あと、DもEもFも全部問題傾向がバラバラで面白いセットだった。実装のD、知識応用のE、考察重ねのF。
コンテストの成績は4位だった。これで順位表1ページ目スタンプが1つ埋まり、残りが3, 11, 13, 16, 18, 20位になった。
