はじめに
今回はコンテスト中にF以外を解けたので、それを載せようと思います。
なお、僕のライブラリは提出結果をご確認ください。
では、見ていきましょう。
A - Buildings
問題文はこちら
愚直にループを回して探しました。
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、H1の受け取り
int N = sc.nextInt();
int H1 = sc.nextInt();
//全探索
for(int i=2;i<=N;i++){
//Hの受け取り
int H = sc.nextInt();
//答えが見つかれば出力して終了
if(H1<H){
System.out.println(i);
return;
}
}
//見つからなければ-1
out.println(-1);
out.close();
}
}
B - AtCoder Amusement Park
問題文はこちら
最後に$1$回スタートするのは確定なので、順に変数に$A_i$を足していき、何回$K$を超えたかを数えて、$1$足して出力することで答えを求めました。
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){
//N、Kの受け取り
int N = sc.nextInt();
int K = sc.nextInt();
//最後の1回分は先に足しておく
int ans = 1;
//今の客の数
int now = 0;
//順に誘導してみる
while(N-->0){
int A = sc.nextInt();
if(now+A<=K)
now += A;
else{
now = A;
ans++;
}
}
//答えの出力
out.println(ans);
out.close();
}
}
C - Sigma Problem
問題文はこちら
$10^8$で割らずにそのまま総和を求めたときの値から、$10^8$がいくつ引かれているかを二分探索を用いて求めることで答えを求めました。
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、Aの受け取り
int N = sc.nextInt();
long[] A = sc.nextLong(N);
//fが可換であることからソートしても答えは変わらないのでソートする
Arrays.sort(A);
//あまりを求めない解を求めておく
long sum = MathFunction.sum(A);
//数え上げ用変数
long ans = 0;
//各Aiに対する、10^8が引かれる回数分だけ答えから10^8を引きながら答えを構築
for(int i=0;i<N;i++){
sum -= A[i];
ans += sum+A[i]*(N-1-i);
int index = Searcher.downSearch(A,99_999_999-A[i]);
ans -= (N-Math.max(i,index)-1)*100_000_000L;
}
//答えの出力
out.println(ans);
out.close();
}
}
実装に手間取りました…。
D - Another Sigma Problem
問題文はこちら
各$A_i$の寄与について考えてみると、$f(A_j,A_i)$となる組み合わせは$i-1$個、$f(A_i,A_j)$となる組み合わせは$N-i-1$個あることがわかり、$A_j$の桁数を$K$とすると、$f(A_i,A_j)=A_i \times 10^K + A_j$であることから、事前に各$A_i$の桁数を求めておき、$10$の何乗をかけるときが何回あるか、と考えることで高速に解を求めることができます。
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);
//法
private static final int MOD = 998244353;
public static void main(String[] args){
//N、Aの受け取り
int N = sc.nextInt();
long[] A = sc.nextLong(N);
//各Aiの桁数を求める
int[] count = new int[11];
for(long num:A)
count[MathFunction.digit(num)]++;
//先に総和を求める
long sum = MathFunction.sum(A)%MOD;
//数え上げ用変数
long ans = 0;
//各Aiについて繰り上げ分を考慮して答えの数え上げ
for(long num:A){
count[MathFunction.digit(num)]--;
sum -= num;
while(sum<0)
sum += MOD;
ans += sum;
if(MOD<=ans)
ans -= MOD;
for(int i=1;i<11;i++){
num *= 10;
num %= MOD;
ans += num*count[i]%MOD;
if(MOD<=ans)
ans -= MOD;
}
}
//答えの出力
out.println(ans);
out.close();
}
}
E - Yet Another Sigma Problem
問題文はこちら
「自身を表す文字とそれに続く文字のNodeクラスのインスタンスを保持したHashMap」を表すNodeクラスを考えると、$S_i$はこのNodeクラスのインスタンスの連結リストとして表すことができ、各Nodeに個数を保持させることで、最初のNodeからあるNodeまで自身と同じ文字の文字列の個数を記録することができます。全部の文字列を表すNodeインスタンスの生成は$\mathrm{sum}(|S_i|)$回で済み、答えの集計も$\mathrm{sum}(|S_i|)$回で済むので十分高速です。
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);
//上記のNodeクラス
static class Node{
int count;
HashMap<Character,Node> map;
Node(){
count = 0;
map = new HashMap<>();
}
}
public static void main(String[] args){
//N、Sの受け取り
int N = sc.nextInt();
String[] S = sc.next(N);
//最初の文字と、それに対応するNodeクラスのインスタンスを保持するMap
HashMap<Character,Node> map = new HashMap<>();
//各Sの連結リストを構築しながら個数を記録
for(String s:S){
HashMap<Character,Node> now = map;
for(char c:s.toCharArray()){
if(!now.containsKey(c))
now.put(c,new Node());
Node node = now.get(c);
node.count++;
now = node.map;
}
}
//数え上げ用変数
long ans = 0;
//各Sに対する最長共通接頭辞の総和を数え上げ
for(String s:S){
//自分自身の分を引きながら、そのNodeまで一致しているSの個数を数える
HashMap<Character,Node> now = map;
for(char c:s.toCharArray()){
Node node = now.get(c);
ans += --node.count;
now = node.map;
}
}
//答えの出力
out.println(ans);
out.close();
}
}
G - Merchant Takahashi
問題文はこちら
各街について、その街から街$1$に移動したときの所持金の最大値を保持したセグメント木、その街から街$N$に移動したときの所持金の最大値を保持したセグメント木の二つを保持することで、任意の位置へ移動したときの所持金の最大値を高速に求めることができ、これによりDPの要領で各街に最終的にいたときの所持金の最大値を求めることができます。
G.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、Cの受け取り
int N = sc.nextInt();
long C = sc.nextInt();
//i番目の所持金からC*(N-i+1)だけ引いた値を保持したセグ木
SegmentTree<Long> LsegT = new SegmentTree<>(N,Long.MIN_VALUE,true){
public Long function(Long a,Long b){
return Long.max(a,b);
}
};
//i番目の所持金からC*iだけ引いた値を保持したセグ木
SegmentTree<Long> RsegT = new SegmentTree<>(N,Long.MIN_VALUE,true){
public Long function(Long a,Long b){
return Long.max(a,b);
}
};
//街1にいるので初期化
LsegT.update(1,-C*N);
RsegT.update(1,-C);
//Mの受け取り
int M = sc.nextInt();
//クエリ処理
while(M-->0){
//T、Pの受け取り
int T = sc.nextInt();
long P = sc.nextLong();
//左右の街から移動してきたときの所持金の最大値を求める(街Pに留まっている場合も含める)
long max = Math.max(
LsegT.query(1,T)+C*(N-T+1),
RsegT.query(T,N)+C*T);
//所持金の最大値にバイアスをかけた値で更新
LsegT.update(T,Math.max(max+P-C*(N-T+1),LsegT.get(T)));
RsegT.update(T,Math.max(max+P-C*T,RsegT.get(T)));
}
//補正しながら最大値を求める
long ans = 0;
for(int i=1;i<=N;i++)
ans = Math.max(ans,RsegT.get(i)+C*i);
//答えの出力
out.println(ans);
out.close();
}
}
もっと速くこっちに移るべきだったか…。
感想
A,B:易しい
C:手間取った…
D,E:そんなに苦戦はしなかったけど、実装が遅い…
F:わからない…
G:Gにしては易しい？
って感じでした。
6完は純粋に嬉しいですが、F解きたかったなぁ…。