はじめに
今回はコンテスト中にFまで解けたのでそれをそのまま載せようと思います。
なお、僕のライブラリに関しては提出結果をご確認ください。
では、見ていきましょう。
A - Adjacent Product
問題文はこちら
問題文の通りに実装しました。
A.java
final class Main{
private static final boolean autoFlush = false;
private static final SimpleScanner sc = new SimpleScanner(System.in);
private static final SimpleWriter out = new SimpleWriter(System.out,autoFlush);
public static void main(String[] args){
//N、Aの受け取り
int N = sc.nextInt();
int A = sc.nextInt();
//答えの構築
int[] ans = new int[N-1];
for(int i=0;i<N-1;i++){
int temp = sc.nextInt();
ans[i] = A*temp;
A = temp;
}
//答えの出力
out.println(ans);
out.close();
}
}
B - Piano
問題文はこちら
wbwbwwbwbwbwの何文字目から見始めるかを全探索し、雑に$1000$文字読んで、途中で答えを見つけられるかで判定しました。
B.java
final class Main{
private static final boolean autoFlush = false;
private static final SimpleScanner sc = new SimpleScanner(System.in);
private static final SimpleWriter out = new SimpleWriter(System.out,autoFlush);
public static void main(String[] args){
//Sとして定義
String S = "wbwbwwbwbwbw";
//W、Bの受け取り
int W = sc.nextInt();
int B = sc.nextInt();
//全探索
boolean canMake = false;
for(int i=0;i<S.length();i++){
int sumW = 0;
int sumB = 0;
//テキトーに1000文字見る
for(int j=0;j<1000;j++){
if(S.charAt((i+j)%S.length())=='w')
sumW++;
else
sumB++;
canMake |= W==sumW&&B==sumB;
}
}
//答えの出力
out.println(canMake?"Yes":"No");
out.close();
}
}
C - Σ
問題文はこちら
制約上、無いものを考えるのは難しいです。なので、最初は全部無いものとして考えると答えは$\frac{1}{2}K(K+1)$であることからあるものを差し引いていけば高速に答えを求めることができそうです。
C.java
final class Main{
private static final boolean autoFlush = false;
private static final SimpleScanner sc = new SimpleScanner(System.in);
private static final SimpleWriter out = new SimpleWriter(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);
//初期状態の設定
HashSet<Integer> set = new HashSet<>();
long ans = (long)K*(K+1)/2;
//順に見ていく
for(int a:A)
if(a<=K&&set.add(a)){
ans -= a; //無かったら答えから差し引く
set.add(a);
}
//答えを出力
out.println(ans);
out.close();
}
}
D - Gomamayo Sequence
問題文はこちら
0、1が交互に並んでいる列、すなわち0101...と1010...を構築するのに必要なコストを予め求めておくと、どこまでを01...(10...)にしてどこから10...(01...)に切り替えるか、を全探索することで良い文字列を構築するのに必要な最小コストを求めることができます。
D.java
final class Main{
private static final boolean autoFlush = false;
private static final SimpleScanner sc = new SimpleScanner(System.in);
private static final SimpleWriter out = new SimpleWriter(System.out,autoFlush);
public static void main(String[] args){
//N、S、Cの受け取り
int N = sc.nextInt();
char[] S = sc.nextCharArray();
int[] C = sc.nextInt(N);
//奇数番目、偶数番目が1になるような文字列を構築するときのコストを求める
long[] odd = new long[N+1];
long[] even = new long[N+1];
for(int i=0;i<N;i++){
odd[i+1] = odd[i];
even[i+1] = even[i];
if((S[i]=='0')^(i%2==0))
even[i+1] += C[i];
if((S[i]=='0')^(i%2==1))
odd[i+1] += C[i];
}
//全探索
long ans = Long.MAX_VALUE;
for(int i=1;i<N;i++){
ans = Math.min(ans,odd[N]+even[i]-odd[i]);
ans = Math.min(ans,even[N]+odd[i]-even[i]);
}
//答えの出力
out.println(ans);
out.close();
}
}
E - Paint
問題文はこちら
塗り替えを反映させるのが難しいので、クエリを逆順に処理することで塗り替えを考えないようにし、十分高速に解くことができました。
E.java
final class Main{
private static final boolean autoFlush = false;
private static final SimpleScanner sc = new SimpleScanner(System.in);
private static final SimpleWriter out = new SimpleWriter(System.out,autoFlush);
public static void main(String[] args){
//H、W、Mの受け取り
int H = sc.nextInt();
int W = sc.nextInt();
int M = sc.nextInt();
//各行、列の情報を記録する用
HashMap<Integer,int[]> R = new HashMap<>();
HashMap<Integer,int[]> C = new HashMap<>();
//クエリ先読み
int[][] query = sc.nextInt(M,3);
//逆順に処理
while(M-->0){
int T = query[M][0];
int A = query[M][1];
int X = query[M][2];
if(T==1)
R.putIfAbsent(A,new int[]{X,W-C.size()});
else if(T==2)
C.putIfAbsent(A,new int[]{X,H-R.size()});
}
//各色のマスの数を数える
TreeMap<Integer,Long> map = new TreeMap<>();
long zeroSum = (long)H*W;
for(Entry<Integer,int[]> entry:R.entrySet()){
int color = entry.getValue()[0];
long sum = entry.getValue()[1];
if(sum>0)
map.merge(color,sum,Long::sum);
zeroSum -= sum;
}
for(Entry<Integer,int[]> entry:C.entrySet()){
int color = entry.getValue()[0];
long sum = entry.getValue()[1];
if(sum>0)
map.merge(color,sum,Long::sum);
zeroSum -= sum;
}
//0のマスがあれば追加
if(zeroSum>0)
map.merge(0,zeroSum,Long::sum);
//答えの出力
out.println(map.size());
for(Entry<Integer,Long> entry:map.entrySet())
out.println(entry.getKey()+" "+entry.getValue());
out.close();
}
}
最初$0$で塗られていることを忘れていてペナルティを頂いてしまいました…。
F - SSttrriinngg in StringString
問題文はこちら
答えを直接求めるのは難しいですが、ある非負整数$k$に対して、$g(X,k)$が$f(X,N)$の部分文字列かどうかは高速に求めることができるので、$k$の値を二分探索することで解きました。
F.java
final class Main{
private static final boolean autoFlush = false;
private static final SimpleScanner sc = new SimpleScanner(System.in);
private static final SimpleWriter out = new SimpleWriter(System.out,autoFlush);
public static void main(String[] args){
//N、S、Tの受け取り
long N = sc.nextLong();
char[] S = sc.nextCharArray();
char[] T = sc.nextCharArray();
//各文字が何文字目までに何回出現するかを記録する用
long[][] map = new long[26][S.length+1];
for(int i=0;i<S.length;i++){
for(char c='a';c<='z';c++){
map[c-'a'][i+1] = map[c-'a'][i];
if(S[i]==c)
++map[c-'a'][i+1];
}
}
//二分探索
long a = 0;
long b = Long.MAX_VALUE>>1;
long ans = 0;
Loop:while(a-b<1){
//判定
long c = a+b>>1;
int index = 0;
long now = 0;
for(char cc:T){
if(c<=map[cc-'a'][S.length]-map[cc-'a'][index]){
index = Searcher.upSearch(map[cc-'a'],c+map[cc-'a'][index]);
}
else{
final int i = index;
long r = c-map[cc-'a'][S.length]+map[cc-'a'][index];
long num = Searcher.upSearch(1,N,r,d->d*map[cc-'a'][S.length]);
now += num;
r -= (num-1)*map[cc-'a'][S.length];
index = Searcher.upSearch(map[cc-'a'],r);
}
if(S.length<index){
index = 0;
now++;
}
}
if(now<=N&&now*S.length+index<=S.length*N)
a = (ans=c)+1;
else
b = c-1;
}
//答えの出力
out.println(ans);
out.close();
}
}
実装にかなり手間取って大変でした。
感想
A,B,C:易しい
D:気付けばそうでもない
E:ちょっと実装が面倒
F:かなり大変だった…
って感じでした。
ペナが全体的に多かったので、ちゃんと精度良く実装したいです。