はじめに
今回はコンテスト中にDまでとF、コンテスト後にEを解いたのでそれを載せようと思います。
では、見ていきましょう。
A - Pairing
問題文はこちら
楽かなと思ってHashSetでAを管理することで解を求めました。
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){
HashSet<Integer> set = new HashSet<>();
int ans = 0;
for(int i=0;i<4;i++){
int A = sc.nextInt();
if(set.contains(A)){
ans++;
set.remove(A);
}
else
set.add(A);
}
out.println(ans);
out.close();
}
}
B - Garbage Collection
問題文はこちら
要約すると$q_{t_i}$の倍数+$r_{t_i}$で、$d_i$以上で最も小さいものを求めれば良いらしいので、それを求めました。
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){
int N = sc.nextInt();
int[][] list = sc.nextInt(N,2);
int Q = sc.nextInt();
while(Q-->0){
int t = sc.nextInt()-1;
int d = sc.nextInt();
int q = list[t][0];
int r = list[t][1];
int ans = (d-r+q-1)/q*q+r;
out.println(ans);
}
out.close();
}
}
C - Repeating
問題文はこちら
要は直前にその値が出現した場所さえ管理できていれば答えが求まるので、HashMapで管理して解を求めました。
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){
int N = sc.nextInt();
int[] B = new int[N];
HashMap<Integer,Integer> map = new HashMap<>();
for(int i=0;i<N;i++){
int A = sc.nextInt();
B[i] = map.getOrDefault(A,-1);
map.put(A,i+1);
}
out.println(B);
out.close();
}
}
D - Count Simple Paths
問題文はこちら
入力例3を見るとそんなに通り数が多くなさそうなので、愚直にDFSで解を数え上げました。
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){
int H = sc.nextInt();
int W = sc.nextInt();
int K = sc.nextInt();
char[][] S = sc.nextCharArray(H);
int ans = 0;
boolean[][] checked = new boolean[H][W];
for(int i=0;i<H;i++){
for(int j=0;j<W;j++){
if(S[i][j]=='.'){
ans += dfs(i,j,K,S,checked);
}
}
}
out.println(ans);
out.close();
}
private static final int[] dx = {1,-1,0,0};
private static final int[] dy = {0,0,1,-1};
private static int dfs(int x,int y,int K,char[][] S,boolean[][] checked){
if(K==0)
return 1;
int ans = 0;
checked[x][y] = true;
for(int i=0;i<4;i++){
int nx = x+dx[i];
int ny = y+dy[i];
if(MathFunction.rangeCheck(nx,0,checked.length)&&
MathFunction.rangeCheck(ny,0,checked[x].length)&&
!checked[nx][ny]&&S[nx][ny]=='.'){
ans += dfs(nx,ny,K-1,S,checked);
}
}
checked[x][y] = false;
return ans;
}
}
E - Mod Sigma Problem
問題文はこちら
公式解説の通りです。
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){
int N = sc.nextInt();
int M = sc.nextInt();
int[] A = sc.nextInt(N);
int[] sum = new int[N+1];
for(int i=0;i<N;i++){
sum[i+1] = sum[i]+A[i]%M;
if(M<=sum[i+1])
sum[i+1] -= M;
}
long ssum = 0;
long ans = 0;
BIT bit = new BIT(M);
for(int i=1;i<=N;i++){
ans += (long)sum[i]*i;
ans -= ssum;
ans += M*(bit.sum(M)-bit.sum(sum[i]+1));
ssum += sum[i];
bit.add(sum[i]+1,1);
}
out.println(ans);
out.close();
}
}
気づけないです…。
F - Add One Edge 2
問題文はこちら
次数が$3$という制約があるので、次数$3$の頂点同士で連結している箇所を一つの頂点とみなし、その頂点と直接連結している次数$2$の頂点同士に辺を張ると本問題の条件に見合う閉路を生成できます。
したがって、UnionFindで次数$3$の頂点をつなぎ合わせ、その連結成分の代表をkey、連結成分と直接連結している次数$2$の頂点の個数をvalueとしたHashMapを構築し、辺の張り方の組み合わせは連結成分毎に$v=\mathrm{value}$として$\frac{1}{2}v(v-1)$通りあるのでこれを数え上げました。
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){
int N = sc.nextInt();
int[][] graph = sc.nextGraph(N,N-1);
UnionFind uf = new UnionFind(N+1);
for(int i=1;i<=N;i++){
if(graph[i].length==3){
for(int next:graph[i]){
if(graph[next].length==3){
uf.unite(i,next);
}
}
}
}
HashMap<Integer,Integer> map = new HashMap<>();
for(int i=1;i<=N;i++){
if(graph[i].length==2){
for(int next:graph[i]){
if(graph[next].length==3){
map.merge(uf.root(next),1,Integer::sum);
}
}
}
}
long ans = 0;
for(int val:map.values()){
ans += (long)val*(val-1)/2;
}
out.println(ans);
out.close();
}
}
感想
A,B,C:易しい
D:計算量がちょっと不安だった
E:キツイ…
F:最後間に合ってよかった
って感じでした。
もう少し早くFに移れば軽傷で済んだんですが…。