Hewlaの競プロ記

競プロ記です。

GCJ ROUND 1A 2018

お疲れ様でした。2問目、3問目ほとんどわからなかったので撤退しました。

BとかCとかで上位勢が抜けたところを狙っていきたいと思います。

 

Waffle Choppers

縦にR行、横にC列並んだ正方形のセルからなる巨大な長方形のワッフルがあります。このセルにはチョコチップが1つ入ってたり、また入ってなかったりします。

このワッフルを横向きにH回、縦向きにV回切ることで(H+1)×(V+1)個の長方形に分けます。このとき各ピースの大きさは異なっていても構いませんが(いいのかよ)、どのピースにも同じ数のチョコチップが入っていないといけません。

R, C, H, Vと、チョコチップのある位置に関する情報が与えられるので、この条件を満たすように切り分けることは可能かどうか出力しなさい、という問題です。問題文を適当に抜粋したため条件に抜けがあるかもしれませんので、 詳細は問題文を参照してください。

考察 - Hidden-

これ、最初から何ピースに分けるのかがすぐにわかります。(H+1)×(V+1)です。 チョコチップの個数の和をS、ピース数をP = (H+1)×(V+1)とすると1ピースにはS/Pこのチョコチップが入ります。SがPで割り切れなければIMPOSSIBLEです。

ここから少し考察しました。横にH回切るとH+1個の帯ができます。この帯それぞれをV回縦に切るとき、そのすべてに同じ数のチョコチップがないといけないわけですから、すべての帯に含まれるチョコチップの数も同じ数にならないといけません。帯をH+1個作ることと、チョコチップがS個あることから、各帯にはS/(H+1)個ずつチョコチップが入るように切り分ける必要があります。これをもとにうまいこと(全ての帯にS/(H+1)個のチョコチップが

入るような切り方を探す)処理すると、「どこで横に切るといいか」ということがわかります。ここの実装で迷ってしまったなんて言えない(精進不足)

同じことが縦に切り分けるときのことについても言えるので、どこで切り分けるといいかが縦横全てについてわかることになります。この分け方以外に条件を満たす切り分け方がある可能性がないってことになります。あとは、その情報に基づいて「各ピースにしっかりS/P個のチョコチップが入っているか」を確かめます。

 

感想

なかなか実装がしんどかったです。てか僕の実装がクソ実装だったんでしょうね。それだけにACしたときはびっくりしました。絶対落ちると思ってた

次回、Round1Bもがんばります

 

2018/07/07 追記

そういえばこの後1Bと1Cも落ちました