🔖

AtCoder Beginner Contest ABC432 解法メモ

に公開
Nim
AtCoder
tech

文中で使用しているのは、PythonライクでAtCoderに最適な言語の1つNimです

ABC432

ABC432A - Permute to Maximize

解法

A、B、Cは1～9なので、降順に並べて出力すればよい
ACコード

ABC432B - Permute to Minimize

解法

Xを文字で受け取ってから、各桁の数字の配列に変形し、ソートする
先頭に0が来ない最小の数字にするには、
先頭からみていって、最初の0でない数字と、先頭の数字を交換すればよい
出来上がった数列を詰めて出力したものが答え
ACコード

メモ

交換、は思いつかず、0でない最小値mを探しておき、答えとなる配列の頭に入れ、Xをソートした配列を頭からみていき、初めてmが出たときだけ無視して、他は、順に答えの配列に加えた

ABC432C - Candy Tribulation

解法

各子供に配られる飴の重量が取り得る範囲はA[i]\times XからA[i]\times Yの間である
そのすべてに共通する範囲の中で、Yの個数を最大化するということは、最も少ない個数をもらう子供がすべてYでもらう場合に他ならない
目標重量が定まった上で、各子供のYの個数を考えていくと、
目標重量A.min*Yに対して、すべてXでもらった重量A[i]*Xとの差を、飴の重量差Y-Xで割ったものになる（XをYに入れ替えればY-Xだけ重量が増えるため）
よって、それをすべての子供にわたって足し合わせれば、答えとなる
ただし、そもそも、A.min*YよりA[i]*Xが大きかったり（範囲が重ならなかったり）、
A.min*Y-A[i]*XがY-Xで割り切れなかったら（どうXとYを調整しても、目標重量を
作れなかったら）、配り方が存在しないので、-1を出力すればよい
ACコード

ABC432D - Suddenly, A Tempest

解法

各矩形(lx,rx,ly,ry)に対し、各大嵐をシミュレートし、
出来上がった矩形群（多くても2^{14}=16384個）を連結判定しながらUnion-Findし、最後に連結成分ごとのマス目の数を解答することを考える
大嵐のシミュレート部分は、
CiがXかYかにわけて、
わかれ目Aiが、
矩形の右にあるとき、
矩形の真ん中を分断するとき、
矩形の左にあるときにわけて
移動先の矩形を作っていく
出来上がった矩形の数を頂点数とするUnion-Findを用意し、
全i、jの組み合わせで、連結判定する
連結判定は、xとyにわけて、
片方の軸のiのl端とjのr端、もしくは、iのr端とjのl端が同じで、
かつ、
もう片方の軸でiのl端<jのr端、かつ、iのr端>jのl端になればよい
groupsのlenと、groupsごとの(rx-lx)*(ry-ly)を合計したものをソートしたものが答え
ACコード

メモ

愚直にシミュレートする勇気が出なかった

ABC432E - Clamp

解法

クエリ2は、題名通り、l、rから外れた値をl、rに寄せ直した値の合計である
これは、l、r間については、そこに収まっているAiの合計でよく、
それ以外については、l未満、rより大きいAiの個数をそれぞれ求めることで、各々それにl、rをかければ計算できる
これは、Aのインデックスではなく、要素の値A[i]を基準としたフェニック木（BIT）を用意すれば実現できる
Aiの値の制約である5*10^5を上限に、個数カウント用cと、合計カウント用sの2種類のフェニック木を用意し、
初めに、すべてのiに対して、
c.add(A[i],1)と、s.add(A[i],A[i])をしておく
クエリ1に対しては、
cとsのA[x-1]の位置から各々値を減らして、yの位置を増やせばよい
（もちろん、A[x-1]=yに書き変える）
クエリ2に対しては、
c[0..<l]*l+s[l..<r]+c[r..5*10^5]*r
を出力すればよい
ただし、l>rのこともあり、その場合はすべての項がlになるので、N*lを答えることになる
ACコード

メモ

値を軸に2種類の木で管理すべきことまではわかったが、なぜかセグメント木を持ち出してしまい、実装に時間をかけた
l>rのときは、単にN*lとなることがすぐに見抜けなかった

反復学習にはmochiがおすすめ
全問入ったdeckはこちら

Discussion