Toy と帽子と ADP BE

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

AtCoder Regular Contest 106

3完2WA。powさん・・・。

各問題

A - 106

単純に取りうる範囲(1018以下)を全探索すればよいです。ただし、C++で安易にpowを使うと誤差死します。(しました)

参考までに、Writerさんのツイートです。

そんなことで2WAだすとは・・・。競プロどんだけやってんですかって話ですね。反省。

それともやっぱりこういう問題はJavaで投げるべきか・・・。

B - Values

Union-Findを知っていますか?私は知っています。(慣用句)

値の移動は1ずつ行われるので、aとbのそれぞれの和が一致していればいずれ合わせられますし、一致していなければどうやっても合いません。

というわけで、Union-Findで連結成分作って、それぞれでaとbの和を集計して、一つでも異なる組があれば"No"で、すべて一致すれば"Yes"です。

C - Solutions

蟻本を持っていますか?私は持っています。(慣用句再び)

というわけで、この問題中の問題は、蟻本の最初の方にも載っている区間スケジューリング問題で、それを理解していれば高橋くんは正しく問題を解けていますが、青木くんは解けていないことがわかります。

よって、まずMが負はありえません。高橋くんのほうが最適解なので、青木くんの出した答えを下回ることはありません。また、Mが0のときは自明で、すべての区間を重ならないように置けばどちらのアルゴリズムでも同じ解答が出ますから、それを構築すればよいです。

問題はMが正のときですが、長ーい区間の中に、重ならない短い区間を置けばよいです。

|----------------------|
  |--|   |--|   |--|

例えばこれだと青木くんは1で高橋くんは3となります。余った分はいずれの区間にも重ならないように置けばよいです。

ただし、上記部分の構築にM+2の区間が必要なのでN-(M+2)<0のときは区間の数が足らず構築できないことに注意が必要です。

(追記)

M=0を特別扱いせずに組んでしまうと、N=1, M=0がコーナーケースになるそうです。(N-(M+2)<0となってしまうので)

私はたまたまM=0のときだけは自明じゃんとかいって最初にそれを構築するように組んだので助かりましたが。

D - Powers

数学はできますか?私はできません。

ということで、解けませんでした。

まとめ

Aが相当もったいなかったのですが、Cがあっさり閃けたので青パフォで水色復帰しました。やったぜ。

f:id:mdstoy:20201024225116p:plain