AtCoder |
C
1,2,3のいずれかで移動出来る。
Nから0に移動する。
NGの数値が与えられて、NGの数字には移動出来ない。
貪欲法で3,2,1の順番に移動出来るかチェックする。
void solve() throws Throwable {
startTime = System.currentTimeMillis();
String NO = "NO" ;
String YES = "YES";
int N = readInt();
int[] ng = new int[3];
for(int i = 0; i < 3; i++) {
ng[i] = readInt();
if (ng[i] == N) {
pw.println(NO);
return;
}
}
int now = N;
for (int i = 0; i < 100; i++) {
boolean isRoopUpdate = false;
for (int j = 3; j > 0; j--) {
boolean isUpdate = true;
int koho = now - j;
if (koho < 0) continue;
for(int n : ng) {
if (koho == n) {
isUpdate = false;
break;
}
}
if (isUpdate) {
if (koho == 0) {
pw.println(YES);
return;
}
now = koho;
isRoopUpdate = true;
break;
}
}
if (!isRoopUpdate) {
break;
}
}
pw.println(NO);
}
D問題
Dの距離を移動出来る人がN回移動したときに
X,Yの地点にいる確率を求める。
まずはSRMのTCO、1C Div2のHard問題の解法を適用するも100点。
TLE。O（N^3)では間に合わない。
ニコ生の解説によると、
パスカルの三角形を使用した解法がよいみたい。
それと、こういう移動系の問題は、左と下への移動を考えないというのが
有効なテクニックになる。
上と右への移動から、左と下への移動は推測出来るってことね。
正答は明日考えよう。
・・・・・・・
やっと出来た。
5時間ぐらいかかったんじゃなかろうか・・・・
パスカルの三角形を使って、nCi(nは事象の起きる総数。iは対象の事象）を計算する。
上下方向に進む確率(nCi) * 上下方向に進む事象の中で目的にたどり着く確率(iCx) * 左右方向に進む事象の中で目的にたどり着く確率((N-i)Cy)
上下方向に進む全パターンの総和が対象の確率となる。
パスカルの三角形は組み合わせの確率を出すのに便利だ。
Nが1000以内なら使えそう。
static class Pascale {
static BigDecimal[][] probability = new BigDecimal[1010][1010];
static {
//probability[0] = new double[1]l;
for (int i = 0; i < probability.length; i++) {
Arrays.fill(probability[i], BigDecimal.ZERO);
}
probability[0][0] = BigDecimal.ONE;
for (int i = 1; i < probability.length; i++) {
//probability[i] = new double[i + 1];
probability[i][0] = BigDecimal.ONE;
probability[i][i] = BigDecimal.ONE;
for (int j = 1; j < i ; j++) {
probability[i][j] = probability[i - 1][j - 1].add(probability[i - 1][j]);
}
}
}
static BigDecimal calc(int cnt, int pCnt) {
BigDecimal allCnt = new BigDecimal(2).pow(cnt);
BigDecimal elementCnt = probability[cnt][pCnt];
BigDecimal p = elementCnt.divide(allCnt, MathContext.DECIMAL128);
return p;
}
}
/**
* @throws Throwable
*/
void solve() throws Throwable {
startTime = System.currentTimeMillis();
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int D = sc.nextInt();
int X = sc.nextInt();
int Y = sc.nextInt();
if (X % D != 0 || Y % D != 0) {
pw.println(0);
return;
}
X = Math.abs(X / D);
Y = Math.abs(Y / D);
BigDecimal res = BigDecimal.ZERO;
for (int i = X; i <= N; i++) {
// iは上下方向への総移動回数
// moveXCntは目的方向への移動回数
int moveXCnt = (i - X);
if (moveXCnt %2 !=0) {
// 目的方向への移動後に余った移動回数が偶数でない場合に目的地に戻れないのでコンテニューする
continue;
}
moveXCnt = moveXCnt / 2 + X;
int moveYCnt = (N - i - Y);
if (moveYCnt < 0 || moveYCnt %2 !=0) {
continue;
}
moveYCnt = moveYCnt / 2 + Y;
res = res.add(Pascale.calc(N, i).multiply(Pascale.calc(i, moveXCnt).multiply(Pascale.calc(N - i, moveYCnt))));
}
pw.println(res);
}
400点で65位。
過去最高かな？yeah
・A問題
重複を除いた文字種の数をカウントする。
既に使った文字をメモしておく。
void solve() throws Throwable {
startTime = System.currentTimeMillis();
char[] c = br.readLine().toCharArray();
boolean[] used = new boolean[30];
int sum = 0;
for (char x : c) {
if (x >= 'a' && x <= 'z') {
if (!used[x - 'a']) {
used[x - 'a'] = true;
sum++;
}
}
}
pw.println(sum);
}
・B問題
ある文字列が与えられたときに、
その文字列の部分文字列を連続して同じになる場合の最長の長さを答える。
また、引数で指定されたintを文字列の右に加算してよい。
void solve() throws Throwable {
char[] c = br.readLine().toCharArray();
int K = readInt();
int N = c.length;
int max = 0;
for (int i = 0; i < N; i++) {
for (int j = 2; i + j <= N + K; j+=2) {
boolean isFalse = false;
for (int k = 0; k < j / 2; k++) {
if (i + j / 2 + k < N) {
if (c[i + k] != c[i + j / 2 + k ]) {
isFalse = true;
break ;
}
}
}
if (!isFalse) {
max = max(max, j);
}
}
}
pw.println(max);
}
C,D,Eは解けず。
1400⇒1451
最高レート更新ヽ(^o^)丿
TopCoder |
SRM625 Div2参戦
Easy問題
a*b+c=x
xが与えられるので、a,b,cの値を返却しろという問題
ただし、a,b,cに0,1を使用してはならない。
a,b,c,xに使用できる値の制約が厳しいので
何も考えずにシミュレーションすればOK.
public int[] makeExpression(int y) { int res[] = new int[3]; for (int i = 1000; i >= -1000; i--) { if (i == 0 || i == 1) { continue; } int tmp = y - i; for (int j = 2; j < 10; j++) { for (int j2 = j; j2 < 100; j2++) { if(tmp == j * j2) { res[0] = j; res[1] = j2; res[2] = i; return res; } } } } return res; }
ちなみにこれは修正版です。
テストの際は間違えてました。
Medium問題
intの配列と一回に加算できる数値が与えられる。
加算は何回でも出来る。
intの配列にkを加えて、1,2,3・・・・n(配列の長さ)にすることが出来るかを判定する。
1,2,3・・・・・nの数値を達成することが出来たかを管理する
booleanの配列を持って、
オリジナルのint配列と照らし合わせる。
既にその数値が達成されている場合にKを加算する。
public String canItBeDone(int k, int[] A) { String OK = "POSSIBLE"; String NOT = "IMPOSSIBLE"; boolean[] res = new boolean[A.length + 1]; for (int j = 0; j < A.length; j++) { int tmp = 0; int i = A[j]; while(i + tmp * k <= A.length) { if (!res[i + tmp * k]) { res[i + tmp * k] = true; break; } tmp++; } } for (int i = 1; i <= A.length; i++) { if (!res[i]) { return NOT; } } return OK; }
Hard問題
嘘つきと正直者が輪になって座っている。
それぞれの人に右隣の人が嘘つき(L)か正直者(H)かを尋ねる。
嘘つきは常に嘘を、正直者は常に正直に答える。
ただし、質問されていない人(?)もいる。
最小の嘘つきの人数を答える。
ただし、ゲームが成立していない場合？、-1を返却する。
LLLの場合、一人目が嘘つきでも正直者でも矛盾が発生する。
char[] array = null;
boolean isLast = false;
int sum = -1;
public int minimumLiars(String answers)
{
array = answers.toCharArray();
dfs(0, 0, false);
isLast = true;
dfs(0, 0, true );
return sum;
}
void dfs(int x, int lier, boolean isHonest) {
for (int i = x; i < array.length; i++) {
if (isHonest) {
if (array[i] == 'L') {
lier++;
isHonest = false;
} else if (array[i] == 'H') {
} else {
if (i + 1 < array.length && array[i + 1] == '?') {
} else {
dfs(i + 1, lier, true);
dfs(i + 1, lier + 1, false);
return;
}
}
} else {
if (array[i] == 'L') {
isHonest = true;
} else if (array[i] == 'H') {
lier++;
} else {
if (i + 1 < array.length && array[i + 1] == '?') {
} else {
dfs(i + 1, lier, true);
dfs(i + 1, lier + 1, false);
return;
}
}
}
}
if (isHonest == isLast) {
if (sum == -1) {
sum = 10000;
}
sum = Math.min(sum, lier);
return ;
}
}
誤答。
上の解答はプラクティスモードで通したものです。
解答方法はテスト中に思いついたものと同じなんだけど、
?が50この時にO(2^50)で間に合わないと思ったけど、
?が連続した場合は分岐しなくていいから、maxでもO(2^25)で
間に合うなぁ。残念。
Mediumのみ正解だったけど、
チャレンジモードで75点稼いで
レートアップに成功。
1054⇒1072