はじめに
今回もEまでコンテスト中に解けたのでそれをそのまま載せようと思います。
では、見ていきましょう。
A - wwwvvvvvv
問題文はこちら
char[]として受け取って先頭からvかwか見て加算していきました。
class Main{
static final boolean autoFlush = false;
static final Library System = new Library(java.lang.System.in,java.lang.System.out,java.lang.System.err,autoFlush);
public static void main(String[] args){
//Sの受け取り
char[] S = System.in.nextCharArray();
//順に見て数え上げ
int count = 0;
for(char c:S)
if(c=='v')
count++;
else
count += 2;
//出力
System.out.println(count);
System.out.close();
}
}
特に問題は無いですね。
B - LOOKUP
問題文はこちら
せっかくString::indexOf()があるのでそれを使いました。
class Main{
static final boolean autoFlush = false;
static final Library System = new Library(java.lang.System.in,java.lang.System.out,java.lang.System.err,autoFlush);
public static void main(String[] args){
//S、Tの受け取り
String S = System.in.next();
String T = System.in.next();
//部分文字列か判定
System.out.println(S.indexOf(T)!=-1?"Yes":"No");
System.out.close();
}
}
これも問題は無いですね。
C - RANDOM
問題文はこちら
列ごと並べ替える->行ではなく列でそれぞれ文字列を作って(計$H$個)、それをソートして見れば楽そうだなと思ってそれで実装しました。
class Main{
static final boolean autoFlush = false;
static final Library System = new Library(java.lang.System.in,java.lang.System.out,java.lang.System.err,autoFlush);
public static void main(String[] args){
//H、Wの受け取り
int H = System.in.nextInt();
int W = System.in.nextInt();
//行と列を入れ替えて受け取る用のStringBuilder[]
StringBuilder[] subS = new StringBuilder[W];
StringBuilder[] subT = new StringBuilder[W];
for(int i=0;i<W;i++){
subS[i] = new StringBuilder();
subT[i] = new StringBuilder();
}
//S、Tの受け取り
for(int i=0;i<H;i++)
for(int j=0;j<W;j++)
subS[j].append(System.in.nextChar());
for(int i=0;i<H;i++)
for(int j=0;j<W;j++)
subT[j].append(System.in.nextChar());
//列ごとにソート
Arrays.sort(subS);
Arrays.sort(subT);
//先頭から順に、同じ文字列か判定
boolean canSort = true;
for(int i=0;i<W;i++)
canSort &= subS[i].toString().equals(subT[i].toString());
//全部同じ文字列だったか？
System.out.println(canSort?"Yes":"No");
System.out.close();
}
}
StringBuilder同士の比較って出来ないんですね。コンテスト中に焦ってしまいました。
D - Freefall
問題文はこちら
操作をもう一回行なうべきか否かは以下の式を満たすかどうかで考えられます(現段階での操作回数を$x$とする)。
$\frac{A}{\sqrt{x}}-\frac{A}{\sqrt{x+1}} \ge B$
なので上記の式を満たす最大の$x$を求めてあげれば解けそうだと思い、二分探索で探すようにしました。
class Main{
static final boolean autoFlush = false;
static final Library System = new Library(java.lang.System.in,java.lang.System.out,java.lang.System.err,autoFlush);
public static void main(String[] args){
//A、Bの受け取り
long A = System.in.nextLong();
long B = System.in.nextLong();
//二分探索
long a = 1,b = (long)1e18,ans = 1,c;
while(a-b<=0){
c = (a+b)/2;
//上記の式の値を求める
double temp = A/Math.sqrt(c)-A/Math.sqrt(c+1);
if(B>=temp)
b = (ans = c) - 1;
else
a = c + 1;
}
//答えの出力
System.out.printf("%.7f",(double)B*(ans-1)+A/Math.sqrt(ans));
System.out.close();
}
}
あまりに大きい値だとdoubleが指数表記になってしまうのでprintfを使いました。
・追記
指数表記にはなっていても良いそうです。知らなかった･･･。
E - Cheating Amidakuji
問題文はこちら
$i$回目の操作を行なわなかった場合どうなるかを考えると、全部操作したあとの結果について、$i$回目の操作で入れ替える数字$B_{A_i}$と$B_{A_i+1}$が反転している状態になると考えられます。
ということで、実際に全部の操作を行なってみてどの数字同士が反転したかをメモしておいて順に処理していけば良いと思いそれを実装しました。
class Main{
static final boolean autoFlush = false;
static final Library System = new Library(java.lang.System.in,java.lang.System.out,java.lang.System.err,autoFlush);
public static void main(String[] args){
//N、M、Aの受け取り
int N = System.in.nextInt();
int M = System.in.nextInt();
int[] A = System.in.nextInt(M);
//Bを作る
int[] B = new int[N+1];
for(int i=1;i<=N;i++)
B[i] = i;
//i回目の操作でどの値同士が入れ替わってるか記録するmap
HashMap<Integer,Integer[]> map = new HashMap<>();
//swapしながら記録
for(int i=0;i<M;i++){
int temp = B[A[i]];
B[A[i]] = B[A[i]+1];
B[A[i]+1] = temp;
map.put(i,new Integer[]{B[A[i]],B[A[i]+1]});
}
//B[i]にあった値がiに移動していることを記録するmap
HashMap<Integer,Integer> list = new HashMap<>();
for(int i=1;i<=N;i++)
list.put(B[i],i);
//オートボクシング避け
Integer one = 1;
for(int i=0;i<M;i++){
Integer[] pair = before.get(i);
//swapするべきなら入れ替えた先の場所を、しなくていいならそのまま1の移動先をしゅつりょく
if(pair[0]==one)
System.out.println(list.get(pair[1]));
else if(pair[1]==one)
System.out.println(list.get(pair[0]));
else
System.out.println(list.get(one));
}
System.out.close();
}
}
最初、$i$番目の操作を除いた操作を行なった後の$B$に対して、$i+1$番目の操作を除いた操作を行なうものだと思って非常に時間をロスしてしまいました･･･反省･･･。
感想
A、B:易しい
C:ちょっと考えたけど比較的易しい
D:合ってるか不安なまま解いた感じ･･･
E:気付けば簡単な気がする
って感じでした。
レートが上がって嬉しいですが、次回以降はレート以上にパフォーマンス出さないといけないなぁと思うと不安に感じています･･･。