はじめに
今回はコンテスト中にEまで、コンテスト後にFを解いたのでFまで載せようと思います。
なお、僕のライブラリは提出結果よりご確認ください。
では、見ていきましょう。
A - Sanitize Hands
問題文はこちら
$H$を順に受け取って、$M$が$0$を下回ってしまうタイミングを探しました。
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、Mの受け取り
int N = sc.nextInt();
int M = sc.nextInt();
//Mが0を下回るときを調べる
for(int i=0;i<N;i++){
int H = sc.nextInt();
if(M<H){
System.out.println(i);
return;
}
M -= H;
}
//ループを抜けた=全員消毒できたのでN
out.println(N);
out.close();
}
}
B - Uppercase and Lowercase
問題文はこちら
先頭から愚直に小文字と大文字の個数を調べて問題文の通りに変換しました。
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){
//Sの受け取り
String S = sc.next();
//小文字の個数-大文字の個数を求める
int count = 0;
for(char c:S.toCharArray())
count += c<'a'?1:-1;
//条件に応じて変換
out.println(count<0?S.toLowerCase():S.toUpperCase());
out.close();
}
}
C - Sierpinski carpet
問題文はこちら
各レベルのカーペットは再帰的に定義されているので、どの位置がレベルいくつになるかを再帰メソッドを定義することで解きました。
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の受け取り
int N = sc.nextInt();
//再帰で答えを構築
char[][] ans = new char[(int)MathFunction.pow(3,N)][(int)MathFunction.pow(3,N)];
fill(ans,0,0,N);
//答えの出力
out.println(ans);
out.close();
}
//再帰メソッド(構築用配列、開始座標、レベルを引数に)
private static void fill(char[][] ans,int x,int y,int N){
//レベル0は1マスだけなのでその場で構築
if(N==0){
ans[x][y] = '#';
return;
}
//レベル1以上は再帰しながら構築
else{
int subN = (int)MathFunction.pow(3,N-1);
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
if(i==1&&j==1){
for(int k=0;k<subN;k++){
for(int l=0;l<subN;l++){
ans[x+subN+k][y+subN+l] = '.';
}
}
}
else{
fill(ans,x+subN*i,y+subN*j,N-1);
}
}
}
}
}
}
D - 88888888
問題文はこちら
$N$の桁数を$S$とすると、$V_N=\sum_{i=1}^N{N \times (10^S)^{i-1}}$となることから、
$$V_N=\sum_{i=1}^N{N \times (10^S)^{i-1}}=N \times \sum_{i=1}^N{(10^S)^{i-1}}=N \times \frac{(10^S)^N-1}{10^S-1}$$
と変形することができます。法が素数なので、容易に逆元が求まることから、これを実装することで問題を解きました。
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の受け取り
long N = sc.nextLong();
//上記の式の値を構築(rは10^Sに該当)
long ans = N%MOD;
long r = MathFunction.modPow(10,MathFunction.digit(N),MOD);
ans *= MathFunction.modPow(r,N,MOD)-1;
ans %= MOD;
ans *= MathFunction.modPow((MOD+r-1)%MOD,MOD-2,MOD);
ans %= MOD;
//答えの出力
out.println((ans%MOD+MOD)%MOD);
out.close();
}
}
式変形にめちゃくちゃ手こずりました…。
E - Reachability in Functional Graph
問題文はこちら
AtCoderLibraryForJavaのSCCを使って解きました。
強連結成分毎に遷移しながら、順に移動できる頂点の組を数え上げることで高速に解くことができます。
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の受け取り
int N = sc.nextInt();
//隣接リストとSCCを同時構築
ArrayList<ArrayList<Integer>> list = new ArrayList<>();
for(int i=0;i<N;i++)
list.add(new ArrayList<>());
SCC scc = new SCC(N);
for(int i=0;i<N;i++){
int a = sc.nextInt()-1;
list.get(a).add(i);
scc.addEdge(a,i);
}
//強連結成分ごとに遷移するDPで数え上げ
int[][] graph = scc.build();
long[] dp = new long[graph.length];
long ans = 0;
for(int i=0;i<graph.length;i++){
HashSet<Integer> set = new HashSet<>();
for(int now:graph[i])
for(int next:list.get(now))
set.add(scc.id(next));
set.remove(i);
long sum = dp[i]+graph[i].length;
for(int next:set)
dp[next] += sum;
ans += dp[i]+(long)graph[i].length*graph[i].length;
}
//答えの出力
out.println(ans);
out.close();
}
}
SCCの実装は上記のリンク先よりご確認ください。
F - Two Sequence Queries
問題文はこちら
公式解説の通りです。
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{
long A,B,sum,length;
public Node(long a,long b,long s,long l){
A = a;
B = b;
sum = s;
length = l;
}
}
static class SubNode{
long xA,xB;
public SubNode(long a,long b){
xA = a;
xB = b;
}
}
public static void main(String[] args){
//N、Q、A、Bの受け取り
int N = sc.nextInt();
int Q = sc.nextInt();
int[] A = sc.nextInt(N);
int[] B = sc.nextInt(N);
//遅延セグ木構築
Node[] node = new Node[N];
for(int i=0;i<N;i++)
node[i] = new Node(A[i],B[i],(long)A[i]*B[i]%998244353,1);
LazySegmentTree<Node,SubNode> lSegT = new LazySegmentTree<>(node,new Node(0,0,0,0),new SubNode(0,0),true){
final int MOD = 998244353;
public Node function(Node a,Node b){
return new Node(
(a.A+b.A)%MOD,
(a.B+b.B)%MOD,
(a.sum+b.sum)%MOD,
a.length+b.length
);
}
public Node mapping(Node a,SubNode f){
long A = (a.A+f.xA*a.length)%MOD;
long B = (a.B+f.xB*a.length)%MOD;
long sum = (a.sum+A*f.xB+a.B*f.xA)%MOD;
return new Node(A,B,sum,a.length);
}
public SubNode composition(SubNode fa,SubNode fb){
return new SubNode(
(fa.xA+fb.xA)%MOD,
(fa.xB+fb.xB)%MOD
);
}
};
//クエリ処理
while(Q-->0){
int t = sc.nextInt();
if(t==1){
int l = sc.nextInt();
int r = sc.nextInt();
int x = sc.nextInt();
lSegT.apply(l,r+1,new SubNode(x,0));
}
if(t==2){
int l = sc.nextInt();
int r = sc.nextInt();
int x = sc.nextInt();
lSegT.apply(l,r+1,new SubNode(0,x));
}
if(t==3){
int l = sc.nextInt();
int r = sc.nextInt();
out.println(lSegT.query(l,r+1).sum);
}
}
out.close();
}
}
遅延セグ木でいけそう、ということしか気づけなかった…。
感想
A,B:易しい
C:一瞬ウッてなった
D:かなり時間をかけてしまった…
E:SCCでいけそうな気はしたが、ACL4Javaを取ってくるのが面倒で横着して時間をかけた…
F:何載せれば良いかがわからなかった…経験不足…
って感じでした。
うぅ…レート下がり続きで辛い…。