はじめに
オンサイトで参加した第2回緑以下コンテストでなんとか全完できたので、その時のコードを載せようと思います。今回は基本自作ライブラリを使ってないのでそのままで動くと思います。
なお、感じたことをなるべくそのまま書くために普段以上に文体が崩れてるかと思いますが、ご了承ください。
では、見ていきましょう。
A - 緑以下コンテスト
問題文はこちら
普通に三項演算子で良い感じに判定しました。
A.java
import java.util.*;
import java.io.*;
class Main{
private static final BufferedReader br =
new BufferedReader(new InputStreamReader(System.in));
private static final PrintWriter out =
new PrintWriter(System.out);
public static void main(String[] args)throws IOException{
//Nの受け取り
int N = Integer.parseInt(br.readLine());
//Nに合った答えを出力
out.println(N<1200?"green":"difficult");
br.close();
out.close();
}
}
まぁ、灰下位ですかね。
B - 中国剰余定理
問題文はこちら
$A$と$B$が互いに素なので必ず解があって、$a$と$b$の全組み合わせは$1$～$AB$で全部列挙できるので全探索しても$AB \le 9 \times 10^6$より間に合います。
B.java
import java.util.*;
import java.io.*;
class Main{
private static final BufferedReader br =
new BufferedReader(new InputStreamReader(System.in));
private static final PrintWriter out =
new PrintWriter(System.out);
public static void main(String[] args)throws IOException{
//A、B、a、bの受け取り
String[] str = br.readLine().split(" ");
int A = Integer.parseInt(str[0]);
int B = Integer.parseInt(str[1]);
int a = Integer.parseInt(str[2]);
int b = Integer.parseInt(str[3]);
//条件を満たすものを全探索
for(int i=0;;i++)
if(i%A==a&&i%B==b){
out.println(i);
break;
}
br.close();
out.close();
}
}
正直、Bだから大丈夫でしょ！という軽い考えで特に考察することなく全探索しました()。
これもきっと灰下位でしょう。
C - 眩しい数直線
問題文はこちら
制約を見ると割と小さい値なので、各街灯由来の眩しさを$O(B_i)$で反映しても十分間に合います。
C.java
import java.util.*;
import java.io.*;
class Main{
private static final BufferedReader br =
new BufferedReader(new InputStreamReader(System.in));
private static final PrintWriter out =
new PrintWriter(System.out);
public static void main(String[] args)throws IOException{
//N、X、A、Bの受け取り
String[] str = br.readLine().split(" ");
int N = Integer.parseInt(str[0]);
int X = Integer.parseInt(str[1]);
int[][] AB = new int[N][2];
for(int i=0;i<N;i++){
str = br.readLine().split(" ");
AB[i][0] = Integer.parseInt(str[0]);
AB[i][1] = Integer.parseInt(str[1]);
}
//Lの構築
int[] L = new int[X+1];
for(int i=0;i<N;i++){
//眩しさの反映
for(int j=0;j<AB[i][1];j++){
if(j+AB[i][0]<=X)
L[AB[i][0]+j] = Math.max(L[AB[i][0]+j],AB[i][1]-j);
if(AB[i][0]-j>0)
L[AB[i][0]-j] = Math.max(L[AB[i][0]-j],AB[i][1]-j);
}
}
//答えの出力
out.print(L[1]);
for(int i=2;i<=X;i++){
out.print(" ");
out.print(L[i]);
}
out.println();
br.close();
out.close();
}
}
これは…どうなんだろ。灰中位？
D - A_1 < A_2 < ... < A_N
問題文はこちら
辞書順で最小にしたいということで、なるべく前の方は小さい値にしたいなと考えると末尾だけを大きくして総和が$X$になるように調整すれば良いということに気付いたので、それを実装しました。
D.java
import java.util.*;
import java.io.*;
class Main{
private static final BufferedReader br =
new BufferedReader(new InputStreamReader(System.in));
private static final PrintWriter out =
new PrintWriter(System.out);
public static void main(String[] args)throws IOException{
//Tの受け取り
int T = Integer.parseInt(br.readLine());
while(T-->0){
//N、Xの受け取り
String[] str = br.readLine().split(" ");
int N = Integer.parseInt(str[0]);
long X = Long.parseLong(str[1]);
//Xじゃ構築できないなら-1
if(X<(long)N*(N+1)/2)
out.println(-1);
else{
//構築できるなら答えの出力
for(int i=1;i<N;i++){
out.print(i);
out.print(" ");
}
out.println(X-(long)N*(N-1)/2);
}
}
br.close();
out.close();
}
}
これはまぁ、等差数列の和とか発想を使うので灰中位～上位くらいですかね。
E - みんな大好きmod 998
問題文はこちら
$N \le 28$より、階乗はさすがに間に合わなそうな不安がありますが、$K \le \min(8,N)$より、$O(_NC_K)$なら間に合いそうだなと思い、再帰メソッドで全探索しました。
E.java
import java.util.*;
import java.io.*;
class Main{
private static final BufferedReader br =
new BufferedReader(new InputStreamReader(System.in));
private static final PrintWriter out =
new PrintWriter(System.out);
public static void main(String[] args)throws IOException{
//N、K、Aの受け取り
String[] str = br.readLine().split(" ");
int N = Integer.parseInt(str[0]);
int K = Integer.parseInt(str[1]);
str = br.readLine().split(" ");
int[] A = new int[N];
for(int i=0;i<N;i++)
A[i] = Integer.parseInt(str[i]);
//再帰全探索
out.println(dfs(0,0,K,A));
br.close();
out.close();
}
private static long dfs(int now,long sum,int K,int[] A){
//全部選んだのなら判定
if(K==0)
return sum%998244353<=sum%998?1:0;
//選びきれずに末尾に到達したら0
if(now==A.length)
return 0;
//条件を満たす組み合わせの総和を返す
return (dfs(now+1,sum,K,A)+dfs(now+1,sum+A[now],K-1,A))%998;
}
}
最初$998244353$を$99824353$と打ち間違えてしまい、3回もWAを出してしまいました…。
再帰って思ったよりdiff上がりやすい印象なので、茶下位～中位なんですかねぇ。
F - 数字探しゲーム（緑以下コンver.）
問題文はこちら
え、どうすんの？nextPermutationとか間に合わないけど…って思ったんですが、制約を見ると指定されている数字の個数は9個以下だそうで、$10^{18}$以下ということを考えると上位9桁に全て詰めてしまえば$M\le10^9$より、下9桁で辻褄合わせは出来そうだなと思い、それを実装しました。
F.java
import java.util.*;
import java.io.*;
class Main{
private static final BufferedReader br =
new BufferedReader(new InputStreamReader(System.in));
private static final PrintWriter out =
new PrintWriter(System.out);
public static void main(String[] args)throws IOException{
//Tの受け取り
int T = Integer.parseInt(br.readLine());
while(T-->0){
//Mの受け取り
int M = Integer.parseInt(br.readLine());
//上位9桁の構築
StringBuilder N = new StringBuilder();
String[] str = br.readLine().split(" ");
for(int i=0;i<9;i++)
for(int j=0;j<Integer.parseInt(str[i]);j++)
N.append(i+1);
//18桁までかさ増し
while(N.length()<18)
N.append(0);
//上手くMの倍数になるように調整
long num = Long.parseLong(N.toString());
num += (M-num%M)%M;
//答えの出力
out.println(num);
}
br.close();
out.close();
}
}
発想がほんのりARCよりなのかも？ABCで出るなら茶中位くらいな印象。
G - 色ごとのグループ
問題文はこちら
同じ色同士しか結局は移動できないので、同じ色同士の辺のみに注目すれば同じ色同士の頂点が一つの連結成分になるにはあと何本辺が必要ですか？という問題になるので、UnionFindとHashMapで良い感じに管理しながら解きました。
G.java
import java.util.*;
import java.io.*;
class Main{
private static final BufferedReader br =
new BufferedReader(new InputStreamReader(System.in));
private static final PrintWriter out =
new PrintWriter(System.out);
public static void main(String[] args)throws IOException{
//N、M、Cの受け取り
String[] str = br.readLine().split(" ");
int N = Integer.parseInt(str[0]);
int M = Integer.parseInt(str[1]);
int[] C = new int[N];
str = br.readLine().split(" ");
for(int i=0;i<N;i++)
C[i] = Integer.parseInt(str[i]);
//key：色、value：{辺の数,頂点の数}のHashMap
HashMap<Integer,int[]> map = new HashMap<>();
for(int i=0;i<N;i++){
if(map.containsKey(C[i]))
map.get(C[i])[1]++;
else
map.put(C[i],new int[]{0,1});
}
//辺の管理用のUnionFind
UnionFind uf = new UnionFind(N+1);
while(M-->0){
//u、vの受け取り
str = br.readLine().split(" ");
int u = Integer.parseInt(str[0]);
int v = Integer.parseInt(str[1]);
//同じ色同士で、かつ有効な辺なら加算する
if(C[u-1]==C[v-1])
if(uf.unite(u,v))
map.get(C[u-1])[0]++;
}
//必要な辺の数え上げ(木を構築するのに必要な辺の数から求める)
int ans = 0;
for(int[] temp:map.values())
ans += temp[1]-temp[0]-1;
//答えの構築
out.println(ans);
br.close();
out.close();
}
}
final class UnionFind {/*普段のライブラリをご参照ください*/}
急に難易度変わったな…って印象でした。緑下位くらいはありそう。なんかみんな解けてて怖いけど。
H - 衝突予測
問題文はこちら
さほど場合分け多くないな？って思ったので気合い入れてif-elseを書きました。
H.java
import java.util.*;
import java.io.*;
class Main{
private static final BufferedReader br =
new BufferedReader(new InputStreamReader(System.in));
private static final PrintWriter out =
new PrintWriter(System.out);
public static void main(String[] args)throws IOException{
//Tの受け取り
int T = Integer.parseInt(br.readLine());
while(T-->0){
//二頂点と向きの受け取り
String[] str;
str = br.readLine().split(" ");
int x1 = Integer.parseInt(str[0]);
int y1 = Integer.parseInt(str[1]);
char d1 = str[2].charAt(0);
str = br.readLine().split(" ");
int x2 = Integer.parseInt(str[0]);
int y2 = Integer.parseInt(str[1]);
char d2 = str[2].charAt(0);
//場合分け
if(x1==x2){
if(y1<y2)
out.println(d1=='U'&&d2=='D'?"Yes":"No");
else
out.println(d1=='D'&&d2=='U'?"Yes":"No");
}
else if(y1==y2){
if(x1<x2)
out.println(d1=='R'&&d2=='L'?"Yes":"No");
else
out.println(d1=='L'&&d2=='R'?"Yes":"No");
}
else{
if((d1=='U'||d1=='D')&&(d2=='U'||d2=='D'))
out.println("No");
else if((d1=='L'||d1=='R')&&(d2=='L'||d2=='R'))
out.println("No");
else{
int x3 = d1=='U'||d1=='D'?x1:x2;
int y3 = d1=='L'||d1=='R'?y1:y2;
if(x1<x3&&d1=='R'){
if(y2<y3&&d2=='U')
out.println(
x3-x1==y3-y2?"Yes":"No");
else if(y2>y3&&d2=='D')
out.println(
x3-x1==y2-y3?"Yes":"No");
else
out.println("No");
}
else if(x3<x1&&d1=='L'){
if(y2<y3&&d2=='U')
out.println(
x1-x3==y3-y2?"Yes":"No");
else if(y2>y3&&d2=='D')
out.println(
x1-x3==y2-y3?"Yes":"No");
else
out.println("No");
}
else if(y1<y3&&d1=='U'){
if(x2<x3&&d2=='R')
out.println(
x3-x2==y3-y1?"Yes":"No");
else if(x2>x3&&d2=='L')
out.println(
x2-x3==y3-y1?"Yes":"No");
else
out.println("No");
}
else if(y1>y3&&d1=='D'){
if(x2<x3&&d2=='R')
out.println(
x3-x2==y1-y3?"Yes":"No");
else if(x2>x3&&d2=='L')
out.println(
x2-x3==y1-y3?"Yes":"No");
else
out.println("No");
}
else
out.println("No");
}
}
}
br.close();
out.close();
}
}
書いててやっぱり場合分け多いかも…となりましたが引くに引けなかったのでゴリ押しました。
解ける分には解けるでしょうから(ペナとかはありますけど)、茶中位とかでしょうか？
I - はじめてのおつかい
問題文はこちら
町$N-1$と町$N$を通過したかを保持したダイクストラでいけるなと思い、それを実装しました。
I.java
import java.util.*;
import java.io.*;
class Main{
private static final BufferedReader br =
new BufferedReader(new InputStreamReader(System.in));
private static final PrintWriter out =
new PrintWriter(System.out);
public static void main(String[] args)throws IOException{
//N、Mの受け取り
String[] str = br.readLine().split(" ");
int N = Integer.parseInt(str[0]);
int M = Integer.parseInt(str[1]);
//隣接リストの構築
ArrayList<ArrayList<Integer>> list = new ArrayList<>();
for(int i=0;i<=N;i++)
list.add(new ArrayList<>());
while(M-->0){
str = br.readLine().split(" ");
int u = Integer.parseInt(str[0]);
int v = Integer.parseInt(str[1]);
list.get(u).add(v);
}
//ダイクストラ
//N-1に到達しているなら+N、Nに到達しているなら+2Nした値を添え字にしてる
PriorityQueue<int[]> queue = new PriorityQueue<>((a,b)->Integer.compare(a[1],b[1]));
int[] dist = new int[4*N+1];
Arrays.fill(dist,Integer.MAX_VALUE);
dist[1] = 0;
queue.add(new int[]{1,0,0});
while(queue.size()>0){
int[] now = queue.poll();
if(dist[now[0]+now[2]*N]<now[1])
continue;
for(int next:list.get(now[0])){
int nextP = next==N-1?now[2]|1:next==N?now[2]|2:now[2];
if(dist[now[0]+now[2]*N]+1<dist[next+nextP*N]){
dist[next+nextP*N] = dist[now[0]+now[2]*N]+1;
queue.add(new int[]{next,dist[next+nextP*N],nextP});
}
}
}
//どちらにも到達して1に戻ったときのコストの出力
out.println(dist[3*N+1]==Integer.MAX_VALUE?-1:dist[3*N+1]);
br.close();
out.close();
}
}
後からTwitter上でBFSで解けることを知って確かに…になりました。
知ってるかどうかって感じの問題なので、茶上位～緑下位ですかね。
J - 美しい整数列
問題文はこちら
どっかの値を一つに定めれば他の値も$B$を基に定まるので、何か基準を定めておいて、基準からどれくらい離れているかをkeyに、基準からkeyだけずらすことでどれだけコストを節約できるかをvalueにしたHashMapで解きました。
J.java
import java.util.*;
import java.io.*;
class Main{
private static final BufferedReader br =
new BufferedReader(new InputStreamReader(System.in));
private static final PrintWriter out =
new PrintWriter(System.out);
public static void main(String[] args)throws IOException{
//N、M、A、B、Cの受け取り
String[] str = br.readLine().split(" ");
int N = Integer.parseInt(str[0]);
int M = Integer.parseInt(str[1]);
str = br.readLine().split(" ");
int[] A = new int[N];
for(int i=0;i<N;i++)
A[i] = Integer.parseInt(str[i]);
str = br.readLine().split(" ");
int[] B = new int[M];
for(int i=0;i<M;i++)
B[i] = Integer.parseInt(str[i]);
str = br.readLine().split(" ");
int[] C = new int[N];
for(int i=0;i<N;i++)
C[i] = Integer.parseInt(str[i]);
//A_0を固定したときのA_iとのズレをkeyに、その位置を変化するのに必要なコストをvalueにしたHashMap
HashMap<Long,Long> map = new HashMap<>();
long now = A[0];
map.put(0L,(long)C[0]);
for(int i=1;i<N;i++){
now += B[(i-1)%M];
map.merge(now-A[i],(long)C[i],Long::sum);
}
//Cの総和を求めておく
long sumC = 0;
for(long num:C)
sumC += num;
//節約できる最大値を求める
long max = 0;
for(long num:map.values())
max = Math.max(num,max);
//答えの出力
out.println(sumC-max);
br.close();
out.close();
}
}
良い具合の実装問ですね。
う～ん…緑中位、ですかね。あんまり難易度感がピンとこない…。
K - A_1 > A_2 > ... > A_N
問題文はこちら
辞書順最小なので、当然前の方の値はなるべく小さくしたいですが、条件を満たすように構築しようとするとどうしても先頭から大きくするしかないので、$K=X-\frac{N(N+1)}{2}$として$N+K/N,N-1+K/N,\dots,2+K/N,1+K/N$をベースに、$X \mod N$項目までに1を足す感じで調整しました。
K.java
import java.util.*;
import java.io.*;
class Main{
private static final BufferedReader br =
new BufferedReader(new InputStreamReader(System.in));
private static final PrintWriter out =
new PrintWriter(System.out);
public static void main(String[] args)throws IOException{
//Tの受け取り
int T = Integer.parseInt(br.readLine());
while(T-->0){
//N、Xの受け取り
String[] str = br.readLine().split(" ");
long N = Long.parseLong(str[0]);
long X = Long.parseLong(str[1]);
//このXでは構築出来ないなら-1
if(X<N*(N+1)/2)
out.println(-1);
else{
//答えの構築
long sub = X-N*(N+1)/2;
long index = sub%N;
out.print(N+sub/N+(0<index?1:0));
for(int i=1;i<N;i++){
out.print(" ");
out.print((N-i)+sub/N+(i<index?1:0));
}
out.println();
}
}
br.close();
out.close();
}
}
きっとこうだろうなと思いながら実装してみたら通ったので良かったです。
緑下位かな。多分。
L - 列辞書順列列
問題文はこちら
便宜上、$A_i$は全て$1$だけ引いてあるとします。すると、$A$は$M$進数で表記された数字として見ることができます。すると、この問題は「$l_i$桁目から$r_i$桁目までの数字を抜き出したとき、この$M$進数の値を$10$進数で表記した値を$998244353$で割ったあまりは？」という問題になるので、先頭から$i$桁目までを10進数にして$998244353$で割ったあまりを配列に保持しておくことで、$O(1)$でこのクエリに答えることができます。
L.java
import java.util.*;
import java.io.*;
import java.awt.Point;
import java.math.BigInteger;
class Main{
private static final BufferedReader br =
new BufferedReader(new InputStreamReader(System.in));
private static final PrintWriter out =
new PrintWriter(System.out);
public static void main(String[] args)throws IOException{
final int mod = 998244353;
//N、M、Qの受け取り
String[] str = br.readLine().split(" ");
int N = Integer.parseInt(str[0]);
int M = Integer.parseInt(str[1]);
int Q = Integer.parseInt(str[2]);
//AをM進数として受け取る
long[] subA = new long[N+1];
str = br.readLine().split(" ");
for(int i=0;i<N;i++){
subA[i+1] = subA[i]*M%mod+Integer.parseInt(str[i])-1;
if(subA[i+1]>=mod)
subA[i+1] -= mod;
}
while(Q-->0){
//l、rの受け取り
str = br.readLine().split(" ");
int l = Integer.parseInt(str[0]);
int r = Integer.parseInt(str[1]);
//l～rの部分の値を求めて出力
long ans = (subA[r]-subA[l-1]*MathFunction.modPow(M,r-l+1,mod)%mod+1)%mod;
out.println((mod+ans)%mod);
}
br.close();
out.close();
}
}
final class MathFunction {/*普段のライブラリをご参照ください*/}
これは難しめな気がします。水下位に片足突っ込んでそうな気もしますが、緑上位だったりするんですかねぇ…。
感想
A,B:易しめ
C:ちょっとウッってなったけど易しめ
D:気付けば簡単
E:再帰全探索は慣れてるので楽しかった
F:ちょっと面白い
G:ほんのり重め
H:候補はすぐ気付くけど、実装が辛い…
I:緑か…？緑かも…わかんない…
J:割と解けそうなイメージ
K:まぁ、こうしかないかなぁって気付けそうな感じ
L:ちょっと難しめ
って感じでした。
これくらいの難易度が、サクッと考えてサクッと解けるので気持ち良いかも。
主催者の皆様、ありがとうございました。