はじめに
今回はコンテスト中にEまで、コンテスト後にFが解けたのでそれを載せようと思います。
なお、僕のライブラリは提出結果よりご確認下さい。
では、見ていきましょう。
A - tcdr
問題文はこちら
a、i、u、e、o以外をStringBuilderにappendしていくことで答えを構築しました。
A.java
final class Main {
private static final boolean autoFlush = false;
private static final SimpleScanner sc = new SimpleScanner( System.in );
private static final SimplePrinter out = new SimplePrinter( System.out, autoFlush );
public static void main ( String[] args ) {
//Sの受け取り
String S = sc.next();
//答えの構築
StringBuilder sb = new StringBuilder();
for(char c:S.toCharArray()){
if(c=='a'||c=='i'||c=='u'||c=='e'||c=='o')
continue;
sb.append(c);
}
//答えの出力
out.println(sb);
out.close();
}
}
ifの部分は以下のようにすることで短縮できましたね。
A改.java
import java.util.Scanner;
class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
//Sの受け取り
String S = sc.next();
//答えの構築
StringBuilder sb = new StringBuilder();
for(char c:S.toCharArray())
if("aiueo".indexOf(c)<0) //"aiueo"に含まれていなければ戻り値が-1なので、それを利用する
sb.append(c);
System.out.println(sb);
}
}
B - The Middle Day
問題文はこちら
$1$月から$i$月までの総和の$2$倍が全体の総和を超えているところがちょうど半分になるのでそこを探して出力しました。
B.java
final class Main {
private static final boolean autoFlush = false;
private static final SimpleScanner sc = new SimpleScanner( System.in );
private static final SimplePrinter out = new SimplePrinter( System.out, autoFlush );
public static void main ( String[] args ) {
//M、Dの受け取り
int M = sc.nextInt();
int[] D = sc.nextInt(M);
//Dの総和を求めておく
long sum = MathFunction.sum(D);
//今見ているところまでの総和
int now = 0;
for(int i=1;i<=M;i++){
//今見ている月がちょうど真ん中？
if((now+D[i-1])*2>sum){
out.println(i+" "+(sum/2-now+1));
break;
}
//総和に加算しておく
now += D[i-1];
}
out.close();
}
}
C - Flavors
問題文はこちら
一番美味しいアイスを食べるのが最適なので、一番美味しい物を探して後は他のものと組み合わせたときの最大値を求めました。
C.java
final class Main {
private static final boolean autoFlush = false;
private static final SimpleScanner sc = new SimpleScanner( System.in );
private static final SimplePrinter out = new SimplePrinter( System.out, autoFlush );
public static void main ( String[] args ) {
//N、アイスクリームの情報の受け取り
int N = sc.nextInt();
int[][] ice = sc.nextInt(N,2);
//おいしさでソート
Arrays.sort(ice,(a,b)->Integer.compare(b[1],a[1]));
//最大値を求める
int max = 0;
for(int i=1;i<N;i++){
//味が同じ？
if(ice[i][0]==ice[0][0])
max = Math.max(max,ice[0][1]+ice[i][1]/2);
//異なる味があればそれより後ろを見てもしょうがないので打ち切る
else{
max = Math.max(max,ice[0][1]+ice[i][1]);
break;
}
}
//答えの出力
out.println(max);
out.close();
}
}
最初なぜかfor文の条件文をi<=Nと書いてしまってて1ペナ出しました…もったいない…。
D - Magical Cookies
問題文はこちら
公式解説のものと同じです。
異なる点は、ArrayList<ArrayList<Integer>>ではなく、ArrayList<HashMap<Character,Integer>>で処理しているところでしょうか。
D.java
final class Main {
private static final boolean autoFlush = false;
private static final SimpleScanner sc = new SimpleScanner( System.in );
private static final SimplePrinter out = new SimplePrinter( System.out, autoFlush );
public static void main ( String[] args ) {
//H、Wの受け取り
int H = sc.nextInt();
int W = sc.nextInt();
//縦、横の文字の情報を管理するためのArrayList
ArrayList<HashMap<Character,Integer>> listH = new ArrayList<>();
for(int i=0;i<H;i++)
listH.add(new HashMap<>());
ArrayList<HashMap<Character,Integer>> listW = new ArrayList<>();
for(int i=0;i<W;i++)
listW.add(new HashMap<>());
//Mapに記録
for(int i=0;i<H;i++){
for(int j=0;j<W;j++){
char c = sc.nextChar();
listH.get(i).merge(c,1,Integer::sum);
listW.get(j).merge(c,1,Integer::sum);
}
}
//変更が施される間はずっとループ
boolean flag = true;
while(flag){
flag = false;
//印を付ける(ついでにListから削除しておく)
HashMap<Character,Integer> removeH = new HashMap<>();
for(int i=listH.size()-1;i>=0;i--){
if(listH.get(i).size()==1){
int sum = listH.get(i).values().iterator().next();
if(sum>1){
flag = true;
removeH.merge(listH.get(i).keySet().iterator().next(),1,Integer::sum);
listH.remove(i);
}
}
}
HashMap<Character,Integer> removeW = new HashMap<>();
for(int i=listW.size()-1;i>=0;i--){
if(listW.get(i).size()==1){
int sum = listW.get(i).values().iterator().next();
if(sum>1){
removeW.merge(listW.get(i).keySet().iterator().next(),1,Integer::sum);
flag = true;
listW.remove(i);
}
}
}
//印を元に文字を削除する
for(int i=listH.size()-1;i>=0;i--)
for(Map.Entry<Character,Integer> entry:removeW.entrySet())
listH.get(i).merge(entry.getKey(),-entry.getValue(),(a,b)->a+b==0?null:a+b);
for(int i=listW.size()-1;i>=0;i--)
for(Map.Entry<Character,Integer> entry:removeH.entrySet())
listW.get(i).merge(entry.getKey(),-entry.getValue(),(a,b)->a+b==0?null:a+b);
}
//Listに残っている文字の個数を数え上げ
int sum = 0;
for(HashMap<Character,Integer> map:listH)
for(int num:map.values())
sum += num;
//答えの出力
out.println(sum);
out.close();
}
}
ちょっと重かったですね…。
E - Prerequisites
問題文はこちら
本$1$から読んでみて、読まなくちゃいけない本を列挙していって、それらの本から読むことで読めるようになる本へ有向辺を張った有向グラフを構築してトポロジカルソートをして答えを求めました。
E.java
final class Main {
private static final boolean autoFlush = false;
private static final SimpleScanner sc = new SimpleScanner( System.in );
private static final SimplePrinter out = new SimplePrinter( System.out, autoFlush );
public static void main ( String[] args ) {
//Nの受け取り
int N = sc.nextInt();
//情報を元にグラフの構築(読む本から読まなきゃいけない本への有向辺)
int[][] graph = new int[N+1][];
for(int i=1;i<=N;i++){
int C = sc.nextInt();
graph[i] = sc.nextInt(C);
}
//本1を読むために必要な本を管理するSet
HashSet<Integer> group = new HashSet<>();
//BFS
ArrayDeque<Integer> deq = new ArrayDeque<>();
deq.add(1);
group.add(1);
while(deq.size()>0){
int now = deq.pollFirst();
for(int next:graph[now]){
if(group.contains(next))
continue;
group.add(next);
deq.add(next);
}
}
//有向辺を逆にして、Setの中の頂点のみでグラフを再構築
ArrayList<ArrayList<Integer>> list = new ArrayList<>();
for(int i=0;i<=N;i++)
list.add(new ArrayList<>());
for(int num:group)
for(int next:graph[num])
list.get(next).add(num);
//トポロジカルソートパート
int[] count = new int[N+1];
for(ArrayList<Integer> path:list)
for(int point:path)
++count[point];
int[] ans = new int[group.size()-1];
int index = 0;
for(int i=1;i<=N;++i){
if(group.contains(i)&&count[i]==0){
deq.add(i);
}
}
while(deq.size()>0){
int nowP = deq.pollFirst();
if(nowP!=1)
ans[index++] = nowP; // 読んだ順に記録(本1だけ除くように)
for(int nextP:list.get(nowP))
if(--count[nextP]==0){
deq.add(nextP);
}
}
//答えの出力
out.println(ans);
out.close();
}
}
F - Shortcuts
問題文はこちら
公式解説の通りです。
公式解説では考慮する無視の回数の上限を$100$と大きく見積もっていますが、一度も省略せずに通った時の最大の$s$を考えると、$(0,0)$から$(10000,10000)$、$(10000,10000)$から$(0,1)$、$(0,1)$から～みたいな感じが一番距離が長そうで、大体$10^4 \times \sqrt{(10^4)^2 + (10^4)^2} =10^8 \sqrt{2} \lt 2^{28}$と見積もれるので、考慮する無視の回数の上限を$28$としています。
F.java
final class Main {
private static final boolean autoFlush = false;
private static final SimpleScanner sc = new SimpleScanner( System.in );
private static final SimplePrinter out = new SimplePrinter( System.out, autoFlush );
public static void main ( String[] args ) {
//N、座標の受け取り
int N = sc.nextInt();
Point[] p = sc.nextPoint(N);
//探索上限
int L = 28;
//DPテーブル
double[][] cost = new double[N][L];
for(int i=0;i<N;i++)
Arrays.fill(cost[i],Double.POSITIVE_INFINITY);
cost[0][0] = 0;
//遷移
for(int i=0;i<N;i++){
for(int j=0;j<L;j++){
for(int k=1;k<=L-j;k++){
if(i+k>=N)
break;
cost[i+k][j+k-1] = Math.min(cost[i+k][j+k-1],cost[i][j]+Math.hypot(p[i].x-p[i+k].x,p[i].y-p[i+k].y));
}
}
}
//ペナルティを加えての最小値を求める
double ans = cost[N-1][0];
for(int i=1;i<L;i++)
ans = Math.min(ans,cost[N-1][i]+Math.pow(2,i-1));
//答えの出力
out.println(ans);
out.close();
}
}
いやぁ…DPかなぁとは思いましたが、遷移の仕方がわからなくて結局解けませんでした…無念…。
感想
A,B,C:易しい
D:結構重い
E:気付けばそこまで難しくない
って感じでした。
レートは上がりましたが、もうちょっといろいろ出来たんじゃないかと考えてしまいますね…。