はじめに
今回はコンテスト中にDまで、コンテスト後にEまで解いたのでそれを載せようと思います。
なお、僕のライブラリは提出結果よりご確認ください。
では、見ていきましょう。
A - To Be Saikyo
問題文はこちら
$P_2$以降の最大値を求めて$P_1$と比較して答えを求めました。
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、Pの受け取り
int N = sc.nextInt();
int[] P = sc.nextInt(N);
//P[1]以降の最大値を求める
int max = 0;
for(int i=1;i<N;i++)
max = Math.max(max,P[i]);
//P[0]以上があるならmax+1に、無ければそのまま
out.println(P[0]<=max?max-P[0]+1:0);
out.close();
}
}
今思えば$P_2$以降に1を足しての最大値を求めても良かったかもしれません。
B - Who is Saikyo?
問題文はこちら
$A_i$と$B_i$について頂点$A_i$から頂点$B_i$への有向辺を張っていると考えると、これらの辺をトポロジカルソートして、ある数列$P$を、$P_{B_i}:=P_{A_i}+1$として順に更新し、$P_i=0$なる$i$が一つだけなら$i$が答え、二つ以上あるなら一意に定まらないので$-1$と考えて実装しました。
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の受け取り
int N = sc.nextInt();
int M = sc.nextInt();
//隣接リストの構築
ArrayList<ArrayList<Integer>> list = new ArrayList<>();
for(int i=0;i<=N;i++)
list.add(new ArrayList<>());
while(M-->0)
list.get(sc.nextInt()).add(sc.nextInt());
//トポロジカルソート
int[][] path = ArrayFunction.topologicalSort(list);
//入次数0からの距離の記録
int[] p = new int[N+1];
for(int[] pa:path)
p[pa[1]] = p[pa[0]]+1;
//答えを探す
int ans = -1;
for(int i=1;i<=N;i++){
if(p[i]==0){
if(ans>-1){
System.out.println(-1); //複数候補が見つかってしまったら-1
return;
}
ans = i;
}
}
//答えの出力
out.println(ans);
out.close();
}
}
Xで見かけましたが、$B$に出現していないものを見るだけで良かったですね…。
import java.util.Scanner;
class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
//N、Mの受け取り
int N = sc.nextInt();
int M = sc.nextInt();
//Bに出現したかを記録する配列
boolean[] isWeak = new boolean[N+1];
//Nで最強候補の人数を記録する
//A、Bの受け取り
while(M-->0){
int A = sc.nextInt();
int B = sc.nextInt();
if(!isWeak[B])
N--; //初めての出現ならNを一つ減らす
isWeak[B] = true;
}
//一人しか候補がいないならその人を探して出力
if(N==1){
for(int i=1;i<isWeak.length;i++)
if(!isWeak[i])
System.out.println(i);
}
else
System.out.println(-1); //複数人いれば-1
}
}
めちゃくちゃ時間使ってしまった上にペナ出したのほんと良くない…。
C - Approximate Equalization 2
問題文はこちら
操作前の$A$と操作後の$A'$について、総和が変わらないことを考えると、$A$の平均付近に各要素を寄せることが最適と考え、平均より大きいものの操作回数と平均より小さいものの操作回数でより操作が必要な方を求めました。これは、回数が少ない方に合わせると多い方の操作が完了せず、多い方に合わせれば少ない方は平均$\pm1$で上手いことやりくりできるかなと思ったからです。
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);
//平均の計算
long sum = 0;
for(int a:A)
sum += a;
long mid = sum/N;
//平均より小さい項の操作回数と平均より大きい項の操作回数を求める
long minSum = 0;
long maxSum = 0;
for(int i=0;i<N;i++){
if(A[i]<=mid)
minSum += mid-A[i];
else
maxSum += A[i]-mid-1;
}
//それぞれでより操作が必要な方を出力
out.println(Math.max(minSum,maxSum));
out.close();
}
}
気付くまで凄い時間を使ってしまった…。
D - Odd or Even
問題文はこちら
$1$から$K+1$までを見たとき、これらから$1$個だけ除いた組み合わせを全て質問してみます。もしこの中に$1$が奇数個あれば、$0$と返ってきた時に除いた項は$1$、$1$と返ってきた時に除いた項は$0$とわかります。偶数個なら返ってきた値と同じであると推測できます。ところで、$K+1$は偶数なので、$1$から$K+1$までの$1$の数と質問から返ってくる$0$の数の偶奇は一致します。これを利用して、$1$から$K+1$までの値を$K+1$回の質問で決定します。あとは、$K+2$以降を、$1$から$K-1$までと合わせて質問することで$K+2$以降も特定することが出来ます。
final class Main {
private static final boolean autoFlush = true;
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の受け取り
int N = sc.nextInt();
int K = sc.nextInt();
//ゼロかどうかを記録する配列
boolean[] zero = new boolean[N+1];
//0の個数を数えておく
int sum = 0;
//1～K+1の中から選ぶ全通りを質問する
for(int i=1;i<=K+1;i++){
StringBuilder sb = new StringBuilder();
sb.append("?");
for(int j=1;j<=K+1;j++){
if(i!=j){
sb.append(" ");
sb.append(j);
}
}
out.println(sb.toString());
zero[i] = sc.nextInt()==0;
if(zero[i])
sum++;
}
//奇数個あったら01を反転する
if(sum%2==1)
for(int i=1;i<=K+1;i++)
zero[i] = !zero[i];
//1～K-1での総和と、質問用のStringBuilderの構築
int count = 0;
StringBuilder sb = new StringBuilder();
sb.append("?");
for(int i=1;i<K;i++){
sb.append(" ");
sb.append(i);
count += zero[i]?0:1;
}
//K+2以降を特定する
for(int i=K+2;i<=N;i++){
out.println(sb.toString()+" "+i);
zero[i] = count%2==sc.nextInt();
}
//答えの出力
out.print("!");
for(int i=1;i<=N;i++){
out.print(" ");
out.print(zero[i]?0:1);
}
out.println();
out.close();
}
}
気付いたのはすぐでしたが、実装に時間をかけてしまいました…。
E - Duplicate
問題文はこちら
実際に何個か自分で作って実験すると、操作を行なう毎に二番目以降の数字$k$は自分の前の数字を$k-1$個増殖させるとわかるので、後ろから、$i+1$文字目を消すまでに必要な操作を求めておけば、$i$文字目を消すまでに必要な回数が求まります。
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();
//逆にしてSを受け取る
String S = new StringBuilder(sc.next()).reverse().toString();
//必要な操作回数
long ans = 0;
final int mod = 998244353;
//後ろから見ていく
for(int i=0;i<N-1;i++){
//2以上の数字が隣接していたら終わらないので-1
if(S.charAt(i)>'1'){
if(S.charAt(i+1)>'1'){
System.out.println(-1);
return;
}
}
//これまでに必要な操作回数+1回だけ数字が増殖するのでそれを求めて更新
ans = (ans+1)*(S.charAt(i)-'0');
ans %= mod;
}
//答えの出力
out.println(ans);
out.close();
}
}
う～ん…実験してそれっぽい法則には気付いたんですが、実装まで至りませんでした…。
感想
A:実装ミスによるロスが大きかった…。
B:ライブラリ作っておきながら渡すものが何か忘れててペナ出しちゃった…。
C:最初何も思いつかなくて焦った。
D:直前で焦ったので割とこっちの方が簡単に感じた。実装遅かったけど…。
E:実装、間に合いませんが…。
って感じでした。
いやぁ…時間かけすぎてEの実装に至れなかったのが非常に悔しいです…いや時間あっても解けなかったかもしれませんが…。