はじめに
今回もFまで解けたのでそれを載せようと思います。
なお、僕のライブラリは提出結果よりご確認ください。
では、見ていきましょう。
A - Not Too Hard
問題文はこちら
愚直に$X$以下のものを加算して答えを求めました。
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、Xの受け取り
int N = sc.nextInt();
int X = sc.nextInt();
//総和を求める
int ans = 0;
while(N-->0){
int S = sc.nextInt();
if(S<=X){
ans += S;
}
}
//答えの出力
out.println(ans);
out.close();
}
}
B - 11/11
問題文はこちら
最大でも$10000$日分の判定で済むので判定メソッドを作って全探索しました。
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、Dの受け取り
int N = sc.nextInt();
int[] D = sc.nextInt(N);
//各日付が条件を満たすか調べながら数え上げ
int ans = 0;
for(int i=1;i<=N;i++){
for(int j=1;j<=D[i-1];j++){
if(check(i,j))
ans++;
}
}
//答えの出力
out.println(ans);
out.close();
}
//ゾロ目判定メソッド
private static boolean check(int a,int b){
char c = String.valueOf(a).charAt(0);
return String.valueOf(a).replace(""+c,"").equals("")&&String.valueOf(b).replace(""+c,"").equals("");
}
}
C - Consecutive
問題文はこちら
累積和で自分と左隣が同じ文字である個数を数え上げておいて各クエリに答えました。
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、Q、Sの受け取り
int N = sc.nextInt();
int Q = sc.nextInt();
char[] S = sc.nextCharArray();
//累積和の構築
int[] sum = new int[N+1];
for(int i=1;i<N;i++){
sum[i+1] = sum[i];
if(S[i-1]==S[i])
sum[i+1]++;
}
//各質問に答える
while(Q-->0){
int l = sc.nextInt();
int r = sc.nextInt();
out.println(sum[r]-sum[l]);
}
out.close();
}
}
勝手にこういう問題はDに出るもんだと思ってたのでちょっとだけ驚きました。
D - Take ABC
問題文はこちら
今見ている三文字をそれぞれ変数に保持しておき、ABCでなければ一文字ArrayDequeに入れて、ABCならArrayDequeから取り出してきて、みたいな感じで処理しました。
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 ) {
//とりあえずSをDequeに
ArrayDeque<Character> deq = new ArrayDeque<>();
for(char c:sc.nextCharArray())
deq.add(c);
//ダミーの文字
char c1 = '?';
char c2 = '?';
//答えを格納するDeque
ArrayDeque<Character> ans = new ArrayDeque<>();
while(deq.size()>0){
char c3 = deq.pollFirst();
//今見ている三文字がABCなら消してansから2文字取り出しておく
if(c1=='A'&&c2=='B'&&c3=='C'){
c2 = ans.pollLast();
c1 = ans.pollLast();
}
//違うなら次の区間を確認するために1文字ずらす
else{
ans.add(c1);
c1 = c2;
c2 = c3;
}
}
//最後に見ていた2文字も追加
ans.add(c1);
ans.add(c2);
StringBuilder answer = new StringBuilder();
//ダミーの文字を削除
ans.removeFirst();
ans.removeFirst();
//答えをStringに変換して出力
for(char c:ans)
answer.append(c);
out.println(answer.toString());
out.close();
}
}
思ったより綺麗に書けなくて悲しい…。
E - Modulo MST
問題文はこちら
$M$本の辺から$N-1$本選ぶのは$\binom{M}{N-1}$通りなので、制約上全通りを探索しても間に合います。なので、再帰関数で組み合わせを調べながらUnionFindで全域木を構築できているか確認し、できていれば答えを更新する方針で解きました。
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 ) {
//N、M、K、辺の受け取り
int N = sc.nextInt();
int M = sc.nextInt();
long K = sc.nextLong();
long[][] path = sc.nextLong(M,3);
//再帰全探索
out.println(dfs(1,N,-1,path,K,new ArrayList<>()));
out.close();
}
//再帰用メソッド
private static long dfs(int now,int N,int bef,long[][] path,long K,ArrayList<Integer> list){
//N-1本辺を選んだなら全域木か判定してコストを返す
if(now==N){
UnionFind uf = new UnionFind(N+1);
long sum = 0;
for(int index:list){
uf.unite((int)path[index][0],(int)path[index][1]);
sum += path[index][2];
}
return uf.size(1)==N?sum%K:K-1;
}
//重複が出ないように選びながら再帰
long ans = K-1;
for(int i=bef+1;i<path.length;i++){
list.add(i);
ans = Math.min(ans,dfs(now+1,N,i,path,K,list));
list.remove(list.size()-1);
}
return ans;
}
}
ところで$M$本からいくつか選ぶ($0$本も含む)通り数は$2^M$通りですが、bit全探索の要領で探索してもなんとか間に合います。
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 ) {
//N、M、K、辺の受け取り
int N = sc.nextInt();
int M = sc.nextInt();
long K = sc.nextLong();
long[][] path = sc.nextLong(M,3);
//bit全探索
long ans = Long.MAX_VALUE;
Loop:for(int i=0;i<1<<M;i++){
//N-1個bitが立っているならそれに対応する辺を選んで木の構築
if(Integer.bitCount(i)+1==N){
UnionFind uf = new UnionFind(N+1);
long sum = 0;
for(int j=0;j<M;j++)
if((i&1<<j)>0)
if(uf.unite((int)path[j][0],(int)path[j][1]))
sum += path[j][2];
else
continue Loop; //条件を満たさないならさっさと抜ける
//条件を満たすなら答えの更新
ans = Math.min(ans,sum%K);
}
}
//答えの出力
out.println(ans);
out.close();
}
}
$0$以上$2^n$未満の整数であって丁度$k$個のbitが立っているようなものは$O({}_n C_k)$で求められるのでこの手法を使えば上記の実装は高速化ができます(ABC264-C Matrix Reducingのcirno3153さんのユーザー解説に載っています)。
F - Good Set Query
問題文はこちら
公式解説にある重み付きUnionFindみたいな感じで解きました。
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 );
//親と、親との差分を記録するクラス
static class Node{
int par;
long sub;
public Node(int p,long s){
par= p;
sub = s;
}
}
public static void main ( String[] args ) {
//N、Qの受け取り
int N = sc.nextInt();
int Q = sc.nextInt();
//各頂点の情報を作る
Node[] node = new Node[N+1];
for(int i=0;i<=N;i++)
node[i] = new Node(-1,0);
//答え用List
ArrayList<Integer> ans = new ArrayList<>();
//クエリを受け取る
for(int i=1;i<=Q;i++){
int a = sc.nextInt();
int b = sc.nextInt();
int d = sc.nextInt();
//矛盾が生まれるならスルー、無いならadd
if(!check(a,b,d,node)){
continue;
}
else
ans.add(i);
}
//答えの出力
out.println(ans);
out.close();
}
//UnionFindのuniteに相当するメソッド
private static boolean check(int x,int y,long d,Node[] node) {
//親と自身の値を受け取る
long[] dataX = getValue(node,x);
long[] dataY = getValue(node,y);
//同じ集合にいるならちゃんと条件を満たしているか返す
if(dataX[1]==dataY[1]){
return dataX[0]-dataY[0]==d;
}
//条件を満たすようにNodeの情報を更新
node[(int)dataY[1]].par = (int)dataX[1];
node[(int)dataY[1]].sub = (dataX[0]-dataY[0])-d;
return true;
}
//UnionFindのrootメソッドなどに相当するメソッド
private static long[] getValue(Node[] node,int index){
if(node[index].par==-1)
return new long[]{0,index};
else{
long[] data = getValue(node,node[index].par);
node[index].par = (int)data[1];
node[index].sub += data[0];
return new long[]{node[index].sub,data[1]};
}
}
}
何をとち狂ったのかcheckメソッドの差分の更新の式でやたらミスりまくってものすごい時間をかけてしまいました…。
感想
A,B:易しい
C:Cにしては難しめ？(けどDかと言われると…むむむ…)
D:比較的易しめ
E:全探索できるのさえ気づければサクッとできる
F:みんな解いててびっくりした…
って感じでした。
なかなか青パフォが出せず水に戻ってしまいそうでずっとドキドキしております。