Go to Qiita Advent Calendar 2024 Top
LoginSignup
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@viral_8

ABC328A～Eの解答

Last updated at Posted at 2023-12-06

はじめに

今回もEまで解けたのでそれを載せようと思います。

なお、僕のライブラリは提出結果よりご確認ください。
では、見ていきましょう。

※普段の並行世界の記事はこっち

A - Not Too Hard

問題文はこちら

愚直に$X$以下のものを加算して答えを求めました。

Java
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();
	}
}
C++
A.cpp
#include<iostream>
int main(){
	std::int32_t N,X,S,ans;
	std::cin >> N >> X;
	ans = 0;
	while(N-->0){
		std::cin >> S;
		if(S<=X){
			ans += S;
		}
	}
	std::cout << ans << std::endl;
	return 0;
}
Kotlin
A.kt
fun main(){
	val (N,X) = readLine()!!.split(" ").map{it.toInt()}
	var sum = 0
	for(S in readLine()!!.split(" ").map{it.toInt()}){
		if(S<=X){
			sum += S
		}
	}
	println(sum)
}
C#
A.cs
class Program{
	static void Main(){
		var strs = Console.ReadLine().Split(" ");
		var N = Int32.Parse(strs[0]);
		var X = Int32.Parse(strs[1]);
		var sum = 0;
		foreach(var S in Console.ReadLine().Split(" ")){
			var num = Int32.Parse(S);
			if(num<=X){
				sum += num;
			}
		}
		Console.WriteLine(sum);
	}
}
Python
A.py
N,X = map(int,input().split())
ans = sum(filter(lambda x:x<=X,map(int,input().split())))
print(ans)
Fortran
A.f95
program main
    implicit none
    integer :: N,X,ans,i
    integer, dimension(8) :: S
    
    read(*,*) N,X
    read(*,*) S(1:N)
    
    ans = 0
    do i=1,N
        if(S(i)<=X)then
            ans = ans+S(i)
        end if
    end do
    
    write(*,*) ans
end program main

B - 11/11

問題文はこちら

最大でも$10000$日分の判定で済むので判定メソッドを作って全探索しました。

Java
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++
B.cpp
#include<iostream>
bool check(std::int32_t month,std::int32_t day){
	std::int32_t value = month%10;
	bool is_good = true;
	while(month>0){
		is_good &= month%10==value;
		month /= 10;
	}
	while(day>0){
		is_good &= day%10==value;
		day /= 10;
	}
	return is_good;
}
int main(){
	std::int32_t N,D,ans;
	std::cin >> N;
	ans = 0;
	for(std::int32_t i=1;i<=N;i++){
		std::cin >> D;
		for(std::int32_t j=1;j<=D;j++){
			if(check(i,j)){
				ans++;
			}
		}
	}
	std::cout << ans << std::endl;
	return 0;
}
Kotlin
B.kt
fun main(){
	val N = readLine()!!.toInt()
	val D = readLine()!!.split(" ").map{it.toInt()}
	var ans = 0
	for(i in 1..N){
		for(j in 1..D[i-1]){
			if(check(i,j)){
				ans++
			}
		}
	}
	println(ans)
}
fun check(month:Int,day:Int):Boolean{
	val value = month%10
	var m = month
	while(m>0){
		if(m%10!=value){
			return false;
		}
		m /= 10
	}
	var d = day
	while(d>0){
		if(d%10!=value){
			return false;
		}
		d /= 10
	}
	return true
}
C#
B.cs
class Program{
	static void Main(){
		var N = Int32.Parse(Console.ReadLine());
		var D = Console.ReadLine().Split(" ");
		var ans = 0;
		for(int i=0;i<N;i++){
			var days = Int32.Parse(D[i]);
			for(int j=1;j<=days;j++){
				if(check(i+1,j))
					ans++;
			}
		}
		Console.WriteLine(ans);
	}
	static bool check(int month,int day){
		var value = month%10;
		while(month>0){
			if(month%10!=value){
				return false;
			}
			month /= 10;
		}
		while(day>0){
			if(day%10!=value){
				return false;
			}
			day /= 10;
		}
		return true;
	}
}
Python
B.py
def check(month,day):
	val = month%10
	while month:
		if month%10!=val:
			return False
		month //= 10
	while day:
		if day%10!=val:
			return False
		day //= 10
	return True

