はじめに
今回はコンテスト中にFまで解けたのでそれをそのまま載せようと思います。
では、見ていきましょう。
A - Jiro
問題文はこちら
頑張って全通り書きました。
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 AB = sc.nextChar()=='<'?-1:1;
int AC = sc.nextChar()=='<'?-1:1;
int BC = sc.nextChar()=='<'?-1:1;
if(AB==1){
if(BC==1){
out.println("B");
}
else if(AC==1){
out.println("C");
}
else{
out.println("A");
}
}
else if(AC==1){
out.println("A");
}
else if(BC==1){
out.println("C");
}
else{
out.println("B");
}
out.close();
}
}
B - Taro
問題文はこちら
太郎がすでに生まれているかを保持して順に処理しました。
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 M = sc.nextInt();
boolean[] flag = new boolean[N+1];
while(M-->0){
int A = sc.nextInt();
char B = sc.nextChar();
if(B=='M'){
if(flag[A]){
out.println("No");
}
else{
flag[A] = true;
out.println("Yes");
}
}
else{
out.println("No");
}
}
out.close();
}
}
C - Make Isomorphic
問題文はこちら
順列全探索で頂点の対応を全探索しながら解を求めました。
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 MG = sc.nextInt();
boolean[][] pathG = new boolean[N+1][N+1];
while(MG-->0){
int u = sc.nextInt();
int v = sc.nextInt();
pathG[u][v] = true;
pathG[v][u] = true;
}
int MH = sc.nextInt();
boolean[][] pathH = new boolean[N+1][N+1];
while(MH-->0){
int a = sc.nextInt();
int b = sc.nextInt();
pathH[a][b] = true;
pathH[b][a] = true;
}
int[][] A = new int[N+1][N+1];
for(int i=1;i<=N;i++){
for(int j=i+1;j<=N;j++){
A[i][j] = A[j][i] = sc.nextInt();
}
}
int min = Integer.MAX_VALUE;
int[] map = new int[N+1];
Arrays.setAll(map,i->i);
while(map[0]==0){
int ans = 0;
for(int i=1;i<=N;i++){
for(int j=i+1;j<=N;j++){
if(pathG[i][j]!=pathH[map[i]][map[j]]){
ans += A[map[i]][map[j]];
}
}
}
min = Math.min(min,ans);
ArrayUtil.nextPermutation(map);
}
out.println(min);
out.close();
}
}
D - 1D Country
問題文はこちら
予め村単位での累積和を求めておき、二分探索で含まれる村の区間を求めて解を計算しました。
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 N = sc.nextInt();
int[] X = sc.nextInt(N);
int[] P = sc.nextInt(N);
long[] sumP = new long[N+1];
for(int i=0;i<N;i++)
sumP[i+1] = sumP[i]+P[i];
int Q = sc.nextInt();
while(Q-->0){
int L = sc.nextInt();
int R = sc.nextInt();
int indexL = Searcher.upSearch(X,L);
int indexR = Searcher.downSearch(X,R);
out.println(indexL<=indexR?sumP[indexR+1]-sumP[indexL]:0);
}
out.close();
}
}
E - I Hate Sigma Problems
問題文はこちら
$i=1$のときをHashMapを使って求めておき、あとから$i$を$2,3,\dots$とずらしていくことで差分を求めながら数え上げました。
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[] A = sc.nextInt(N);
TreeMap<Integer,ArrayDeque<Integer>> map = new TreeMap<>();
for(int i=0;i<N;i++){
if(!map.containsKey(A[i]))
map.put(A[i],new ArrayDeque<>());
map.get(A[i]).add(i);
}
HashSet<Integer> set = new HashSet<>();
long ans = 0;
for(int num:A){
set.add(num);
ans += set.size();
}
long sum = ans;
for(int i=0;i<N;i++){
ArrayDeque<Integer> deq = map.get(A[i]);
deq.pollFirst();
int index = deq.size()>0?deq.peekFirst():N;
sum -= index-i;
ans += sum;
}
out.println(ans);
out.close();
}
}
F - Takahashi in Narrow Road
問題文はこちら
座標が$1$だけズレている高橋君をひとまとめにし、左端の座標と連続する人数をTreeMapで保持することで必要な移動回数を高速に求めました。
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();
TreeMap<Integer,Integer> map = new TreeMap<>();
for(int x:sc.nextInt(N)){
Integer f = map.floorKey(x);
if(f==null){
map.put(x,x);
}
else{
int right = map.get(f);
if(right+1<x)
map.put(x,x);
else
map.put(f,x);
}
}
TreeMap<Integer,Integer> mapIndex = new TreeMap<>();
int count = 1;
for(Entry<Integer,Integer> entry:map.entrySet()){
mapIndex.put(count,entry.getKey());
count += entry.getValue()-entry.getKey()+1;
}
int Q = sc.nextInt();
long ans = 0;
while(Q-->0){
int T = sc.nextInt();
int G = sc.nextInt();
int key = mapIndex.floorKey(T);
int left = mapIndex.get(key);
int right = map.get(left);
int X = (T-key)+left;
if(X<G){
if(left<X)
map.put(left,X-1);
else
map.remove(left);
long sum = right-X+1;
ans += (G-X)*sum;
right = (int)(G+sum-1);
mapIndex.put(T,G);
while(map.floorKey(right)!=null&&X<map.floorKey(right)){
int subKey = map.floorKey(right);
int subRight = map.get(subKey);
ans += (long)(subRight-subKey+1)*(right+1-subKey);
right += subRight-subKey+1;
map.remove(subKey);
Integer ind = mapIndex.higherKey(T);
mapIndex.remove(ind);
}
map.put(G,right);
}
else if(G<X){
if(X<right){
map.put(X+1,right);
mapIndex.put(T+1,X+1);
}
map.remove(left);
mapIndex.remove(key);
long sum = X-left+1;
ans += (X-G)*sum;
left = (int)(G-sum+1);
Integer ind = key;
while(map.floorKey(X)!=null&&left<=map.get(map.floorKey(X))){
int subKey = map.floorKey(X);
int subRight = map.get(subKey);
ans += (long)(subRight-subKey+1)*(subRight-left+1);
left -= subRight-subKey+1;
map.remove(subKey);
ind = mapIndex.lowerKey(T);
mapIndex.remove(ind);
}
map.put(left,G);
mapIndex.put(ind,left);
}
}
out.println(ans);
out.close();
}
}
感想
A,B:簡単
C:気づけばサクッと
D:Dにしては易しめ？
E:ちょっと実装がめんどう
F:ギリギリ実装間に合ってよかった…
って感じでした。
毎度こんな感じのパフォを取りたいねぇ。