AtCoder ABC 126 A&B&C&D
A - Changing a Character
- 慣れでこんな書き方したけど、改めて見直すと読みづらい？？？
private void solveA() {
int n = nextInt();
int k = nextInt() - 1;
StringBuilder builder = new StringBuilder(next());
out.println(builder.replace(k, k + 1, builder.substring(k, k + 1).toLowerCase()).toString());
}
- うーーん。いまいち。。。
private void solveA() {
int n = nextInt();
int k = nextInt();
String[] wk = next().split("");
wk[k - 1] = wk[k - 1].toLowerCase();
String res = Arrays.stream(wk).collect(Collectors.joining(""));
out.println(res);
}
B - YYMM or MMYY
private void solveB() {
int wk = nextInt();
int front = wk / 100;
int back = wk % 100;
if ((0 < front && front <= 12) && (back <= 0 || back > 12)) {
out.println("MMYY");
} else if ((0 < back && back <= 12) && (front <= 0 || front > 12)) {
out.println("YYMM");
} else if ((0 < front && front <= 12) && (0 < back && back <= 12)) {
out.println("AMBIGUOUS");
} else {
out.println("NA");
}
}
C - Dice and Coin
- 端数処理面倒なのでBigDecimalを利用
例1：
3面ダイスを振るので
1が出た場合、4回連続でコインの表がでる必要がある
1がでたら： $1×2×2×2×2 = 16$
確率： $ \frac{1}{3} × (\frac{1}{2})^4 $
2が出た場合、3回連続でコインの表がでる必要がある
2がでたら： $2×2×2×2 = 16$
確率： $ \frac{1}{3} × (\frac{1}{2})^3 $
3が出た場合、2回連続でコインの表がでる必要がある
3がでたら： $3×2×2 = 12$
確率： $ \frac{1}{3} × (\frac{1}{2})^2 $
総計(1が出た場合+2が出た場合+3が出た場合)としては以下
$ \frac{1}{3} × (\frac{1}{2})^4 + \frac{1}{3} × (\frac{1}{2})^3 +\frac{1}{3} × (\frac{1}{2})^2 = \frac{7}{48} $
くくって式を簡略化**(実装時に端数処理を考えるのが面倒なので、割り算は最後に持っていく)**
$ ((\frac{1}{2})^4 + (\frac{1}{2})^3 + (\frac{1}{2})^2) × \frac{1}{3} = \frac{7}{48} $
- まとめると
- コインの表を何回出すのかをそれぞれ計算して合算
- 1が出た時、何回2倍すればよいのか
- 2が出た時、何回2倍すればよいのか
- 3が出た時、何回2倍すればよいのか
- 以下、ダイスの面だけループ
- 最後に、ダイスの面の数で割る
- 小数点以下桁数は11桁くらいできっとけば大丈夫
- コインの表を何回出すのかをそれぞれ計算して合算
private void solveC() {
int n = nextInt();
int k = nextInt();
BigDecimal res = new BigDecimal("0");
for (int i = 1; i <= n; i++) {
int pow = recursiveC(i, k);
/*
* コインの裏表は1/2なので0.5のn乗
* ダイス面がiの時、0.5^pow
*/
BigDecimal powB = new BigDecimal("0.5").pow(pow);
//足しておく
res = res.add(powB);
}
//最後、一括でダイス面で割る
out.println(res.divide(new BigDecimal(n), 11, RoundingMode.HALF_UP));
}
/**
* 何回×2したらnを超えるのかを返す
* @param i
* @param n
* @return
*/
private int recursiveC(int i, int n) {
if (i >= n) {
return 0;
}
return recursiveC(i * 2, n) + 1;
}
D - Even Relation(BFS版)
参考サイト
AtCoder ABC 126 D - Even Relation (400 点)
- 上記けんちょんさんの参考サイトにはDFSでの解法が載っています。そちらを参考にしました。
- 自分でもDFSで解いたのがあるが、けんちょんさんのサイトの方が分かりやすいので自分のは載せない
- 総当たりするでもなく、1つ根を決めてそこからの距離の偶奇で塗り分ける(説明観ないとわからんかったが)
- 多分、ダイクストラでもいけるんじゃないか？？？今度試そう。
private void solveD() {
int n = nextInt();
int[] u = new int[n - 1];
int[] v = new int[n - 1];
int[] w = new int[n - 1];
/*
* 辺のMapを作成
*/
Map<Integer, List<Edge>> wk = new TreeMap<Integer, List<Edge>>();
for (int i = 0; i < n - 1; i++) {
Edge e = null;
List<Edge> tmp = null;
u[i] = nextInt() - 1;
v[i] = nextInt() - 1;
w[i] = nextInt();
/*
* コストは偶奇以外不要なのでmodしたけど別にしなくてもよかったよね。。。
*/
int cost = w[i] % 2;
e = new Edge();
e.from = u[i];
e.to = v[i];
e.cost = cost;
tmp = wk.getOrDefault(e.from, new ArrayList<Edge>());
tmp.add(e);
wk.put(e.from, tmp);
e = new Edge();
e.from = v[i];
e.to = u[i];
e.cost = cost;
tmp = wk.getOrDefault(e.from, new ArrayList<Edge>());
tmp.add(e);
wk.put(e.from, tmp);
}
/*
* BFS用のQueue
*/
Deque<Edge> ek = new ArrayDeque<Edge>();
/*
* tree探索するための最初のqueの選択
* なんでもよいわけではなくて、子が一つのものを選択
* 頂点がN個で辺がN-1個なので、必ずこの条件にあてはまるものがいる。
* while()の中で最初のqueueだけは自分の行き先を全て見ていないので。
* まぁ、while()に入る前に位置0のedgeを全てqueueに入れておけば良いだけな気はしている。
*/
for (List<Edge> edges : wk.values()) {
if (edges.size() == 1) {
ek.addLast(edges.get(0));
break;
}
}
// ek.addLast(wk.get(0).get(0));
int[] res = new int[n];
//色の格納用
res[0] = 0;
while (!ek.isEmpty()) {
Edge e = ek.removeLast();
/*
* costの偶奇で塗る色を決定
*/
if (e.cost % 2 == 0) {
//偶数ならfromもtoも同じ色
res[e.to] = res[e.from];
} else {
//奇数ならfromと違う色にtoを塗る必要がある
res[e.to] = 1 - res[e.from];
}
//toに子がいるのかの探索
List<Edge> edges = wk.get(e.to);
for (Edge edge : edges) {
/*
* 親↔子が循環しないように
*/
if (e.from == edge.to) {
continue;
}
/*
* 探索対象なのでQueueにadd
*/
ek.addLast(edge);
}
}
for (int resN : res) {
out.println(resN);
}
}
/**
* 辺を表すためのinnerクラス
*/
private static class Edge {
private int from;
private int to;
private int cost;
}