N = int(input())
ans = 0
for i,D in enumerate(map(int,input().split())):
	for j in range(D):
		if check(i+1,j+1):
			ans += 1
print(ans)
Fortran
B.f95
program main
    implicit none
    integer :: N,i,j,ans
    integer, dimension(100) :: D
    
    read(*,*) N
    read(*,*) D(1:N)
    
    ans = 0
    do i=1,N
        do j=1,D(i)
            if(check(i,j))then
                ans = ans+1
            end if
        end do
    end do
    
    write(*,*) ans
contains
logical function check(m,d)
    implicit none
    integer :: month,day,m,d,value
    check = .true.
    month = m
    day = d
    value = mod(month,10)
    do
        if(mod(month,10)/=value)then
            check = .false.
            exit
        end if
        month = month/10
        if(month==0)then
            exit
        end if
    end do
    do
        if(mod(day,10)/=value)then
            check = .false.
            exit
        end if
        day = day/10
        if(day==0)then
            exit
        end if
    end do
end function
end program main

C - Consecutive

問題文はこちら

累積和で自分と左隣が同じ文字である個数を数え上げておいて各クエリに答えました。

Java
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();
	}
}
C++
C.cpp
#include<iostream>
#include<string>
int main(){
	std::int32_t N,Q,l,r;
	std::string S;
	std::cin >> N >> Q;
	std::cin >> S;
	std::int32_t sum[300'001];
	sum[1] = 0;
	for(std::int32_t i=1;i<N;i++){
		sum[i+1] = sum[i];
		if(S[i-1]==S[i]){
			sum[i+1]++;
		}
	}
	while(Q-->0){
		std::cin >> l >> r;
		std::cout << sum[r]-sum[l] << '\n';
	}
	std::cout << std::flush;
}
Kotlin
C.kt
fun main(){
	val (N,Q) = readLine()!!.split(" ").map{it.toInt()}
	val S = readLine()!!
	val sum = IntArray(N+1)
	for(i in 1..N-1){
		sum[i+1] = sum[i]
		if(S[i-1]==S[i]){
			sum[i+1]++
		}
	}
	for(i in 1..Q){
		val (l,r) = readLine()!!.split(" ").map{it.toInt()}
		println(sum[r]-sum[l])
	}
}
C#
C.cs
class Program{
	static void Main(){
		var strs = Console.ReadLine().Split(" ");
		var N = Int32.Parse(strs[0]);
		var Q = Int32.Parse(strs[1]);
		var S = Console.ReadLine();
		var 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){
			strs = Console.ReadLine().Split(" ");
			var l = Int32.Parse(strs[0]);
			var r = Int32.Parse(strs[1]);
			Console.WriteLine(sum[r]-sum[l]);
		}
	}
}
Python
C.py
N,Q = map(int,input().split())
S = input()
sum = [0,0]
for i in range(1,N):
	sum.append(sum[-1])
	if S[i-1]==S[i]:
		sum[-1] += 1
while Q:
	l,r = map(int,input().split())
	print(sum[r]-sum[l])
	Q -= 1
Fortran
C.f95
program main
    implicit none
    integer :: N,Q,l,r,i,index
    character(300000) :: S
    integer,dimension(300001) :: sm
    
    read(*,*) N,Q
    read(*,*) S
    
    sm(1) = 0
    do i=2,N
        sm(i) = sm(i-1)
        if(S(i-1:i-1)==S(i:i))then
            sm(i) = sm(i)+1
        end if
    end do
    
    do i=1,Q
        read(*,*) l,r
        write(*,*) sm(r)-sm(l)
    end do
end program main
勝手にこういう問題はDに出るもんだと思ってたのでちょっとだけ驚きました。

D - Take ABC

問題文はこちら

今見ている三文字をそれぞれ変数に保持しておき、ABCでなければ一文字ArrayDequeに入れて、ABCならArrayDequeから取り出してきて、みたいな感じで処理しました。

