はじめに
今回はEまでコンテスト中に解けて、Fもコンテスト後に解いたのでそのコードを載せようと思います。
では、見ていきましょう。
なお、ライブラリに関しては提出結果をご覧ください。
A - Filter
問題文はこちら
問題文のまま実装しました。
A.java
final class Main {
private static final boolean autoFlush = false;
private static final SimpleScanner sc = new SimpleScanner( System.in );
private static final SimplePrinter out = new SimplePrinter( System.out, autoFlush );
public static void main ( String[] args ) {
//N、Aの受け取り
int N = sc.nextInt();
int[] A = sc.nextInt(N);
//先頭から見て、偶数だったら空白区切りで出力
for(int num:A)
if(num%2==0)
out.print(num+" ");
out.close();
}
}
今思えばStream使った方が簡潔でしたね。
B - ASCII Art
問題文はこちら
受け取りながらSを構築して出力しました。
B.java
final class Main {
private static final boolean autoFlush = false;
private static final SimpleScanner sc = new SimpleScanner( System.in );
private static final SimplePrinter out = new SimplePrinter( System.out, autoFlush );
public static void main ( String[] args ) {
//H、Wの受け取り
int H = sc.nextInt();
int W = sc.nextInt();
char[][] S = new char[H][W];
for(int i=0;i<H;i++){
for(int j=0;j<W;j++){
//A[i][j]の受け取り
int A = sc.nextInt();
//問題文の通りに変換
if(A==0)
S[i][j] = '.';
else
S[i][j] = (char)(A+'A'-1);
}
}
//答えの出力
out.println(S);
out.close();
}
}
これもそこまで難しくないですね。
C - Merge Sequences
問題文はこちら
$C$を構築して先頭から$A$、$B$と一致するか見ていって答えを構築しました。
C.java
final class Main {
private static final boolean autoFlush = false;
private static final SimpleScanner sc = new SimpleScanner( System.in );
private static final SimplePrinter out = new SimplePrinter( System.out, autoFlush );
public static void main ( String[] args ) {
//N、M、A、Bの受け取り
int N = sc.nextInt();
int M = sc.nextInt();
int[] A = sc.nextInt(N);
int[] B = sc.nextInt(M);
//Cの構築
int[] C = new int[N+M];
System.arraycopy(A,0,C,0,N);
System.arraycopy(B,0,C,N,M);
ArrayFunction.sort(C);
//答え用の配列
int[] ansA = new int[N];
int[] ansB = new int[M];
//どこまで見たかを管理する変数
int indexA = 0;
int indexB = 0;
//先頭から一致する方の配列に答えを格納
for(int i=0;i<N+M;i++){
if(indexA<N&&A[indexA]==C[i])
ansA[indexA++] = i+1;
else
ansB[indexB++] = i+1;
}
//答えの出力
out.println(ansA," ");
out.println(ansB," ");
out.close();
}
}
マージソートみたいですね。
D - Bank
問題文はこちら
問題文のまま実装しました。呼ばれた人は追加、削除が速いTreeSetで管理しています。
D.java
final class Main {
private static final boolean autoFlush = false;
private static final SimpleScanner sc = new SimpleScanner( System.in );
private static final SimplePrinter out = new SimplePrinter( System.out, autoFlush );
public static void main ( String[] args ) {
//Nの受け取り
int N = sc.nextInt();
//呼ばれていない人用
TreeSet<Integer> notCalled = new TreeSet<>();
//呼ばれている人用
TreeSet<Integer> called = new TreeSet<>();
//初期状態にセット
for(int i=1;i<=N;i++)
notCalled.add(i);
//Qの受け取り
int Q = sc.nextInt();
while(Q-->0){
//イベント番号の受け取り
int e = sc.nextInt();
//それぞれ問題文の通りに処理
if(e==1){
called.add(notCalled.pollFirst());
}
else if(e==2){
int x = sc.nextInt();
called.remove(x);
}
else{
out.println(called.first());
}
}
out.close();
}
}
呼ばれてない人はintで管理した方が良かったですね。
E - 2xN Grid
問題文はこちら
各行について、TreeMapで先頭から何列目かをkey、変換後の値をvalueとして保持し、各行の値を更新しながら一致している列数をカウントしました。
E.java
final class Main {
private static final boolean autoFlush = false;
private static final SimpleScanner sc = new SimpleScanner( System.in );
private static final SimplePrinter out = new SimplePrinter( System.out, autoFlush );
public static void main ( String[] args ) {
//L、N1、N2の受け取り
long L = sc.nextLong();
int N1 = sc.nextInt();
int N2 = sc.nextInt();
//各行の情報を保持するようのmap
TreeMap<Long,Integer> map1 = new TreeMap<>();
TreeMap<Long,Integer> map2 = new TreeMap<>();
//先頭から何番目かを得るために累積和のように
long sum = 0;
while(N1-->0){
int v = sc.nextInt();
long l = sc.nextLong();
map1.put(sum+=l,v);
}
sum = 0;
while(N2-->0){
int v = sc.nextInt();
long l = sc.nextLong();
map2.put(sum+=l,v);
}
//今見ている列番号と値
long now1 = 0;
int val1 = 0;
long now2 = 0;
int val2 = 0;
//答え用
long ans = 0;
//どっちも空になるまで
while(map1.size()+map2.size()>0){
//1行目の方が先頭からの距離が短いなら1行目を更新
if(now1<now2){
Map.Entry<Long,Integer> m = map1.pollFirstEntry();
//次の値が2行目と一致しているならansにその分を加算
if(val2==m.getValue())
ans += Math.min(now2,m.getKey())-now1;
//情報の更新
now1 = m.getKey();
val1 = m.getValue();
}
//2行目の方が先頭に近いなら2行目を更新
else{
Map.Entry<Long,Integer> m = map2.pollFirstEntry();
//次の値が1行目と一致しているならansにその分を加算
if(val1==m.getValue())
ans += Math.min(now1,m.getKey())-now2;
//情報の更新
now2 = m.getKey();
val2 = m.getValue();
}
}
//答えの出力
out.println(ans);
out.close();
}
}
これもTreeMapじゃなくて普通にArrayDequeとかで良かったですね…。
F - Sugar Water 2
問題文はこちら
公式解説のものとほぼ同一です。考えやすいので二分探索の上限下限は$0$と$1$ではなく$0$と$100$にしています。
F.java
final class Main {
private static final boolean autoFlush = false;
private static final SimpleScanner sc = new SimpleScanner( System.in );
private static final SimplePrinter out = new SimplePrinter( System.out, autoFlush );
public static void main ( String[] args ) {
//N、M、Kの受け取り
int N = sc.nextInt();
int M = sc.nextInt();
long K = sc.nextLong();
//高橋君、青木君のもっている砂糖水の情報の受け取り
long[][] sugerT = sc.nextLong(N,2);
long[][] sugerA = sc.nextLong(M,2);
//二分探索の上限下限の設定
double a = 0;
double b = 100;
//適当な値を入れている答え用変数
double ans = 100;
//そこそこな精度になるまで繰り返す
while(b-a>1e-10){
//調べる濃度
double c = (a+b)/2;
//水1g当たりに必要な砂糖の量
double x = c/(100-c);
//青木君の持っている砂糖水それぞれにおける砂糖の過不足を計算し、ソート
double[] sub = new double[M];
for(int i=0;i<M;i++)
sub[i] = sugerA[i][0]-sugerA[i][1]*x;
Arrays.sort(sub);
//濃度cのものをいくつ作れるか管理する変数
long sum = 0;
//高橋君の持っている砂糖水に対していくつ作れるかを二分探索して加算
for(int i=0;i<N;i++)
sum += M-ArrayFunction.upSearch(sub,sugerT[i][1]*x-sugerT[i][0]);
//作れるのがK個未満ならK番目はこれより小さいはずなので上限値を引き下げ(ついでにansも更新)
if(sum<K)
b = ans = c;
//K個以上作れたのなら下限値を引き上げ
else
a = c;
}
//小数点第9位まで出力
out.printf("%.9f",ans);
out.close();
}
}
二分探索で出来そうとは思ったのですが、じゃあどうやるのか、というところが全くわかりませんでした…。
感想
A,B,C:易しい
D:Dにしては易しい
E:ちょっとめんどくさく感じたけど、易しい部類な気がする
F:難しい…
って感じでした。
速解き回って感じでしたね。こういう回でペナ出した時のダメージがめちゃくちゃデカいので、かなり慎重に提出しました。