AtCoder ABC 062 B&C
A問題
- 同一のグループなのか否かの判定
- 判定用グループを作って判定
private void solveA() {
int numX = nextInt();
int numY = nextInt();
Map<Integer, Integer> wk = new HashMap<Integer, Integer>();
wk.put(1, 1);
wk.put(3, 1);
wk.put(5, 1);
wk.put(7, 1);
wk.put(8, 1);
wk.put(10, 1);
wk.put(12, 1);
wk.put(4, 2);
wk.put(6, 2);
wk.put(9, 2);
wk.put(11, 2);
wk.put(2, 3);
out.println(wk.get(numX) == wk.get(numY) ? "Yes" : "No");
}
B問題
for文での実装はコメントアウト
- 周囲1ピクセルなので
- 最初は文字列長+2回、
*で埋める - 次は、1文字目
*、文字列、最終文字* - 最後は文字列長+2回、
*で埋める
- 最初は文字列長+2回、
private void solveB() {
int numH = nextInt();
int numW = nextInt();
IntStream.range(0, numH + 2).forEach(i -> {
StringBuilder builder = new StringBuilder();
char[] wk = new char[numW];
if (i != 0 && i != numH + 1) {
wk = next().toCharArray();
}
for (int j = 0; j < numW + 2; j++) {
if (i == 0 || i == numH + 1) {
builder.append("#");
continue;
}
if (j == 0 || j == numW + 1) {
builder.append("#");
} else {
builder.append(wk[j - 1]);
}
}
out.println(builder.toString());
});
// char[][] wk = new char[numH][numW];
//
// for (int i = 0; i < numH; i++) {
// wk[i] = next().toCharArray();
// }
//
// for (int i = 0; i < numH + 2; i++) {
// StringBuilder builder = new StringBuilder();
//
// for (int j = 0; j < numW + 2; j++) {
// if (i == 0 || i == numH + 1) {
// builder.append("#");
// continue;
// }
// if (j == 0 || j == numW + 1) {
// builder.append("#");
// } else {
// builder.append(wk[i - 1][j - 1]);
// }
// }
//
// out.println(builder.toString());
// }
}
C問題
-
チョコの分割方法は4通り(図はサイトの解答を参照)
- 縦に3分割
- 最低値は0または、縦の高さ
- $mod3=0$なら$0$になるし、$mod3!=0$なら、あまりは1または2のどちらかなので$max-min$は縦の高さになる
- 最低値は0または、縦の高さ
- 横に3分割
- 最低値は0または、横の幅
- $mod3=0$なら$0$になるし、$mod3!=0$なら、あまりは1または2のどちらかなので$max-min$は横の幅になる
- 最低値は0または、横の幅
- 縦1:横2
- 縦2:横1
- 縦横入れ替えれば同じ式を利用できる
- 縦に3分割
-
注意事項（はまったところ）
- 下の三つ、「１」と「２」「３」は結果が違う。。。-1がintなので式の評価結果がintにcastされ、桁溢れる。。。ｺﾚに気づかず数時間。。。
- 大きい計算するときの注意事項をすっかり忘れていてショックだ。
- １：System.out.println((long) (100000 * (100000 - 1)));
- ２：System.out.println((long) (100000 * (100000 - (long) 1)));
- ３：System.out.println((long) 100000 * (99999));
private void solveC() {
/*
* resultが違う
*/
// System.out.println((long) (100000 * (100000 - 1)));
// System.out.println((long) 100000 * (99999));
// System.out.println((long) 99999 * 100000);
int numH = nextInt();
int numW = nextInt();
out.println(chkSolvceC(numH, numW));
}
/**
*
* HWWWWWWW
* HWWWWWWW
* HWWWWWWW
* HWWWWWWW
*
*/
private long chkSolvceC(long numH, long numW) {
long res = Long.MAX_VALUE;
long pHW = Long.MAX_VALUE;
if (numH % 3 == 0 || numW % 3 == 0) {
//このパターンにおいては均等に3分割可能なため、差分が0になる
return 0;
}
/*
* 最小値の初期化
*
* 以下の形のチョコの場合、A=1列目、B=2列目、C=3と4列目が最も簡単にわかる分割方法
* つまり、最低この形をクリアするのは必須
* 1234
* PPPP
* PPPP
* PPPP
* PPPP
*
*/
/*
* 縦
* 最小パターンのためにnum%3の余りを分配
* 単純に(numH -numH/3)をHとして扱ってしまうと、mod3=2の時に問題が出る
*
* これは困る
* H/3 * W
* H/3 * W
* H/3+2 * W
*
* こうしたい
* H/3 * W
* H/3+1 * W
* H/3+1 * W
*/
long m1 = 0;
long m2 = 0;
long m3 = 0;
switch ((int) numH % 3) {
case 0:
break;
case 1:
m3 = 1;
break;
case 2:
m2 = 1;
m3 = 1;
break;
}
long pA1 = (numH / 3 + m1) * numW;
long pA2 = (numH / 3 + m2) * numW;
long pA3 = (numH / 3 + m3) * numW;
pHW = pA3 - pA1;
res = Math.min(res, pHW);
//横 最小パターンのためにnum%3の余りを分配
switch ((int) numW % 3) {
case 0:
break;
case 1:
m3 = 1;
break;
case 2:
m2 = 1;
m3 = 1;
break;
}
long pB1 = (long) (numW / 3 + m1) * numH;
long pB2 = (long) (numW / 3 + m2) * numH;
long pB3 = (long) (numW / 3 + m3) * numH;
pHW = pB3 - pB1;
res = Math.min(res, pHW);
for (int i = 0; i < 2; i++) {
long wkH = 0;
long wkW = 0;
if (i == 0) {
wkH = numH;
wkW = numW;
} else {
wkH = numW;
wkW = numH;
}
long wkH1 = (wkH / 2);
long wkH2 = (wkH - wkH / 2);
for (int j = 1; j < wkW; j++) {
long wkW1 = (wkW - j);
long p1 = (long) wkH * j;
long p2 = (long) wkH1 * wkW1;
long p3 = (long) wkH2 * wkW1;
long max = Math.max(Math.max(p1, p2), p3);
long min = Math.min(Math.min(p1, p2), p3);
res = Math.min(res, max - min);
}
}
//三分割(再帰で書いたらstackoveflowした)
// pHW = saikiC(1, numH, numW);
// res = Math.min(res, pHW);
//
// pHW = saikiC(1, numW, numH);
// res = Math.min(res, pHW);
return res;
}