Java
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();
	}
}
C++
D.cpp
#include<iostream>
#include<string>
int main(){
	std::int32_t N,Q,l,r;
	std::string S;
	std::cin >> N >> Q;
	std::cin >> S;
	std::int32_t sum[300'001];
	sum[1] = 0;
	for(std::int32_t i=1;i<N;i++){
		sum[i+1] = sum[i];
		if(S[i-1]==S[i]){
			sum[i+1]++;
		}
	}
	while(Q-->0){
		std::cin >> l >> r;
		std::cout << sum[r]-sum[l] << '\n';
	}
	std::cout << std::flush;
}
Kotlin
D.kt
fun main(){
	val S = readLine()!!
	var ans = buildString{
		append("?")
		append("?")
		var count = 2
		for(c in S){
			append(c)
			count++
			if(this.substring(count-3)=="ABC"){
				delete(count-3,count)
				count -= 3
			}
		}
	}
	println(ans.substring(2))
}
C#
D.cs
using System.Text;
class Program{
	static void Main(){
		var S = Console.ReadLine();
		var ans = new StringBuilder("??");
		foreach(var c in S){
			ans.Append(c);
			if(ans.ToString(ans.Length-3,3)=="ABC"){
				ans.Remove(ans.Length-3,3);
			}
		}
		Console.WriteLine(ans.ToString(2,ans.Length-2));
	}
}
Python
D.py
S = input()
ans = []
for c in S:
	ans.append(c)
	if ans[-3:]==['A','B','C']:
		ans[-3:] = []
print("".join(ans))
Fortran
D.f95
program main
    implicit none
    integer :: i,index
    character(300000) :: S,ans
    
    read(*,*) S
    
    ans(1:2) = "??"
    index = 2
    do i=1,len_trim(S)
        index = index+1
        ans(index:index) = S(i:i)
        if(ans(index-2:index)=="ABC")then
            index = index-3
        end if
    end do
    write(*,*) ans(3:index)
end program main
思ったより綺麗に書けなくて悲しい…。

E - Modulo MST

問題文はこちら

$M$本の辺から$N-1$本選ぶのは$\binom{M}{N-1}$通りなので、制約上全通りを探索しても間に合います。なので、再帰関数で組み合わせを調べながらUnionFindで全域木を構築できているか確認し、できていれば答えを更新する方針で解きました。

Java
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;
	}
}
C++
E.cpp
#include<iostream>
#include<array>

const std::int32_t deBrujin32[] = {0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9};
std::int32_t numberOfTrailingZeros(std::int64_t x) {
	if(x==0){
		return 32;
	}
	return deBrujin32[((x&-x)*0x077CB531>>27)&0x1f];
}

int main(){
	std::int32_t N,M;
	std::int64_t K,ans;
	std::int64_t path[28][3];
	std::cin >> N >> M;
	std::cin >> K;
	for(std::int32_t i=0;i<M;i++){
		std::cin >> path[i][0] >> path[i][1] >> path[i][2];
	}
	ans = K;
	for(std::int32_t s=(1<<(N-1))-1;s<(1<<M);){
		std::int32_t par[9] = {-1,-1,-1,-1,-1,-1,-1,-1,-1};
		std::int64_t sum = 0;
		bool flag = true;
		for(std::int32_t j=0;j<M;j++){
			if((s&1<<j)>0){
				std::int32_t par1 = (std::int32_t)path[j][0];
				while(par[par1]>0){
					par1 = par[par1];
				}
				std::int32_t par2 = (std::int32_t)path[j][1];
				while(par[par2]>0){
					par2 = par[par2];
				}
				if(par1==par2){
					flag = false;
					break;
				}
				sum += path[j][2];
				par[par2] = par1;
			}
		}
		sum %= K;
		if(flag&&sum<ans){
			ans = sum;
		}
		std::int32_t t = s|(s-1);
		s = (t+1)|((((~t)&(-(~t)))-1)>>(numberOfTrailingZeros(s)+1));
	}
	std::cout << ans << std::endl;
}
Kotlin
E.kt
fun main(){
	val (subN,subM,K) = readLine()!!.split(" ").map{it.toLong()}
	val N = subN.toInt()
	val M = subM.toInt()
	val path: MutableList<LongArray> = mutableListOf()
	for(i in 1..M){
		val (u,v,w) = readLine()!!.split(" ").map{it.toLong()}
		val temp = longArrayOf(u,v,w)
		path.add(temp)
	}
	var ans = K
	var s = 1.shl(N-1)-1
	while(s<1.shl(M)){
		val par = intArrayOf(-1,-1,-1,-1,-1,-1,-1,-1,-1)
		var sum = 0L
		var flag = true
		for(j in 0..M-1){
			if(s.and(1.shl(j))>0){
				var par1 = path[j][0].toInt()
				while(par[par1]>0){
					par1 = par[par1]
				}
				var par2 = path[j][1].toInt()
				while(par[par2]>0){
					par2 = par[par2]
				}
				if(par1==par2){
					flag = false;
					break;
				}
				sum += path[j][2]
				par[par2] = par1
			}
		}
		sum %= K
		if(flag&&sum<ans){
			ans = sum
		}
		val t = s.or(s-1)
		s = (t+1).or((t.inv().and(-t.inv())-1).shr(Integer.numberOfTrailingZeros(s)+1))
	}
	println(ans)
}
C#
E.cs
class Program{
	static int N,M,S;
	static long K;
	static long[,] path;
	static void Main(){
		var strs = Console.ReadLine().Split(" ");
		N = Int32.Parse(strs[0]);
		M = Int32.Parse(strs[1]);
		K = Int64.Parse(strs[2]);
		path = new long[M,3];
		for(int i=0;i<M;i++){
			strs = Console.ReadLine().Split(" ");
			for(int j=0;j<3;j++){
				path[i,j] = Int64.Parse(strs[j]);
			}
		}
		S = 0;
		Console.WriteLine(Dfs(1,0));
	}
	static long Dfs(int now,int bef){
		if(now==N){
			var par = new int[N+1];
			for(int i=0;i<=N;i++){
				par[i] = -1;
			}
			var sum = 0L;
			for(int i=0;i<M;i++){
				if((S&1<<i)>0){
					var par1 = (int)path[i,0];
					var par2 = (int)path[i,1];
					while(par[par1]>=0){
						par1 = par[par1];
					}
					while(par[par2]>=0){
						par2 = par[par2];
					}
					if(par1==par2){
						return K;
					}
					par[par2] = par1;
					sum += path[i,2];
				}
			}
			return sum%K;
		}
		var ans = K;
		for(int i=bef;i<M;i++){
			S ^= 1<<i;
			ans = Math.Min(ans,Dfs(now+1,i+1));
			S ^= 1<<i;
		}
		return ans;
	}
}
Python
E.py
from itertools import combinations

