AT_xmascon18_a Art Time
Description
[problemUrl]: https://atcoder.jp/contests/xmascon18/tasks/xmascon18_a
以下の画像を $ 4 $ 色で塗り分けよ．ただし，隣り合う領域は同じ色で塗ってはならない．
なお，枠の外の余白は塗らなくてよい．
Input Format
この問題では入力は与えられない．
Output Format
塗り分けた後の画像を**解答キー生成スクリプト**に読み込むと，解答のための**解答キー**が出力される．この解答キーを標準出力に出力するプログラムを提出すると正解となる．
Explanation/Hint
### 解答キー生成スクリプト
Copy### 備考
- 画像サイズは $ 584\ \mathrm{px}\ \times\ 400\ \mathrm{px} $ から変更しないこと．
- 領域ごとに色の RGB 値が多少ずれていても，*AI* が自動で同じ色だと識別してくれるようになっている．
- スクリプトでは解答キーの生成と同時に正誤判定も行い，結果が表示される．
- 提出言語として「Text (cat)」を選択すると解答キーをそのまま提出するだけで良いため，楽である．
var W = 584, H = 400;
var V = [[16,18],[559,26],[290,390],[41,82],[91,68],[135,44],[159,33],[212,54],[267,72],[374,75],[438,78],[463,77],[485,66],[544,95],[544,183],[545,308],[464,314],[407,347],[353,348],[317,341],[209,340],[158,348],[122,313],[58,327],[29,202],[106,143],[165,104],[239,119],[384,125],[473,130],[507,179],[510,250],[433,274],[375,271],[269,278],[187,275],[95,250],[158,154],[245,147],[355,161],[429,164],[457,204],[121,212],[185,195],[208,197],[283,239],[311,210],[363,212],[417,95],[141,213],[385,199],[228,311],[231,360],[482,317],[482,367],[37,145]];
var E = [[0,1,291,15,303,18],[0,2,6,193,6,205],[0,3,18,24,30,27],[0,4,58,16,64,27],[0,5,118,16,124,27],[0,6,150,16,156,27],[0,7,203,16,206,28],[0,8,256,36,262,47],[0,24,14,167,26,170],[0,55,19,133,31,136],[1,2,559,201,559,213],[1,8,296,47,303,37],[1,9,354,43,361,53],[1,10,385,44,394,52],[1,11,443,43,450,53],[1,12,475,43,483,52],[1,13,523,43,529,54],[1,14,547,160,559,157],[2,14,547,210,559,213],[2,15,509,378,515,368],[2,16,452,379,460,370],[2,17,363,385,370,375],[2,18,343,385,350,375],[2,19,255,379,262,369],[2,20,200,380,206,369],[2,21,131,385,138,375],[2,22,70,385,77,375],[2,23,19,254,31,257],[2,24,14,205,26,202],[3,4,52,27,64,27],[3,5,54,124,66,127],[3,55,31,124,31,136],[4,5,64,107,68,118],[5,6,141,59,153,62],[5,25,93,138,99,149],[5,26,137,110,149,113],[5,55,57,141,66,133],[6,7,177,71,189,74],[6,26,152,81,153,69],[7,8,250,44,262,47],[7,26,180,82,189,74],[7,27,214,82,217,94],[8,9,349,51,361,53],[8,27,250,105,262,102],[8,28,343,107,349,118],[9,10,379,87,391,90],[9,28,363,90,363,102],[10,11,438,51,450,53],[10,28,380,99,391,93],[10,29,405,108,412,118],[10,48,399,88,411,91],[11,12,468,55,480,58],[11,29,452,95,452,107],[12,13,488,56,500,59],[12,29,470,107,481,101],[13,14,537,148,539,160],[13,29,515,115,525,108],[13,30,522,141,533,135],[14,15,539,250,545,239],[14,30,516,178,528,181],[14,31,527,217,539,214],[15,16,496,329,507,335],[15,31,502,287,512,294],[16,17,444,314,456,311],[16,31,479,294,486,284],[16,32,445,300,457,303],[16,53,464,306,476,309],[16,54,464,347,476,350],[17,18,358,311,370,314],[17,32,400,314,407,304],[17,33,370,302,370,314],[18,19,334,315,340,304],[18,33,328,299,340,302],[19,20,250,366,262,369],[19,33,299,315,305,304],[19,34,263,303,264,315],[20,21,192,315,204,312],[20,34,228,294,235,284],[20,35,192,301,204,304],[20,51,212,304,224,307],[20,52,212,359,224,362],[21,22,87,361,99,364],[21,35,137,303,138,315],[22,23,65,365,77,368],[22,35,114,294,125,288],[22,36,79,284,85,295],[23,24,30,238,32,250],[23,36,56,252,68,251],[24,25,70,162,82,160],[24,36,34,170,46,173],[24,55,30,164,31,152],[25,26,136,124,148,126],[25,36,77,181,86,173],[25,37,133,164,145,167],[25,42,104,184,115,190],[25,55,73,152,82,160],[26,27,205,91,217,94],[26,37,147,140,148,128],[26,38,176,130,183,140],[27,28,335,126,347,129],[27,38,210,140,217,130],[27,39,309,129,316,139],[28,29,400,117,412,118],[28,39,339,139,347,130],[28,40,379,133,385,144],[29,30,496,147,502,158],[29,40,405,147,413,138],[30,31,494,210,500,221],[30,40,474,169,486,172],[30,41,458,189,470,192],[31,32,469,252,481,251],[31,41,473,242,481,251],[32,33,390,252,402,251],[32,40,414,221,421,231],[32,41,438,231,450,231],[32,47,394,242,402,251],[33,34,293,298,305,301],[33,39,339,246,345,257],[33,45,302,270,309,280],[33,47,359,248,365,237],[34,35,223,281,235,284],[34,44,242,253,244,241],[34,45,255,252,264,244],[35,36,113,282,125,285],[35,42,127,241,133,252],[35,43,165,246,172,237],[35,44,195,251,203,242],[36,42,102,196,114,193],[37,38,169,143,181,146],[37,42,138,181,145,171],[37,43,159,173,170,179],[38,39,302,143,314,146],[38,43,177,159,181,148],[38,46,290,157,302,160],[39,40,373,143,385,144],[39,45,324,252,333,244],[39,46,307,160,314,150],[39,47,349,188,361,191],[40,41,438,187,450,190],[40,47,369,218,381,221],[42,43,158,182,170,179],[42,49,123,190,135,193],[43,44,191,178,203,181],[43,45,264,204,264,216],[43,46,280,178,292,181],[44,45,252,213,264,216],[45,46,290,216,302,213],[47,50,369,190,381,193]];
var N = V.length, M = E.length;
function copy(textVal){
var copyFrom = document.createElement("textarea");
copyFrom.textContent = textVal;
var bodyElm = document.getElementsByTagName("body")[0];
bodyElm.appendChild(copyFrom);
copyFrom.select();
var retVal = document.execCommand('copy');
bodyElm.removeChild(copyFrom);
return retVal;
}
$ (function()\ { $("#in-png").change(function() {
if (!this.files.length) {
console.log('not selected');
return;
}
var file = this.files[0];
var canvas = $ ("#cnvs");
\ var\ ctx\ =\ canvas[0].getContext('2d');
\ var\ image\ =\ new\ Image();
\ var\ fr\ =\ new\ FileReader();
\ fr.onload\ =\ function(evt)\ {
\ image.onload\ =\ function()\ {
\ var\ w\ =\ image.naturalWidth;
\ var\ h\ =\ image.naturalHeight;
\ if\ (w\ !=\ W)\ console.log('wrong\ width');
\ if\ (h\ !=\ H)\ console.log('wrong\ height');
\ ctx.drawImage(image,\ 0,\ 0,\ w,\ h); $('#cnvs').show();
// recognize
var data = ctx.getImageData(0, 0, W, H).data;
var rgb = [];
for (var i = 0; i < N; i++) {
var x = V[i][0], y = V[i][1];
var si = (y*W+x)*4;
rgb.push([data[si],data[si+1],data[si+2]]);
}
console.log('RGB', rgb);
var masters = [0];
while (masters.length < 4) {
var best = -1, bi = 0;
for (var i = 0; i < N; i++) {
var dist = 1e9;
for (var k = 0; k < masters.length; k++) {
var d = 0;
for (var j = 0; j < 3; j++) d += Math.abs(rgb[masters[k]][j]-rgb[i][j]);
dist = Math.min(dist, d);
}
if (best < dist) {
best = dist;
bi = i;
}
}
masters.push(bi);
}
var col = [];
for (var i = 0; i < N; i++) {
var best = 1e9;
col.push(0);
for (var k = 0; k < 4; k++) {
var d = 0;
for (var j = 0; j < 3; j++) d += Math.abs(rgb[masters[k]][j]-rgb[i][j]);
if (d < best) {
best = d;
col[i] = k;
}
}
}
console.log('Color ID', col);
// judge
var SC = [0,0,0], SCval = 0;
for (var r = 0; r < 256; r += 5) {
for (var g = 0; g < 256; g += 5) {
for (var b = 0; b < 256; b += 5) {
var dist = r+g+b;
dist = Math.min(dist, 255*3);
for (var i = 0; i < 4; i++) {
var d = 0;
for (var j = 0; j < 3; j++) d += Math.abs(rgb[masters[i]][j]-[r,g,b][j]);
dist = Math.min(dist, d);
}
if (dist > SCval) {
SCval = dist;
SC = [r,g,b];
}
}
}
}
console.log('rgb('+SC[0]+','+SC[1]+','+SC[2]+')');
ctx.strokeStyle = 'rgb('+SC[0]+','+SC[1]+','+SC[2]+')';
var same = 0;
for (var i = 0; i < M; i++) {
if (col[E[i][0]] == col[E[i][1]]) {
same++;
console.log('NG Edge', E[i].slice(0,2));
ctx.beginPath();
ctx.moveTo(E[i][2], E[i][3]);
ctx.lineTo(E[i][4], E[i][5]);
ctx.stroke();
}
}
if (same) $ ('#result').text('Wrong...');
\ else $('#result').text('Correct!');
var ans = '';
for (var i = 0; i < N; i++) ans += col[i];
$ ('#answer-key').val(ans);
\ }
\ image.src\ =\ evt.target.result;
\ };
\ fr.readAsDataURL(file);
\ }); $('#cpy-ans').click(function() {
copy($('#answer-key').val());
});
});