AtCoder ABC 131 A&B&C&D&E
※2019/06/27
B問題にコメント追記
Fは近いうちに更新予定
※Eは完全グラフについて調べたら追記するかも
A - Security
- 連続して同じ値の場合のみBad
private void solveA() {
char[] wk = next().toCharArray();
for (int i = 1; i < wk.length; i++) {
if (wk[i] == wk[i - 1]) {
out.println("Bad");
return;
}
}
out.println("Good");
}
B - Bite Eating
最近B問題でやたらと時間を溶かす傾向が・・・
- 全部の合計を算出しておく
-
絶対値で最小のものを算出しておく
- ただし、絶対値で比較するが、値としてほしいのは絶対値ではないのに注意
解説PDF読むと分かりますが、この問題は算数の問題なのでループなしでもACできます。
private void solveB() {
int n = nextInt();
int l = nextInt();
int total = 0;
int temp = Integer.MAX_VALUE;
for (int i = 1; i <= n; i++) {
total += l + i - 1;
if (Math.abs(temp) > Math.abs(l + i - 1)) {
temp = (l + i - 1);
}
}
out.println(total - temp);
}
C - Anti-Division
- 全体 $(b-a(-1))$ から、 $(cの倍数+dの倍数-cの倍数かつdの倍数)$ を引けば、 $(cの倍数でもなく、dの倍数でもない数)$ がわかる
- $cの倍数かつdの倍数$ は、CとDの最小公倍数を求めれば算出できる
参考サイト：
包除原理の２通りの証明
private void solveC() {
long a = nextLong();
long b = nextLong();
long c = nextLong();
long d = nextLong();
long res1 = (b / c) - ((a - 1) / c);
long res2 = (b / d) - ((a - 1) / d);
long lcm = getLcm2Args(c, d);
long res4 = (b / lcm) - ((a - 1) / lcm);
out.println((b - (a - 1)) - (res1 + res2 - res4));
}
public long getLcm2Args(long num1, long num2) {
return num1 * num2 / getGcd2Args(num1, num2);
}
public long getGcd2Args(long num1, long num2) {
try {
long wkVal1 = Long.max(num1, num2);
long wkVal2 = Long.min(num1, num2);
long res = wkVal1 % wkVal2;
if (res != 0) {
return getGcd2Args(wkVal2, res);
} else {
return wkVal2;
}
} catch (Exception e) {
System.out.println("num1 : " + num1 + " / num2:" + num2);
e.printStackTrace();
return -1;
}
}
D - Megalomania
パターン1：
$A_1 \leq B_1$
$A_1 + A_2 \leq B_2$
パターン2：
$A_2 \leq B_2$
$A_1 + A_2 \leq B_1$
パターン2が成り立つならパターン1は成り立つはず。。。
証明は公式のYoutubeで
-
締め切りでソート
- ただし、締め切りが同じならかかる時間でソート
-
ソート後、現在時刻が締め切りを超えないかを判定していく
- 締め切りを超えたらNGで、全ての作業が完了出来たらOK
private void solveD() {
int n = nextInt();
int[][] ab = Stream.generate(() -> new int[] { nextInt(), nextInt() }).limit(n).toArray(int[][]::new);
Arrays.sort(ab, (x, y) -> {
int ret = Integer.compare(x[1], y[1]);
return ret != 0 ? ret : Integer.compare(x[0], y[0]);
});
long curTime = 0;
for (int i = 0; i < n; i++) {
curTime += ab[i][0];
if (curTime > ab[i][1]) {
out.println("No");
return;
}
}
out.println("Yes");
}
E - Friendships
参考サイト：
いつもお世話になっている
けんちょんの競プロ精進記録 （AtCoder ABC 131 E - Friendships (500 点)）
- 解説聞いても完全グラフとか理解のとっかかりも持っていないので解説をもとにACしたコードだけ公開。。。
- i=1から開始しているのは、starグラフの中心に1を持ってきているから
- まず、頂点1から伸びる辺を全部列挙しその後、必要な数だけ辺を書く。方針で
private void solveE() {
int n = nextInt();
int k = nextInt();
/*
* Kの下限は0
* 完全グラフ（ある頂点から、他の頂点への距離が全て1）
*
* Kの上限は(n-1)(n-2)/2
* star（ある頂点を起点に、ほかの頂点へ辺が伸びている）
* 全頂点の組み合わせがn(n-1)/2個
* 辺をはるので全頂点の組み合わせから(n-1)引く
*/
long cntEdge = (n - 1) * (n - 2) / 2;
if (k > cntEdge) {
out.println(-1);
return;
}
long maxCnt = cntEdge - k + (n - 1);
long cnt = 0;
StringBuilder builder = new StringBuilder();
for (int i = 1; i <= n; i++) {
for (int j = i; j <= n; j++) {
if (i == j) {
continue;
}
if (cnt < maxCnt) {
builder.append(i + " " + j + System.lineSeparator());
}
cnt++;
}
}
out.println(maxCnt);
out.println(builder.toString());
}