N,M,K = map(int,input().split())
path = []
for i in range(M):
	path.append(list(map(int,input().split())))

ans = K

for pathes in combinations(path,N-1):
	par = [-1]*(N+1)
	s = 0
	for p in pathes:
		par1 = p[0]
		par2 = p[1]
		while 0<=par[par1]:
			par1 = par[par1]
		while 0<=par[par2]:
			par2 = par[par2]
		if par1==par2:
			break
		par[par2] = par1
		s += p[2]
	else:
		ans = min(ans,s%K)

print(ans)
Fortran
E.f95
program main
    implicit none
    integer :: N,M,i,j,t,par1,par2
    integer(8) :: K,ans,s
    integer, dimension(8) :: par
    integer, dimension(28) :: u,v
    integer(8), dimension(28) :: w
    
    read(*,*) N,M,K
    do i=1,M
        read(*,*) u(i),v(i),w(i)
    end do
    
    ans = K
    i = ishft(1,N-1)-1
    do
        par(:) = -1
        s = 0
        do j=1,M
            if(btest(i,j-1))then
                par1 = u(j)
                par2 = v(j)
                do
                    if(par(par1)==-1)then
                        exit
                    end if
                    par1 = par(par1)
                end do
                do
                    if(par(par2)==-1)then
                        exit
                    end if
                    par2 = par(par2)
                end do
                if(par1==par2)then
                    s = K-1
                    exit
                end if
                par(par2) = par1
                s = s+w(j)
            end if
        end do
        ans = min(ans,mod(s,K))
        t = ior(i,i-1)
        i = ior(t+1,ishft(iand(not(t),-not(t))-1,-number_of_trailing_zeros(i)-1))
        if(ishft(1,M)<=i)then
            exit
        end if
    end do
    
    write(*,*) ans
contains
integer function number_of_trailing_zeros(num)
    implicit none
    integer :: num
    do number_of_trailing_zeros=0,31
        if(btest(num,number_of_trailing_zeros))then
            exit
        end if
    end do
end function
end program main

感想

A,B:易しい
C:Cにしては難しめ？(けどDかと言われると…むむむ…)
D:比較的易しめ
E:全探索できるのさえ気づければサクッとできる
って感じでした。

なかなか青パフォが出せず水に戻ってしまいそうでずっとドキドキしております。

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?