はじめに
今回はコンテスト中にDまで解けたので提出コードをそのまま載せようと思います。
では、見ていきましょう。
※ライブラリがこれまでとちょっと変わってるので気になる方は提出コードをご覧ください。
A - Contest Result
問題文はこちら
普通に$B$を添え字として$A$の和を求めれば良いですね。$B$が1-indexedであることに注意です。
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);
//和を取る
long ans = 0;
for(int num:B)
ans += A[num-1];
out.println(ans);
out.close();
}
}
易しめですね。
B - Qual B
問題文はこちら
先頭$K$個のoはそのまま、それ以降のoはxに変換して出力しました。
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、Sの受け取り
int N = sc.nextInt();
int K = sc.nextInt();
char[] S = sc.nextCharArray();
//xにすべきところをxに変換
for(int i=0;i<N;i++)
if(S[i]=='o'&&K--<=0)
S[i] = 'x';
//出力
out.println(S);
out.close();
}
}
&&の左辺がfalseであれば右辺の評価はされないのでこれで$K$個分oをスルー出来ます。
C - Max MEX
問題文はこちら
$K$個要素を選んだ時の$MEX(X)$は$K$を超えないので、$\mathrm{min}(MEX(A),K)$が答えとなります。
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、Aの受け取り
int N = sc.nextInt();
int K = sc.nextInt();
int[] A = sc.nextInt(N);
//TreeSetに入れて、MEX(A)を調べる
TreeSet<Integer> set = new TreeSet<>();
for(int num:A)
set.add(num);
//Kに達した時点で切りあげるように
int index = 0;
while(!set.isEmpty()&&set.first()==index&&K-->0){
set.pollFirst();
index++;
}
//出力
out.println(index);
out.close();
}
}
!set.isEmpty()を入れ忘れてREでペナルティを2回も食らってしまいました…焦りすぎですね…。
D - Marking
問題文はこちら
以下、$D$は$D$%$N$に置き換えても一般性を失わないので置き換えたものとして話を進めます($D$が$N$の倍数の場合は$1$に)。
あまりを取らなかった場合の$x$の値は$D(K-1)$です。そして、$x$が過去に印をつけた箇所と被る周期は$\mathrm{lcm}(N,D)$です。したがって、あまりを取らなかったときの$x$に対して被った分だけ加算して$N$で割ったあまりを求める、以下の式で答えが求められます。
$$( \lfloor \frac{D(K-1)}{\mathrm{lcm}(N,D)} \rfloor +D(K-1))\ \mathrm{mod}\ N$$
公式解説の式への変形
上記の式を式Aとします。
公式解説を見ると以下の式を用いて求めています。
$$\lfloor \frac{K-1}{N / \mathrm{gcd}(N,D)} \rfloor +D(K-1)\ \mathrm{mod}\ N$$
後ろの項はそのままなので前の項を式Aの前の項から導きます。
$N=ng$、$D=dg$($g$は$\mathrm{gcd}(N,D)$)とすると、$\mathrm{lcm}(N,D)=ndg$です。したがって、式Aの前の項は以下のように変形できます。
$$\frac{D(K-1)}{\mathrm{lcm}(N,D)}=\frac{dg(K-1)}{ndg}=\frac{K-1}{n}$$
よって、$n=N / \mathrm{gcd}(N,D)$より式Aは公式解説の式と同じ式になります。
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 ) {
//Tの受け取り
int T = sc.nextInt();
while(T-->0){
//N、Dの受け取り
int N = sc.nextInt();
int D = sc.nextInt()%N; //Nで割ったあまりに変換
if(D==0)
D++; //「D==0だとずっと被り続ける」=「Dが1の時と同じ挙動」をするので1に変換
//x=0から始まるので1引いておいた方が楽
int K = sc.nextInt()-1;
//上記の式の実装
out.println(((long)D*K/MathFunction.lcm(N,D)+(long)D*K)%N);
}
out.close();
}
}
気付かなくてずっと愚直に求めるコードを書いてしまってました…。
感想
A,B:易しい
C:ペナこそあったが、気付けば難しくはない
D:全然頭回ってなかった…
という感じでした。
焦りがまんまペナルティとして出た感じでした…。改めて、精進し直します。
追記(E - Make it Palindrome)
問題文はこちら
公式解説の通りです。
import java.util.Scanner;
import java.util.ArrayList;
class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
//Nの受け取り
int N = sc.nextInt();
//各要素のインデックスを格納
ArrayList<ArrayList<Integer>> index = new ArrayList<>();
for(int i=0;i<=N;i++)
index.add(new ArrayList<>());
for(int i=1;i<=N;i++){
int A = sc.nextInt();
index.get(A).add(i);
}
//全部の線の数え上げ
long ans = 0;
for(long i=1;i<=N;i++)
ans += (N+1-i)*(i/2);
//良い線を引く工程
for(int i=1;i<=N;i++){
int l = 0;
int r = index.get(i).size()-1;
while(l<r){
if(index.get(i).get(l)<N+1-index.get(i).get(r))
ans -= (long)(r-l)*index.get(i).get(l++);
else
ans -= (long)(r-l)*(N+1-index.get(i).get(r--));
}
}
//出力
System.out.println(ans);
}
}
解説の悪い線を数えれば良さそうだなぁとは思ったのですが、それ以上思考を発展させることができませんでした…。