はじめに
今回はEまで解けたのでそれを載せようと思います。
では見ていきましょう。
なお、ライブラリの内容は提出結果からご確認下さい。
A - Echo
問題文はこちら
一文字ずつ受け取っては2回ずつ出力しました。
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の受け取り
int N = sc.nextInt();
//N個文字を受け取る
while(N-->0){
//一文字受け取って2回出力
char c = sc.nextChar();
out.print(c);
out.print(c);
}
//お気持ちの改行
out.println();
out.close();
}
}
Stringで受け取ってからfor文で2回ずつでも良いと思います。
B - Base 2
問題文はこちら
普通にlongで処理すると$2^{63}$を扱えないので、手っ取り早くBigIntegerを使って処理しました。
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 ) {
//文字列構築用
StringBuilder sb = new StringBuilder();
//Aの受け取り
for(int i=0;i<64;i++)
sb.append(sc.nextInt());
//逆順になっているのでreverseしてBigIntegerに変換して出力
out.println(new BigInteger(sb.reverse().toString(),2));
out.close();
}
}
コンテスト後に気付きましたが、LongクラスのparseUnsignedLongメソッドとtoUnsignedStringを使えばlongでも扱えますね。
B改.java
import java.util.Scanner;
class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
//上記同様最初に二進数表記のStringを構築
StringBuilder sb = new StringBuilder();
for(int i=0;i<64;i++)
sb.append(sc.next());
//符号なし整数として受け取って、符号なし整数として出力
System.out.println(
Long.toUnsignedString(
Long.parseUnsignedLong(sb.reverse().toString(),2)
)
);
}
}
1、2ヶ月前に存在を知ってはいたのですが、やっぱり使っていないと忘れがちですね…。
C - Centers
問題文はこちら
3回ずつ出現するので、ちょうど偶数目の出現の箇所を記録しておけば良いなと思い、boolean型配列で前回の出現が奇数回目かを保持するようにして処理しました。
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の受け取り
int N = sc.nextInt();
//直前が奇数回目か
boolean[] flag = new boolean[N];
//各数字に対して、ans[i][0]に出現したインデックスを入れる配列
//ans[i][1]はi+1を入れておいて、ソート後もわかるように
int[][] ans = new int[N][2];
for(int i=0;i<N;i++)
ans[i][1] = i+1;
//出現箇所の記録
for(int i=0;i<3*N;i++){
int num = sc.nextInt();
if(flag[num-1])
ans[num-1][0] = i;
flag[num-1] = !flag[num-1];
}
//ans[i][0]を基準に二次元配列内の一次元配列をソート
ArrayFunction.sort(ans);
//出力形式を合わせるための配列
int[] answer = new int[N];
//答えを格納して出力
for(int i=0;i<N;i++)
answer[i] = ans[i][1];
out.println(answer);
out.close();
}
}
易しめの問題で助かりました。
D - Poisonous Full-Course
問題文はこちら
動的計画法で解きました。
$\mathrm{dp}[i][j]:i$番目の料理までの最高値($j=0$ならお腹を壊していない、$j=1$ならお腹を壊している)という感じで処理しました。
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();
//X、Yの受け取り
int[] X = new int[N];
int[] Y = new int[N];
for(int i=0;i<N;i++){
X[i] = sc.nextInt();
Y[i] = sc.nextInt();
}
//dpテーブル
long[][] dp = new long[N+1][2];
//遷移
for(int i=0;i<N;i++){
if(X[i]==0){
//毒がないなら食べても食べなくても良いので+max(0,Y[i])
//お腹を壊している状態から治るには食べるしかないので+Y[i]
dp[i+1][0] = Math.max(dp[i][0]+Math.max(0,Y[i]),dp[i][1]+Y[i]);
dp[i+1][1] = dp[i][1]; //食べたら治ってしまうのでこの遷移は食べないときを想定
}
else{
dp[i+1][0] = dp[i][0]; //食べたらお腹を壊すのでこの遷移は食べないときを想定
//毒入りなら亡くなってしまうので食べない遷移と、
//お腹を壊していない状態で食べる遷移の2通り
dp[i+1][1] = Math.max(dp[i][1],dp[i][0]+Y[i]);
}
}
//終了時の高橋君の具合は問われていないので大きい方を
out.println(Math.max(dp[N][0],dp[N][1]));
out.close();
}
}
見辛いのでこれをやる必要はありませんが、遷移のところでifを使いたくない場合は以下のように書けるかと思います。
dp[i+1][X[i]] = Math.max(dp[i][X[i]]+(X[i]^1)*Math.max(0,Y[i]),dp[i][X[i]^1]+Y[i]);
dp[i+1][X[i]^1] = dp[i][X[i]^1];
E - Best Performances
問題文はこちら
降順に並べ替えた時に、後ろ$K$個とそれ以外の$N-K$個を入れる多重集合(TreeMapで簡易的に実装)二つを使って処理しました。
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 ) {
//N、K、Qの受け取り
int N = sc.nextInt();
int K = sc.nextInt();
int Q = sc.nextInt();
//大きい方と小さい方の二つ
TreeMap<Integer,Integer> max = new TreeMap<>();
TreeMap<Integer,Integer> min = new TreeMap<>();
//初期値代入
max.put(0,K);
min.put(0,Math.max(1,N-K)); //後の処理で面倒なので便宜上N=Kなら0を一個入れておく
//現状の解答
long ans = 0;
//問題文のAの準備
int[] A = new int[N+1];
while(Q-->0){
//X、Yの受け取り
int X = sc.nextInt();
int Y = sc.nextInt();
//A[X]がmax側にあるとき
if(max.firstEntry().getKey()<=A[X]){
//maxから削除
max.merge(A[X],-1,(i,j)->i+j==0?null:i+j);
//答えの更新
ans -= A[X];
//minの一番大きい物を記録しておく
Integer m = min.lastEntry().getKey();
if(m==null)
m = Integer.MIN_VALUE; //無いと思うけど念のため
//Yをmaxに入れるべきならmaxに追加して更新
if(m<=Y){
max.merge(Y,1,Integer::sum);
ans += Y;
}
else{
//minに入れるべきならmをmaxに入れてminにYを入れる
max.merge(m,1,Integer::sum);
ans += m; //答えの更新
min.merge(m,-1,(i,j)->i+j==0?null:i+j); //mは取り出しているので削除
min.merge(Y,1,Integer::sum);
}
}
else{
//min側にA[X]があるならminから削除
min.merge(A[X],-1,(i,j)->i+j==0?null:i+j);
int m = max.firstEntry().getKey(); //maxの最小値を記録しておく
//Yをmaxに入れるべきならminにmを移し、maxにYを入れる
if(m<Y){
ans += Y;
max.merge(Y,1,Integer::sum);
ans -= m;
min.merge(m,1,Integer::sum);
max.merge(m,-1,(i,j)->i+j==0?null:i+j);
}
else
min.merge(Y,1,Integer::sum); //minに入れるべきならminに入れて終わり
}
//数列Aの更新
A[X] = Y;
//現状の答えを出力
out.println(ans);
}
out.close();
}
}
いろいろバグらせて2ペナも…悲しい。
感想
A:易しい
B:普通にlong使ったら扱えないものが出てきてびっくり
C:比較的易しい
D:DPって見えやすい問題に感じた
E:発想は出来たけど実装に手間取った
って感じでした。
う～ん…unratedだったから良かったものの、普通にレートが下がる回でした…。
追記(F - Merge Sets)
問題文はこちら
公式解説の通りです。
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、Aの受け取り
int N = sc.nextInt();
int M = sc.nextInt();
int[][] A = sc.nextInt(N,M);
//座標圧縮用
int[] num = new int[N*M];
for(int i=0;i<N;i++)
System.arraycopy(A[i],0,num,i*M,M);
ArrayFunction.sort(num);
//BIT(fenwick tree)
BIT bit = new BIT(N*M);
//答え用変数
long ans = 0;
//走査
for(int i=N-1;i>=0;i--){
for(int j=0;j<M;j++){
A[i][j] = Searcher.search(num,A[i][j])+1;
ans += bit.sum(A[i][j]);
}
for(int j=0;j<M;j++)
bit.add(A[i][j],1);
}
//解説の式に代入
out.println(ans+(long)N*(N-1)/2*M*(M+1)/2);
out.close();
}
}
解説を見れば、確かにそうなんですけど、変形かぁ…思いつかなかったな…。