はじめに
今回はコンテスト中にDまで、コンテスト後にGが解けたのでそれを載せようと思います。
なお、僕のライブラリは提出結果よりご確認ください。
では、見ていきましょう。
A - 3.14
問題文はこちら
問題文にあるものをコピーして、replaceメソッドを用いて小数第$N$位まで出力しました。
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 ) {
//円周率を文字列として保持
String S = "3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679";
//Nの受け取り
int N = sc.nextInt();
//"3."も考慮して+2してる
out.println(S.substring(0,N+2));
out.close();
}
}
新ジャッジになって、これくらいの処理なら30ms台になったんですね。
B - Roulette
問題文はこちら
$X$に賭けているか順に見ていき、賭けていて、かつこれまでの人より賭けた目の個数が最も少ないかどうかを見ながらArrayListに追加していくことで解きました。昇順に見ていくのでArrayListの中身をソートする必要はありません。
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 ) {
//Nの受け取り
int N = sc.nextInt();
//HashSetで各人の賭けた目を保持
ArrayList<HashSet<Integer>> list = new ArrayList<>();
for(int i=0;i<N;i++){
HashSet<Integer> set = new HashSet<Integer>();
int C = sc.nextInt();
while(C-->0)
set.add(sc.nextInt());
list.add(set);
}
//Xの受け取り
int X = sc.nextInt();
//対象の人を格納するArrayList
ArrayList<Integer> ans = new ArrayList<>();
//一番少ない賭け数を記録する変数
int min = Integer.MAX_VALUE;
//先頭から順に見ていく
for(int i=0;i<N;i++){
//Xに賭けてる？
if(list.get(i).contains(X)){
//他の人と賭けた数が同じなら追加
if(list.get(i).size()==min){
ans.add(i+1);
}
//他の人より賭けた数が少ないならansを初期化して追加
else if(list.get(i).size()<min){
min = list.get(i).size();
ans = new ArrayList<>();
ans.add(i+1);
}
}
}
//答えとなる人の数を出力
out.println(ans.size());
//小さい方から順に出力
if(ans.size()>0)
out.print(ans.get(0));
for(int i=1;i<ans.size();i++){
out.print(" ");
out.print(ans.get(i));
}
out.println();
out.close();
}
}
読解に思ったより時間をかけてしまいました…。
C - Rotate Colored Subsequence
問題文はこちら
同じ色の文字同士を先頭から順にArrayDequeに格納していき、1つ巡回シフトした後に色の番号を元に文字列を再構築することで問題を解きました。
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、S、Cの受け取り
int N = sc.nextInt();
int M = sc.nextInt();
String S = sc.next();
int[] C = sc.nextInt(N);
//各色別に格納
ArrayList<ArrayDeque<Character>> list = new ArrayList<>();
for(int i=0;i<=M;i++)
list.add(new ArrayDeque<>());
for(int i=0;i<N;i++)
list.get(C[i]).add(S.charAt(i));
//巡回シフト
for(int i=1;i<=M;i++){
if(list.get(i).size()>0){
Character c = list.get(i).pollLast();
list.get(i).addFirst(c);
}
}
//再構築
StringBuilder ans = new StringBuilder();
for(int i=0;i<N;i++)
ans.append(list.get(C[i]).pollFirst());
//出力
out.println(ans);
out.close();
}
}
よく見たらどの色も一文字以上含まれてたんですね。気付かなかった…。
D - LOWER
問題文はこちら
クエリを先読みしておき、後ろから以下のように処理しました。
・クエリ1：$x$文字目に対するクエリ1とクエリ2、3がまだ処理されてなければ$c$に置換
クエリ2、3のみ処理されている場合はそれに合わせた文字に変換して置換
・クエリ2：クエリ2、3がまだ処理されてなければクエリ1で処理してない箇所を小文字に変換
・クエリ3：クエリ2、3がまだ処理されてなければクエリ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、S、Q、クエリの受け取り
int N = sc.nextInt();
char[] S = sc.nextCharArray();
int Q = sc.nextInt();
int[] queryT = new int[Q];
int[] queryX = new int[Q];
char[] queryC = new char[Q];
//クエリは逆順にしておく
for(int i=0;i<Q;i++){
queryT[Q-i-1] = sc.nextInt();
queryX[Q-i-1] = sc.nextInt();
queryC[Q-i-1] = sc.nextChar();
}
//クエリ2、3が出現したか
boolean flag = false;
//クエリ2、3が出現したとして、小文字か大文字か
boolean small = false;
//クエリ1が出現したか
boolean[] changed = new boolean[N];
//降順にクエリを処理
for(int i=0;i<Q;i++){
//クエリ1
if(queryT[i]==1){
//すでに置換済みならスルー
if(changed[queryX[i]-1])
continue;
//クエリ2、3を処理済みならそれに合わせて文字を変換
if(flag){
if(small)
S[queryX[i]-1] = queryC[i]<'a'?(char)(queryC[i]+'a'-'A'):queryC[i];
else
S[queryX[i]-1] = queryC[i]<'a'?queryC[i]:(char)(queryC[i]-'a'+'A');
}
//クエリ2、3を処理してないならそのまま
else
S[queryX[i]-1] = queryC[i];
changed[queryX[i]-1] = true; //置換済みにしておく
}
//クエリ2
else if(queryT[i]==2){
//クエリ2、3をまだ処理してないなら処理する
if(!flag){
flag = true;
small = true;
for(int j=0;j<N;j++){
if(!changed[j]&&S[j]<'a')
S[j] = (char)(S[j]+'a'-'A');
}
}
}
//クエリ3
else if(queryT[i]==3){
//クエリ2、3をまだ処理してないなら処理する
if(!flag){
flag = true;
small = false;
for(int j=0;j<N;j++){
if(!changed[j]&&S[j]>'Z')
S[j] = (char)(S[j]-'a'+'A');
}
}
}
}
//処理終了後のSの出力
out.println(S);
out.close();
}
}
今思えば普通に先頭から処理できましたね。
D改.java
import java.util.Scanner;
import java.util.HashSet;
class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
//N、S、Qの受け取り
int N = sc.nextInt();
char[] S = sc.next().toCharArray();
int Q = sc.nextInt();
//最後に出たのが2、3のどちらか管理する変数
int lastFlip = -1;
//2、3出現後で置換済みの箇所
HashSet<Integer> set = new HashSet<>();
//Q個のクエリの処理
while(Q-->0){
//t、x、cの受け取り
int t = sc.nextInt();
int x = sc.nextInt()-1;
char c = sc.next().charAt(0);
//クエリ1
if(t==1){
//置換して記録
S[x] = c;
set.add(x);
}
//クエリ2
else if(t==2){
//setを初期化して記録
set = new HashSet<>();
lastFlip = 2;
}
//クエリ3
else if(t==3){
//setを初期化して記録
set = new HashSet<>();
lastFlip = 3;
}
}
//1回以上2、3を処理した時
if(lastFlip>0)
for(int i=0;i<N;i++)
if(!set.contains(i)) //置換してないなら2、3に合わせた文字に変換
S[i] = (char)(lastFlip==2?S[i]|32:S[i]&~32);
//処理後のSの出力
System.out.println(S);
}
}
G - Amulets
問題文はこちら
公式解説の通りです。
G.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、Hの受け取り
int N = sc.nextInt();
int M = sc.nextInt();
long H = sc.nextLong();
//i番目を倒すのに必要な最小個数
int[] ans = new int[N];
//各タイプの総ダメージ
final long[] sum = new long[M];
//現状蓄積しているダメージ
long now = 0;
//使わなくて良いお守りのSet
TreeSet<Integer> set1 = new TreeSet<>(
(a,b)->sum[a]!=sum[b]?Long.compare(sum[a],sum[b]):Integer.compare(a,b)
);
//使わなくちゃいけないお守りのSet
TreeSet<Integer> set2 = new TreeSet<>(
(a,b)->sum[a]!=sum[b]?Long.compare(sum[a],sum[b]):Integer.compare(a,b)
);
//とりあえずset1に全部格納
for(int i=0;i<M;i++)
set1.add(i);
//順に処理
for(int i=0;i<N;i++){
//A、Bの受け取り
long A = sc.nextLong();
int B = sc.nextInt()-1;
//Bが含まれている方のSetの更新
if(set1.contains(B)){
now += A;
set1.remove(B);
sum[B] += A;
set1.add(B);
}
else{
set2.remove(B);
sum[B] += A;
set2.add(B);
}
//set1の中でset2にあるタイプより総ダメージが多いタイプが含まれているものをswap
while(set1.size()>0&&set2.size()>0&&sum[set1.last()]>sum[set2.first()]){
Integer num1 = set1.pollLast();
Integer num2 = set2.pollFirst();
now -= sum[num1];
now += sum[num2];
set1.add(num2);
set2.add(num1);
}
//倒されてしまう場合の処理(set2に一つ移して適当に処理する)
while(now>=H){
int num = set1.pollLast();
now -= sum[num];
set2.add(num);
while(set2.size()>0&&sum[set2.first()]+now<H){
now += sum[set2.first()];
set1.add(set2.pollFirst());
}
}
//必要な個数の記録
ans[i] = set2.size();
}
//答え
int[] answer = new int[M+1];
//各個数における最大値の記録
for(int i=0;i<N;i++)
answer[ans[i]] = i+1;
//少ない個数でより倒せる時があるかわからないけど一応処理しておく
for(int i=0;i<M;i++)
answer[i+1] = Math.max(answer[i+1],answer[i]);
out.println(answer);
out.close();
}
}
解説見れば確かに…とはなるんですけど…まだまだ本番でACできる実力は無いですね…。
感想
A,B,C:易しい
D:ちょっと焦ってしまった…
G:本番中に見て解けそうな気はしたけど、結局解けなかった…
って感じでした。
E、まだ理解できてないのでそのうちまた追記します。