読者です 読者をやめる 読者になる 読者になる

sataniC++

C++、競プロ、数学などについて色々考えたりします。

Google Code Jam 2017 Qualification Round

コンテストページのURLはこちらです。
Dashboard - Qualification Round 2017 - Google Code Jam

A. Oversized Pancake Flipper

問題概要

'+'と'-'のみからなる文字列と整数Kが与えられます。

この文字列に対して長さKのある範囲を指定することで、その中に含まれる'+'を'-'に、'-'を'+'に反転させることが出来ます。

この操作を繰り返して、全ての文字を'+'にすることが出来るか判定してください。
出来る場合は操作の最小回数を、出来ない場合は"IMPOSSIBLE"を出力してください。

考えたこと

文字列の1文字目が'-'になっているとき、その文字を'+'にするためには1文字目からK文字目までを反転する外ありません。

また、1文字目が'+'になっているとき、1文字目からK文字目を反転してしまうと、1文字目が'-'になってしまうため、また同じ範囲を反転しないといけないため、もう1文字目から反転する必要はありません。


このことから、1文字目が'-'なら[1K]を反転、次に2文字目が'-'なら[2K+1]を反転、…と順に見ていけばよいことが分かります。

これをi=|S|-K(|S|は文字列長)まで繰り返し、最後に全てが'+'になっているかを判定してやればよいです。



これをサンプル1で考えてみます。
文字列は---+-++-、K=3です。

  • 1文字目を見ると'-'です。よって1~3文字目を反転させます。

++++-++-

  • 2,3,4文字目は'+'なので何もしません。
  • 5文字目を見ると'-'です。よって5~7文字目を反転させます。

+++++---

  • 6文字目を見ると'-'です。よって6~8文字目を反転させます。

++++++++

  • 最後に文字列全体を見てみると、全ての文字が'+'になっていることが分かります。

よって、この場合は答えが"3"となります。

コード(C++)

ひとこと

この「反転」の考え方は非常に典型的ですね(蟻本にもほぼ同じ問題が載っています)。


B. Tidy Numbers

問題概要

ある整数に対して、桁が上から順に非減少になっているものをきちんとした数と言います。

ある整数Nが与えられたとき、N以下で最大のきちんとした数を答えてください。

考えたこと

N以下で最大」ということからなるべく下の桁を変えるだけに留めたいところですが、上の桁で減少している部分があった場合、いくら下の桁を弄ってもその部分を解決しないことには非減少にはできません。


よって、上の桁から順に減少しているところがないかを調べていきます。
これは具体例で見ていきましょう。

N=12314のとき、上の桁から順に見ていくと、3,4番目が"31"となっており、減少しています。
この部分を非減少とするためには、"29"とするのが最適です。
31以下で非減少とするためには、"3"の桁を"2"としなければなりません。

残りの桁は、なるべく大きい数とするため、全て"9"で埋めてしまいます。

この例では、答えはN=12299となります。


ここで一つ注意点があります。
減少している部分を見つけた場合、その中で左の桁を1減らす必要がありますが、それによって1つ左の部分が非減少から減少になってしまうことがあります。


N=11023を見てみましょう。
上の桁から順に見てみると、2,3番目の"10"が減少となっているため、この部分を"09"と置き換え、残りの桁は全て"9"とします。

するとN=10999となりますが、こうすると1,2番目の"10"も減少となってしまいました。
よって、操作した後は1つ左の部分も見てやる必要があります。

コード(C++)

ひとこと

数として考えると、largeではN10^{18}まで大きくなってしまうため、文字列として考えました。


C. Bathroom Stalls

問題概要

部屋がN+2部屋あり、両端の部屋は既に人が入っていますが、残りのN部屋は空いています。
この中にK人が入ろうとしていますが、それぞれの人は次のように入る部屋を決めます。

  • 全ての空き部屋に対して、左にある人がいる部屋までの距離L、右にある人がいる部屋までの距離Rを調べ、LRの小さい方の値が一番大きい部屋を選びます。
  • そのような部屋が複数ある場合は、該当する部屋の中で一番左の部屋を選びます。

K-1人が順に部屋に入ったあと、最後にK番目の人が部屋に入る時、上記のLRについて、大きい方、小さい方をそれぞれ出力してください。

考えたこと

まず初めに、Nの偶奇それぞれについて最初に人が入る場合を考えます。
f:id:satanic0258:20170409111844p:plain
上記画像のように、人が入ると2つの区間に分割されることが分かります。
これは2人目以降も同じことが言えます。

これを使って、シミュレーションしてみましょう。
大きい方から選んでいく、ということから優先度つきキューを使います。

これでN=K=50のケースを見てみます。

50,
25,24,
24,12,12,
12,12,12,11,
12,12,11,6,5,
12,11,6,6,5,5,
11,6,6,6,5,5,5,
6,6,6,5,5,5,5,5,
6,6,5,5,5,5,5,3,2,
6,5,5,5,5,5,3,3,2,2,
5,5,5,5,5,3,3,3,2,2,2,
5,5,5,5,3,3,3,2,2,2,2,2,
5,5,5,3,3,3,2,2,2,2,2,2,2,
5,5,3,3,3,2,2,2,2,2,2,2,2,2,
5,3,3,3,2,2,2,2,2,2,2,2,2,2,2,
3,3,3,2,2,2,2,2,2,2,2,2,2,2,2,2,
3,3,2,2,2,2,2,2,2,2,2,2,2,2,2,1,1,
3,2,2,2,2,2,2,2,2,2,2,2,2,2,1,1,1,1,
2,2,2,2,2,2,2,2,2,2,2,2,2,1,1,1,1,1,1,
2,2,2,2,2,2,2,2,2,2,2,2,1,1,1,1,1,1,1,
2,2,2,2,2,2,2,2,2,2,2,1,1,1,1,1,1,1,1,
2,2,2,2,2,2,2,2,2,2,1,1,1,1,1,1,1,1,1,
2,2,2,2,2,2,2,2,2,1,1,1,1,1,1,1,1,1,1,
2,2,2,2,2,2,2,2,1,1,1,1,1,1,1,1,1,1,1,
2,2,2,2,2,2,2,1,1,1,1,1,1,1,1,1,1,1,1,
2,2,2,2,2,2,1,1,1,1,1,1,1,1,1,1,1,1,1,
2,2,2,2,2,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
2,2,2,2,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
2,2,2,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
2,2,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
2,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,
1,1,1,1,1,1,
1,1,1,1,1,
1,1,1,1,
1,1,1,
1,1,
1,

