Google Code Jam(GCJ) Round1A 参加記

GCJ Round1Aに参加しました

AB + c(部分点)で865位なので無事通過できそうです

 

f:id:myau_atcoder:20220411092515p:plain

 

A Double or One Thing

ある文字について増やした方がいいか?を考えます

abならaabとしたほうが、2番目に来る文字がbからaになるので得です

baならbbaとしたほうが、2番目に来る文字がaからbになるので損です

このように辞書順で次の文字より小さいなら増やした方がよいです

ただし、同じ文字が連続しているときはそれをまとめて増やした方がよい(aabをaaaabにする)ので、ランレングス圧縮をして文字を持つと楽です。(AC 05:43)

 

B Equal Sum

初見であまり思いつかなかった&構築が苦手なので、飛ばしてCの部分点にいきました

Cの部分点をとってから考えます

サンプルを見ますが、どうみてもN=2のときに満たせるわけがない気がします

よくわからないので、clarを送ります

ぼく「必ずできることが保証されていますか?」

Google「ほかの人のヒントになるから教えてあげないよ」

困りました、でもこの言いかただとおそらくできるんでしょう

じゃないと、できないときに-1を出力せよ、みたいなのがない理由がありません

 

もう一度よくみると、N=100と書いてあります(!!!)

となると、ある程度調整しやすそうなのを投げて最後につじつまを合わせるのが良さそうです。

調整用に1,2,...10,20,...100,200,......10^9を投げることにします(よくよく考えると2べきで十分でした)

こうすると残りで必要なものが10^9以下になると自明に調整ができます

しかし、どうすれば10^9以下にできるのか思いつきません

 

Bとして渡されるものが大きいものばっかりなら、それを最初に適当に使えば10^9以下になりそうなのでいいんですが、そうでないときに困ってしまいます(と思っていました)

いろいろ考えてやっと、Bとして小さいものが渡された時も、Aから大きいものを適当に使えば10^9以下になることに気づきました

 

ということで、AとBをごちゃまぜにして大きい順にソートします

必要なものが今見ているものより小さいなら、最初に投げた1,2,...10,20,...100,200,......10^9で調整できるので、これで無事解けました(AC 2:22:46)

 

2べきで調整は典型なのでちょっと弱いところが出ましたね

 

C Weightlifting

Bを見て後にしようとなったので、部分点をとりにきました

制約がかなり小さいので、それを使いましょう

ありうる順列がすべて列挙できれば、そこから次の適切な状態に移るまでの最小手数を計算する問題に帰着できます

状態は一見多そうですが、1,2,3しか使わない関係でかなり絞られます

よくわからないので、順列を全部生成してmapにつっこむとmapのサイズが6000いかないくらいになるので、なんとかなりそうです

 

状態が列挙できる&十分少ないとわかったので、これを使って最短路問題を解きます

ただ厄介なところとして、i回目に最短だったからといって、そこからi+1回目にも最短となる経路が存在するかはわかりません

なので、i回目として条件を満たすものについてすべて最短路を計算しておきます

i+1回目について計算するときは、「i回目として条件を満たすもの」すべてを始点とした多点Dijkstraをしてあげればよいです

ちょっと計算量が多い気もしますが、C++と長いTLを信じれば通ります

一応の工夫としてグラフの構築は全テストケースの前に終わらせているので、1回だけになっています(AC 41:18)

 

満点解法は考える時間がありませんでした

 

総評

Bで詰まってかなり焦ったんですが、何とか通せてよかったです

Cの部分点めんどいだけなんだけど、思ったより通されてなくて助かった

Round2も勝って今年こそTシャツとるぞ!