naoya_t@hatenablog

いわゆるチラシノウラであります

〈ARC埋め〉AtCoder Regular Contest 094

典型問題に弱いのは明らかなので、ARC過去問をちまちま埋めていこうと思う。

  • Cは気が向いたら箸休めに
  • Dは早解き練習
  • Eは問題読んで方針立てて解説読む練習

今日は、ARC094(2018/4/7開催。出てない…Google Code JamのQualification Round中にやってたやつだ)の問題を解いてみる。
作問はDEGwerさん。


所要時間から見て、実際に出ていたら2完(80分前後で1000点なので240位前後、パフォーマンス1800ぐらい)かな。

D - Worst Case (700)

とりあえずD早解き、とか思ってDから開いたんだけど、この回はD=E=F=700点なのね。実際Eの方がAC数が多かったみたいで。
「1回目A位・2回目B位 を除いた上位m人」を片方は上から、もう片方は下から並べて、その積がAB未満になるかどうかを(A,Bとmの位置関係を考慮した場合分けをしつつ)二次不等式で調べる関数p(x)を書いてx:[0,2√AB+1)ぐらいで二分探索。関数p(x)内にラムダ式が沢山。
→AC (1:05:15)
https://beta.atcoder.jp/contests/arc094/submissions/2578282
いや、いくらなんでもこれじゃあ面倒くさすぎだろ

実際もっと簡単に解けるんだけど、解説ちょっと意味わからない。
kmjpさんの説明の方が人類にはやさしい。

C - Same Integers (300)

ちょっとDがハードだったので箸休め的にCを開く。
3つのうちの2つを+1するってのは残りを-1するのと等価だよね、と思って
「どれか1つを+2する」or「どれか1つを-1する」という操作と考える。

  1. 1する操作は+2-1の組み合わせ(2手)で。

ゴール決め打ちで手数を計算する。ゴールとしては適当な範囲をとる。で、その最小値。
→AC (0:14:20)

解説読んだ。なるほど、A+B+Cのパリティが不変。ゴールはmax(A,B,C)かmax(A,B,C)+1のどちらか。
A≦B≦Cとしよう。

A+B+CのパリティがCと同じ場合:A+Bが偶数なので、B-A=A+B-2Aも偶数である。

  • Cには何もしない。
  • Bの方がCに近いので、A,B各+1を(C-B)回する。いま(C+A-B,C,C)になってる。
  • Aに対し(B-A)/2回だけ+2する。これで(C,C,C)に揃う。

A+B+CのパリティがCと異なる場合:A+Bが奇数なので、B-A=A+B-2Aも奇数である。

  • B,C各+1を1回する。いま(A,B+1,C+1)である。
  • A,B各+1を(C-B)回する。いま(C+A-B,C+1,C+1)である。
  • Aに対し(B-A+1)/2回だけ+2する。これで(C+1,C+1,C+1)に揃う。

E - Tozan and Gezan (700)

こういう「二者が最善手を取っていく」系の問題はめちゃ苦手なのでそっ閉じしたくなる*1。ってことはそういう問題を多めにこなしていけば強くなれるかも?

AはBから逃げて、BはAを追う感じか。
Ai

想定解「Ai>Biなiがあるならとざん君はAiを最後まで減らさないことでそれ以外をすべて0にできる」 それはそう どうして気付かなかったのか

で分かりかけた。Aの作戦としては、Ai>Biのやつをどれか1つ残しておけばBは他をどんどん消費していくものの絶対に終わらないから、他はどれをどういう順に取っても一緒なので適当に取っていく。(残すAi,Biを(A*,B*)としよう)
で、どれを1つ残すのがベスト?
終了の1つ手前では (A*,B*)=(B*+1, B*)、あと1箇所 (Ai,Bi)=(0,1) になっているはず。スコアは(ΣBi) - B* になるので、B*が小さければ小さいほどAの目的に適う。
Aがこういう作戦をとったとして、Bは抗えるのか?Aの1ヵ所残った砦(A*)を消費し始めるのを(他の取れる所を取りながら)待つしかない。B*を消費してしまってはゴールが遠のくのでB*の消費を最後にすることぐらいしかBに残された手はない。

というわけで、答えはΣBi (=ΣAi) から、Ai>Biな中で一番小さいBiを引いた値。
→AC
https://beta.atcoder.jp/contests/arc094/submissions/2579109

F - Normalization (700)

(まだ見てない)

*1:最善手って何だよ。相手もこちらの想定どおりの手を打ってくれないと最善手にならないんじゃないの?とか考え始めちゃうんだよね…