これを見てみると、3を1 1にしたり、2を1にしたりと、同じ操作を何度もやっていることが分かります。
この部分が冗長になっているため、同じ数字は全てひとまとめにしてやってしまいましょう。


区間の長さがsであるものがx個あるとき、人がx人以上居たらまとめてx人分sを分けてやればよいです。

これは\mathtt{map}で管理してやると良いでしょう。

次のコードに同様の具体例を載せています。

コード(C++)

同様にN=K=50の例を見てみましょう。

(50,  1),
(24,  1), (25,  1),
(12,  2), (24,  1),
(11,  1), (12,  3),
( 5,  3), ( 6,  3), (11,  1),
( 5,  5), ( 6,  3),
( 2,  3), ( 3,  3), (5,  5),
( 2, 13), ( 3,  3),
( 1,  6), ( 2, 13),
( 1, 19),

それぞれ、(区間の長さ, その個数)となっています。

区間は半分ずつになっていくため、ループ回数は先ほどのO(K)からO(\log K)となり、十分間に合います。

ひとこと

一度実験してそこからよく考えてみるのは大事ですね。


D. Fashion Show

問題概要

'.', '+', 'x', 'o' からなる大きさN \times Nの盤面が与えられます。

これらにはポイントが割り振られており、それぞれ0点, 1点, 1点, 2点となっています。

また、各行・各列に対して、'.'以外の文字が2つ以上あるとき、どの2つの文字を取っても少なくとも片方が'+'である必要があります。
同様に、各斜めの列(盤面を45°回転させたときの各行・各列)に対して、'.'以外の文字が2つ以上あるとき、どの2つの文字を取っても少なくとも片方が'x'である必要があります。

'.'を他の文字へ変えることが出来ます(変えなくてもかまいません)。
また、'+'、'x' は 'o' へと変えることが出来ます。
それ以外の操作はできません('o' を'.'にしたりなどは出来ません)。

このとき、得られる最高の得点はいくらでしょうか?
またその時、どの文字を変えたかも併せて出力してください。

考えたこと

何もない(=全ての文字が'.')盤面に'+', 'x', 'o' を置いたときのことを考えてみます。
f:id:satanic0258:20170409115144p:plain
上記画像のように、'+'を置いたときはそこから斜めに真っすぐ進んだところには何も置かないか'x'を置く必要があります。
('+'か'o'を置くと制約を満たしません)

同様に、'x' を置いたときはそこから上下左右にまっすく進んだところには何も置かないか'+'を置く必要があります。
('x' か'o'を置くと制約を満たしません)


そして、'o' を置いたときには、同じところに'+'と'x'の両方を置いたときのような制約が生まれます。

このことから、'+'を置くか置かないかのみの盤面、'x' を置くか置かないかのみの盤面に分けて考えても良いことが分かります。

ポイントについて、'+'と'x' は1点ずつであるのに対し'o' は2点となっておりますが、'o' は'+'と'x' を同じ場所に置く、と考えると確かに同じように考えることが出来ます。


では、それぞれの盤面について置く場所を調べていきます。

まず簡単な'x'の盤面について、ある場所に'x' を置くと、以降はその行と列を取り除いた盤面について考えていけばよいです。
f:id:satanic0258:20170409120308p:plain
(緑のマスにもう'x' は置けない)

あとは左上から同じ要領で'x'で埋めていくことが出来ます。


次に'+'の盤面についてですが、斜めに盤面を見ていくのは大変なので、斜めの関係が崩れないように45°回転させた盤面を作ります。
f:id:satanic0258:20170409120811p:plain
(黄色のマスにしか'+'は置けません)


あとは先ほどと同じようにマスに配置していきたいのですが、左上から順に埋めていくとダメなケースが存在します。
f:id:satanic0258:20170409121517p:plain
左は左上から埋めていった例ですが、右のように配置すると1つ多く置くことが出来ます。


そこで、「置ける候補が少ない行or列から順に置いていく」という方法を取ります。*1
f:id:satanic0258:20170409122451p:plain

これによって最大まで埋めることが出来ます。
(この方法の正当性が若干不安な部分はありましたが、盤面がこのような形だと問題ないようです。)


最後に、埋めた個数を得点とし、初期状態との差分を取ってやればよいです。

コード(C++)

ひとこと

初めはマス同士の関係だから『最小カットを使って「燃やす埋める問題」を解く』のテクが使えるかなーとしばらく考えていましたが、結局上記解法にたどり着きました。
("2つ取ったときのペアが少なくとも…"というのが隣接マス間であればこの方法で解けたと思います)

最後に

しばらく考えて出した結果、Qualification Roundは全完出来ました!
ただ時間がかなり(6,7時間くらいは考えていそう)かかってしまったため、本選ラウンドではもっと素早く解法へたどり着く必要がありますね。

好調な滑り出しで初めてのGCJを始められたので、Round1も頑張りたいと思います!

*1:この方法はKnuth' s Algorithm Xというらしいです。何かカッコイイ