水色プログラミング

競プロで解いた問題の記録,ゲーム制作の進捗など...

AtCoder Beginner Contest 099

  • 結果

A,B,D の3完(49:10)。D 問題を始めに通した後、C 問題を考えたが入出力例3が一向に合わず。諦めて A,B 問題を通し終わった。今回の C 問題は D 問題より圧倒的に難しいと思った。

f:id:babcs2035:20180611184402p:plain

 

  • D 問題

  • 問題

D - Good Grid

N*N のマス目のうち、それぞれのマスの (行数 + 列数) mod 3 のものを一色に統一したい。元々の色を変更する場合「違和感」が発生し、その違和感を最小化する、という問題。

 

  • 解法

決める色は3つしかないので、全通り試す。3つにマスをグループ分けし、全通りの色を試す。愚直にやると O(C^3 * N^2) なので、前計算として各グループに対しすべての色を試した結果を持っておく。そうすれば O(C * N^2 + C^3) になり間に合う。貪欲解がぱっと思いついたのでこの方針で解いた。

 

  • 解答

Submission #2647127 - AtCoder Beginner Contest 099

f:id:babcs2035:20180611185047p:plain

 

  • B 問題

  • 問題

B - Stone Monument

 

  • 解法

やるだけ

 

  • 解答

Submission #2649194 - AtCoder Beginner Contest 099

f:id:babcs2035:20180611185748p:plain

 

  • A 問題

  • 問題

A - ABD

 

  • 解法

やるだけ。数字は出力する必要ないことに注意。

 

  • 解答

Submission #2649455 - AtCoder Beginner Contest 099

f:id:babcs2035:20180611185824p:plain