はじめに
今回はコンテスト中にDまで、コンテスト後にFまで解いたのでそれを載せようと思います。
では、見ていきましょう。
A - Humidifier 1
問題文はこちら
追加したタイミングで前回からどれくらいの時間が経っているかを調べることで増減を求めることができます。
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){
int N = sc.nextInt();
int now = 0;
int bef = 0;
while(N-->0){
int T = sc.nextInt();
int V = sc.nextInt();
now -= Math.min(now,T-bef);
now += V;
bef = T;
}
out.println(now);
out.close();
}
}
B - Humidifier 2
問題文はこちら
そんなに通り数が多くないので全マス対全マスで実際に置いてみて加湿される床マスを数え上げてみました。
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 H = sc.nextInt();
int W = sc.nextInt();
int D = sc.nextInt();
char[][] S = sc.nextCharArray(H);
int ans = 0;
for(int i=0;i<H;i++){
for(int j=0;j<W;j++){
if(S[i][j]=='.'){
for(int k=0;k<H;k++){
for(int l=0;l<W;l++){
if((i!=k||j!=l)&&S[k][l]=='.'){
int count = 0;
for(int m=0;m<H;m++){
for(int n=0;n<W;n++){
int dist1 = Math.abs(i-m)+Math.abs(j-n);
int dist2 = Math.abs(k-m)+Math.abs(l-n);
int d = Math.min(dist1,dist2);
if(d<=D&&S[m][n]=='.')
count++;
}
}
ans = Math.max(ans,count);
}
}
}
}
}
}
out.println(ans);
out.close();
}
}
C - Humidifier 3
問題文はこちら
加湿器全部を始点としたBFSで答えを求めました。
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);
private static final int[] dx = {1,-1,0,0};
private static final int[] dy = {0,0,1,-1};
public static void main(String[] args){
int H = sc.nextInt();
int W = sc.nextInt();
int D = sc.nextInt();
char[][] S = sc.nextCharArray(H);
ArrayDeque<Point> deq = new ArrayDeque<>();
for(int i=0;i<H;i++){
for(int j=0;j<W;j++){
if(S[i][j]=='H')
deq.add(new Point(i,j));
}
}
int[][] dist = new int[H][W];
for(int[] temp:dist)
Arrays.fill(temp,D+1);
for(Point p:deq)
dist[p.x][p.y] = 0;
while(deq.size()>0){
Point now = deq.pollFirst();
int x = now.x;
int y = now.y;
for(int i=0;i<4;i++){
int nx = x+dx[i];
int ny = y+dy[i];
if(0<=nx&&nx<H&&0<=ny&&ny<W&&S[nx][ny]!='#'){
if(dist[x][y]+1<dist[nx][ny]){
dist[nx][ny] = dist[x][y]+1;
deq.add(new Point(nx,ny));
}
}
}
}
int ans = 0;
for(int[] temp:dist)
for(int d:temp)
if(d<=D)
ans++;
out.println(ans);
out.close();
}
}
D - 9 Divisors
問題文はこちら
$2$以上の整数$K$を素因数分解した形$\prod_i p_i^{e_i}$($p$は素数)の$e_i$について、$K$の約数の個数は$\prod_i (e_i+1)$で表せます。したがって、約数の個数が$9$個となるような状態は素因数分解したときに「素数の種類数が$2$個かつそれぞれの指数部が$2$である」ときと「素数の種類数が$1$個かつ指数部が$8$である」ときの$2$通りしか存在しないことがわかるかと思います。
$N$の最大値が$4 \times 10^{12}$なのでとりあえず$10^6$くらいまでの素数を列挙しておけば後は上記のもので$N$以下となるようなものを数え上げてあげれば良いです。
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[] p = MathFunction.primes(1_000_000);
public static void main(String[] args){
long N = sc.nextLong();
int ans = 0;
for(int i=0;i<p.length;i++){
if(Math.pow(p[i],8)<=N)
ans += 1;
for(int j=i+1;j<p.length&&0<N/p[j]/p[j]/p[i]/p[i];j++)
ans += 1;
}
out.println(ans);
out.close();
}
}
E - Sum of Max Matching
問題文はこちら
解説に説明や証明は任せますが、貪欲法によって最適解が出るので、それを求めました。
E.java
final class Main{
private static final boolean autoFlush;
private static final SimpleScanner sc;
private static final SimpleWriter out;
static{
autoFlush = false;
sc = new SimpleScanner(System.in);
out = new SimpleWriter(System.out,autoFlush);
}
public static final void main(String[] args){
int N = sc.nextInt();
int M = sc.nextInt();
int K = sc.nextInt();
int[][] path = sc.nextInt(M,3);
HashMap<Integer,Point> map = new HashMap<>();
for(int i=1;i<=N;i++)
map.put(i,new Point(0,0));
for(int A:sc.nextInt(K))
map.get(A).x++;
for(int B:sc.nextInt(K))
map.get(B).y++;
Arrays.sort(path,(a,b)->Integer.compare(a[2],b[2]));
UnionFind uf = new UnionFind(N+1);
long ans = 0;
for(int[] p:path){
int u = p[0];
int v = p[1];
int w = p[2];
int ru = uf.root(u);
int rv = uf.root(v);
if(uf.unite(u,v)){
Point p1 = map.get(ru);
Point p2 = map.get(rv);
long AB = Math.min(p1.x,p2.y);
long BA = Math.min(p1.y,p2.x);
ans += (AB+BA)*w;
p1.x -= AB;
p1.y -= BA;
p2.x -= BA;
p2.y -= AB;
map.put(uf.root(u),new Point(p1.x+p2.x,p1.y+p2.y));
}
}
out.println(ans);
out.close();
}
}
F - Diversity
問題文はこちら
公式解説の通りです。
F.java
final class Main{
private static final boolean autoFlush;
private static final SimpleScanner sc;
private static final SimpleWriter out;
static{
autoFlush = false;
sc = new SimpleScanner(System.in);
out = new SimpleWriter(System.out,autoFlush);
}
public static final void main(String[] args){
int N = sc.nextInt();
int X = sc.nextInt();
int K = sc.nextInt();
HashMap<Integer,ArrayList<int[]>> map = new HashMap<>();
while(N-->0){
int P = sc.nextInt();
int U = sc.nextInt();
int C = sc.nextInt();
if(!map.containsKey(C)){
map.put(C,new ArrayList<>());
}
map.get(C).add(new int[]{P,U});
}
long[] ans = new long[X+1];
Arrays.fill(ans,Long.MIN_VALUE);
ans[0] = 0;
for(ArrayList<int[]> list:map.values()){
long[] dp = new long[X+1];
for(int[] goods:list)
for(int i=X;goods[0]<=i;i--)
dp[i] = MathFunction.max(dp[i],dp[i-goods[0]]+goods[1],ans[i-goods[0]]+goods[1]+K);
for(int i=0;i<=X;i++)
ans[i] = Math.max(ans[i],dp[i]);
}
out.println(MathFunction.max(ans));
out.close();
}
}
う～ん…コンテスト中には実装できないな…。
感想
A,B:易しめ
C,D:ちょうどいい感じの難易度
E:貪欲法じゃダメだろ！になって何もできなかった…
F:実装が…できません…
って感じでした。
落水で泣いてます。