はじめに
今回はCまでがコンテスト中、DとEはコンテスト後に提出したものを載せようと思います。
では見ていきましょう。
A - Count Down
問題文はこちら
whileでもforでも、どちらでも良さそうですね。
今回はwhileで実装しました。
A.java
class Main{
static final boolean autoFlush = false;
static final Library System = new Library(java.lang.System.in,java.lang.System.out,java.lang.System.err,autoFlush);
public static void main(String[] args){
//Nの受け取り
int N = System.in.nextInt();
//Nから0までを出力
System.out.println(N);
while(N-->0){
System.out.println(N);
}
System.out.close();
}
}
まぁ問題は無いですね。
B - Sandwich Number
問題文はこちら
長さが8とは限らないので(けど長さ見てなくて提出した人も通ったっぽいのをTwitterで見かけたのでもしかしたらそんなケースは無かった･･･？)、長さが8の時のみ処理することにします。
1文字目が大文字の英字か、2～7文字目が数字(かつ2文字目は0以外)か、8文字目が大文字の英字か、を見るように実装しました。
B.java
class Main{
static final boolean autoFlush = false;
static final Library System = new Library(java.lang.System.in,java.lang.System.out,java.lang.System.err,autoFlush);
public static void main(String[] args){
//Sの受け取り
String S = System.in.next();
//長さが8じゃないならNo
if(S.length()!=8){
System.out.println("No");
}else{
//各文字が条件を満たしているか見る
char c = S.charAt(0);
boolean isTrue = true;
isTrue &= 'A'<=c&&c<='Z';
for(int i=1;i<7;i++){
c = S.charAt(i);
isTrue &= '0'<=c&&c<='9';
isTrue &= (i==1?c!='0':true);
}
c = S.charAt(7);
isTrue &= 'A'<=c&&c<='Z';
//条件を満たしていた？
System.out.println(isTrue?"Yes":"No");
}
System.out.close();
}
}
いまいま思い返せば正規表現でやればもっと楽でしたね。
焦ってました･･･。
C - Circular Playlist
問題文はこちら
$A$の総和$S$を取って$T$を$T$%$S$に置き換えると、後は先頭から順に見ていって求めている番号と秒数を探せば解けました。
C.java
class Main{
static final boolean autoFlush = false;
static final Library System = new Library(java.lang.System.in,java.lang.System.out,java.lang.System.err,autoFlush);
public static void main(String[] args){
//N、T、Aの受け取り
int N = System.in.nextInt();
long T = System.in.nextLong();
int[] A = System.in.nextInt(N);
//総和を求める
long sum = 0;
for(int num:A)
sum += num;
//Tをsumで割ったあまりに
T %= sum;
//TよりA[index]の方が大きくなるまで探す
int index = 0;
while(true){
//この曲？
if(T<A[index]){
System.out.println((index+1)+" "+T);
break;
}
//違うならTから引いて次へ
T -= A[index++];
}
System.out.close();
}
}
これは比較的早く思いつきました。
D - Max Multiple
問題文はこちら
動的計画法で解きました。
$\mathrm{dp}[i][j]:i$個選んだ時の総和を$D$で割ったあまりが$j$になるものの最大値
として、以下のように遷移しました。
$\mathrm{next}[i][j] = \mathrm{max}(\mathrm{next}[i][j],\mathrm{dp}[i][j])$
$\mathrm{next}[j+1][(k+a[i])$%$D] = \mathrm{max}(\mathrm{dp}[j][k]+a[i],\mathrm{dp}[j+1][(k+a[i])$%$D])$
D.java
class Main{
static final boolean autoFlush = false;
static final Library System = new Library(java.lang.System.in,java.lang.System.out,java.lang.System.err,autoFlush);
public static void main(String[] args){
//N、K、D、aの受け取り
int N = System.in.nextInt();
int K = System.in.nextInt();
int D = System.in.nextInt();
int[] a = System.in.nextInt(N);
//dpテーブル
long[][] dp = new long[K+1][D];
//初期値は-1(dp[0][0]は0)
for(long[] temp:dp)
Arrays.fill(temp,-1);
dp[0][0] = 0;
//遷移
for(int i=0;i<N;i++){
//次のdpテーブル(+初期化)
long[][] next = new long[K+1][D];
for(long[] temp:next)
Arrays.fill(temp,-1);
//上記の式の通りに遷移
for(int j=0;j<=Math.min(i,K);j++){
for(int k=0;k<D;k++){
if(dp[j][k]==-1)
continue;
next[j][k] = Math.max(next[j][k],dp[j][k]);
if(j!=K)
next[j+1][(k+a[i])%D] = Math.max(dp[j][k]%D==k?dp[j][k]+a[i]:0,dp[j+1][(k+a[i])%D]);
}
}
//テーブルを置き換える
dp = next;
}
//K個選んだ時の総和のうち、Dで割ったあまりが0のものの最大値を返す(無ければ-1が入っている)
System.out.println(dp[K][0]);
System.out.close();
}
}
いやぁ･･･DP久しぶりで全然発想できなかった･･･精進不足ですね･･･。
E - Least Elements
問題文はこちら
$M$個を昇順に並べたときの先頭$K$個と後ろの$M-K$個を別々のAVL木で管理して解きました。
コード内のAVLTree_Multiの内容
空白とか省いてるので見づらいです。申し訳ない･･･。
AVLTree_Multi.java
final class AVLTree_Multi<E extends Comparable<? super E>>{
private Node<E> root;
private boolean hasChanged;
private int size;
public AVLTree_Multi(){
size=0;
root=null;
hasChanged=false;
}
public boolean add(final E x){
boolean bool;
if(root==null){
root=new Node<>(null,x);
bool=true;
}
else bool=root.add(x);
if(hasChanged){
root=root.parent;
hasChanged=false;
}
if(bool)++size;
return bool;
}
public boolean remove(final E x){
boolean bool;
if(root==null)bool=false;
else{
bool=root.remove(x);
if(hasChanged){
root=root.parent;
hasChanged=false;
}
}
if(bool)--size;
return bool;
}
public boolean contains(final E x){
if(root==null)return false;
return root.find(x);
}
public int count(final E x){
if(root==null)return 0;
return root.count(x);
}
public E pollFirst(){
if(root==null)return null;
--size;
final E min=root.pollMin();
if(hasChanged){
root=root.parent;
hasChanged=false;
}
return min;
}
public E pollLast(){
if(root==null)return null;
--size;
final E max=root.pollMax();
if(hasChanged){
root=root.parent;
hasChanged=false;
}
return max;
}
public E first(){
if(root==null)return null;
return root.first();
}
public E last(){
if(root==null)return null;
return root.last();
}
public E ceiling(final E x){
if(root==null)return null;
return root.ceiling(x,null);
}
public E floor(final E x){
if(root==null)return null;
return root.floor(x,null);
}
public int size(){
return size;
}
public String toString(){
final Object[]list=new Object[size];
if(root!=null)root.string(list,0);
return java.util.Arrays.toString(list);
}
private class Node<E extends Comparable<? super E>>{
private E value;
int height,count;
Node<E> left,right,parent;
public Node(final Node<E>p,final E v){
value=v;
height=0;
parent=p;
count=1;
}
private int getHeight(){
return Math.max(left==null?-1:left.height,right==null?-1:right.height);
}
public boolean add(final E x){
if(x.compareTo(value)>0)
if(right==null){
right=new Node<>(this,x);
height=getHeight()+1;
check();
return true;
}
else{
if(right.add(x)){
height=getHeight()+1;
check();
return true;
}
}
else if(x.compareTo(value)<0)
if(left==null){
left=new Node<>(this,x);
height=getHeight()+1;
check();
return true;
}
else{
if(left.add(x)){
height=getHeight()+1;
check();
return true;
}
}
else count++;
return true;
}
public boolean remove(final E x){
if(x.compareTo(value)>0){
if(right==null)return false;
else if(right.remove(x)){
height=getHeight()+1;
check();
return true;
}
}
else if(x.compareTo(value)<0){
if(left==null)return false;
else if(left.remove(x)){
height=getHeight()+1;
check();
return true;
}
}
else{
if(count>1)count--;
else
if(parent==null)
if(left==null&&right==null)hasChanged=true;
else{
value=left!=null?left.pollMax():right.pollMin();
height=getHeight()+1;
check();
}
else{
final boolean flag=parent.left==this;
if(left==null&&right==null){
if(flag)parent.left=null;
else parent.right=null;
parent=null;
}
else{
value=left!=null?left.pollMax():right.pollMin();
height=getHeight()+1;
check();
}
}
return true;
}
return false;
}
public boolean find(final E x){
if(x==value)return true;
if(x.compareTo(value)>0)
if(right==null)return false;
else return right.find(x);
else
if(left==null)return false;
else return left.find(x);
}
public int count(final E x){
if(x==value)return count;
if(x.compareTo(value)>0)
if(right==null)return 0;
else return right.count(x);
else
if(left==null)return 0;
else return left.count(x);
}
public E ceiling(final E x,final E before){
if(x.equals(value))return value;
if(x.compareTo(value)<0)
if(left==null)return value;
else return left.ceiling(x,value);
else
if(right==null)return before;
else return right.ceiling(x,before);
}
public E floor(final E x,final E before){
if(x.equals(value))return value;
if(x.compareTo(value)>0)
if(right==null)return value;
else return right.floor(x,value);
else
if(left==null)return before;
else return left.floor(x,before);
}
public E first(){
if(left==null)return value;
return left.first();
}
public E last(){
if(right==null)return value;
return right.last();
}
public E pollMax(){
if(right==null){
if(count>1)count--;
else
if(parent==null){
hasChanged=true;
parent=left;
if(parent!=null)parent.parent=null;
}
else{
if(parent.left==this)parent.left=left;
else parent.right=left;
if(left!=null)left.parent=parent;
parent=null;
}
return value;
}
final E max=right.pollMax();
height=getHeight()+1;
check();
return max;
}
public E pollMin(){
if(left==null){
if(count>1)count--;
else
if(parent==null){
hasChanged=true;
parent=right;
if(parent!=null)parent.parent=null;
}
else{
if(parent.left==this)parent.left=right;
else parent.right=right;
if(right!=null)right.parent=parent;
parent=null;
}
return value;
}
final E min=left.pollMin();
height=getHeight()+1;
check();
return min;
}
private void check(){
final int lh=left==null?-1:left.height;
final int rh=right==null?-1:right.height;
if(lh-rh>1)rotateR();
else if(rh-lh>1)rotateL();
height=getHeight()+1;
}
private void rotateR(){
final Node<E>temp=left;
left=left.right;
if(left!=null)left.parent=this;
temp.right=this;
temp.parent=parent;
if(parent!=null)
if(parent.left==this)parent.left=temp;
else parent.right=temp;
else hasChanged=true;
parent=temp;
if(left!=null)left.check();
if(right!=null)right.check();
}
private void rotateL(){
final Node<E>temp=right;
right=right.left;
if(right!=null)right.parent=this;
temp.left=this;
temp.parent=parent;
if(parent!=null)
if(parent.left==this)parent.left=temp;
else parent.right=temp;
else hasChanged=true;
parent=temp;
if(left!=null)left.check();
if(right!=null)right.check();
}
public int string(final Object[]list,int index){
if(left!=null)index=left.string(list,index);
for(int i=0;i<count;i++)
list[index++]=value;
if(right!=null)index=right.string(list,index);
return index;
}
public String toString(){
return value.toString();
}
}
}
E.java
class Main{
static final boolean autoFlush = true;
static final Library System = new Library(java.lang.System.in,java.lang.System.out,java.lang.System.err,autoFlush);
public static void main(String[] args){
//N、M、K、Aの受け取り
int N = System.in.nextInt();
int M = System.in.nextInt();
int K = System.in.nextInt();
int[] A = System.in.nextInt(N);
//先頭K個用(head)と後ろ用(tail)
AVLTree_Multi<Integer> head = new AVLTree_Multi<>();
AVLTree_Multi<Integer> tail = new AVLTree_Multi<>();
//総和を数えながらheadに追加していく
long sum = 0;
for(int i=0;i<M;i++){
sum += A[i];
head.add(A[i]);
}
//不要な分をtailに移動(+総和から引く)
for(int i=K;i<M;i++){
Integer a = head.pollLast();
tail.add(a);
sum -= a;
}
//最初の答えの出力
System.out.print(sum+" ");
//一個ずつずらしていく
for(int i=M;i<N;i++){
//左端がどっちに入っているかで分岐
if(head.last()<A[i-M])
tail.remove(A[i-M]);
else{
head.remove(A[i-M]);
Integer temp = tail.pollFirst();
//M=1の時にnullになり得るのでその対策
if(temp==null)
temp = 0;
else
head.add(temp);
sum += temp-A[i-M];
}
//追加するのがどっち側かで分岐(M=1の時nullになる可能性があるのでその分岐も)
Integer last = head.last();
if((last!=null?last:Integer.MAX_VALUE)<=A[i])
tail.add(A[i]);
else{
Integer temp = head.pollLast();
head.add(A[i]);
//M=1の時用
if(temp==null)
temp = 0;
else
tail.add(temp);
sum += A[i]-temp;
}
//現在の総和の出力
System.out.print(sum+" ");
}
//最後改行しておく
System.out.println();
System.out.close();
}
}
これは･･･本番中に思いつくかな･･･。
感想
A:易しい
B:めんどくさいことしちゃったな･･･
C:Cにしては簡単？
D:全然頭回ってなかった･･･悔しい･･･
E:実装途中で終わっちゃったけど考え方間違ってたから結局解けなかった･･･
って感じでした。
久々の3完に･･･悔しいなぁ･･･。