パソコン甲子園について

[ウッティ]

2019年パソコン甲子園問題6が全然わかりません。
教えてくれませんか？

[みけCAT]

過去問｜パソコン甲子園2019
に載っている予選の問題ですか？
そうだとしたら、色が塗られている領域は常に長方形になるので四隅の座標を保持するだけで管理でき、
次に色を塗る領域もそこから簡単にわかるので、
指定の位置が次に色を塗る領域に入っているかを判定し、入っていればその色を出力するようにすればよさそうですね。

[ウッティ]

えーっと最近c言語を始めたばかりで問題5が解けて
問題6で躓いています。
まず四隅の座標はどのように保持するのかとどのように指定の位置が次に色を塗る領域に入っているかを判定するのかがわかりません。
教ええいただけないでしょうか。

[みけCAT]

四隅の座標はxとyに分け、タイル1個分を1とした値で複数のint型の変数で保持するといいでしょう。

指定の位置が次に色を塗る領域に入っているかは、次に色を塗る領域を求めた後、
「次に色を塗る領域の東の端のx座標 ≦ 指定の位置のx座標」かつ
「指定の位置のx座標 ≦ 次に色を塗る領域の西の端のx座標」かつ
「次に色を塗る領域の南の端のy座標 ≦ 指定の位置のy座標」かつ
「指定の位置のy座標 ≦ 次に色を塗る領域の北の端のy座標」
かで判定するといいでしょう。 (条件を全て満たす ⇔ 入っている)

[あたっしゅ]

フィボナッチ数の正方形ですね。

https://ja.wikipedia.org/wiki/%E3%83%95 ... 1%E6%95%B0
フィボナッチ数 フィボナッチすう、英: Fibonacci number

この問題の場合は、2次元配列の方がいいだろ。
C/C++ は、配列に負のインデックスないけど、class 化してアクセスすればいい。

１１１３３３３３３３３３３
１１１３３３３３３３３３３
１１１１２３３３３３３３３
２２２２２３３３３３３３３
２２２２２３３３３３３３３
２２２２２３３３３３３３３
２２２２２３３３３３３３３
２２２２２３３３３３３３３

[みけCAT]

この問題の場合は、2次元配列の方がいいだろ。

この問題で入力される座標の範囲はx, yともに-10**6～10**6なので、
この範囲のタイルを全て2次元配列で用意すると、
1個のタイルを1バイトで表現すれば約4TBになってしまいます。
1個のタイルを2ビットで表現しても、約1TBです。
これは現在一般的なコンピュータの主記憶で扱うには大きすぎるでしょう。
また、この巨大な配列の要素を埋めるのにも、現在一般的なコンピュータでは長時間かかることになるでしょう。
従って、わざわざ指定の場所に到達するまでの全タイルの情報を持つのではなく、
塗った範囲の四隅の座標だけを管理する方がいいでしょう。
(「2次元配列」とあるだけで「全タイルの情報を持つ」とは明示されていませんが、
下の数字列より全タイルの情報を持ちたいのだと解釈しました)

2次元配列を使うとしたら、四隅の座標を2次元配列でもつことで、
もしかしたらなんかいい感じに処理が書けるかもしれないですね。 (ちゃんと考えてはいませんが)