はじめに
今回もCまではコンテスト中、DとEはコンテスト後に解いたものを載せようと思います。
では、見ていきましょう。
※今のライブラリが見たい場合はこちらから確認出来ます(見辛いですが･･･)
A - Generalized ABC
問題文はこちら
Aから$i$番目$(0 \le i \lt 26)$の文字は(char)('A'+i)なので、forで順に出力しました。
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){
//Kの受け取り
int K = System.in.nextInt();
//Aから順に出力
for(int i=0;i<K;i++)
System.out.print((char)('A'+i));
//必要は無いけど、気持ち的に改行も
System.out.println();
System.out.close();
}
}
難しくはなかったです。
B - Let's Get a Perfect Score
問題文はこちら
制約に「$M$は$1$以上$30$以下」と書いてあるので、$S_i$はint型で管理出来そうだなと思ってそれぞれをintに変換しました。後は全組み合わせを2重for文で調べました。
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){
//N、M、Sの受け取り
int N = System.in.nextInt();
int M = System.in.nextInt();
char[][] S = System.in.nextCharArray(N);
//対応する整数に変換
int[] s = new int[N];
for(int i=0;i<N;i++){
for(int j=0;j<M;j++){
if(S[i][j]=='o')
s[i] |= 1<<j;
}
}
//条件に合う組み合わせを数え上げ
int count = 0;
for(int i=0;i<N;i++){
for(int j=i+1;j<N;j++){
if((1<<M)==(s[i]|s[j])+1)
count++;
}
}
//出力
System.out.println(count);
System.out.close();
}
}
今々思えば普通に文字のままでも良かったかな･･･と思います。
C - String Delimiter
問題文はこちら
今までに出てきた"の中か否かをboolean型変数で保持する形で解きました.
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の受け取り
int N = System.in.nextInt();
//外側ならtrue、違うならfalse
boolean flag = true;
//一文字ずつ受け取り
while(N-->0){
char c = System.in.nextChar();
//外側で,なら.に変換
if(c==','&&flag)
c = '.';
//"ならflagを反転
else if(c=='"')
flag = !flag;
//処理した文字を出力
System.out.print(c);
}
//お気持ち程度の改行
System.out.println();
System.out.close();
}
}
Cにしては易しいかも･･･？
D - Make Bipartite 2
問題文はこちら
二部グラフをこの問題で初めて知ったんですが、条件を満たすような辺の貼り方は頂点二つを結ぶ全通りから$M$引いて、あとは二部グラフの同じ色同士の頂点を結ぶ辺も引けば答えになります。
公式解説にある通り、そもそもGが二部グラフでない場合に注意してください。
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、Mの受け取り
int N = System.in.nextInt();
int M = System.in.nextInt();
//辺の受け取り
ArrayList<HashSet<Integer>> route = new ArrayList<>();
for(int i=0;i<=N;i++)route.add(new HashSet<>());
for(int i=0;i<M;i++){
int u = System.in.nextInt();
int v = System.in.nextInt();
route.get(u).add(v);
route.get(v).add(u);
}
//全連結成分が二部グラフか保持する変数
boolean isBipartite = true;
//探索済みか記録する配列
boolean[] checked = new boolean[N+1];
//色を記録する変数(1か2ならすでに塗っている。0なら未着色)
int[] color = new int[N+1];
//張ることの出来る辺の総数
long ans = (long)N*(N-1)/2-M;
//各頂点ごとに見ていく
for(int i=1;i<=N;i++){
//すでに調べ済みならスルー
if(checked[i])
continue;
//不必要ではあるけど気持ち的に
checked[i] = true;
//今見ている頂点を1にする
color[i] = 1;
//BFS用のArrayDeque
ArrayDeque<Integer> bfs = new ArrayDeque<>();
//各色の数
long count1 = 1;
long count2 = 0;
//今見ている頂点を入れる
bfs.add(i);
//BFS
while(bfs.size()>0){
int now = bfs.pollFirst();
for(int next:route.get(now)){
//もし同じ色なら二部グラフではないのでfalseになる
isBipartite &= color[now]!=color[next];
//未探索だった時
if(color[next]==0){
bfs.add(next);
color[next] = 3-color[now];
checked[next] = true;
if(color[next]==1)
count1++;
else
count2++;
}
}
}
//同じ色同士で辺は張れないので減らす
ans -= count1*(count1-1)/2;
ans -= count2*(count2-1)/2;
}
//全て二部グラフだったかで場合分け
System.out.println(isBipartite?ans:0);
System.out.close();
}
}
全然分からなくて本番は解けませんでした･･･悔しい･･･。
E - Choose Two and Eat One
問題文はこちら
これの操作回数を考えると$N-1$回になると思いますが($1$回の操作で$1$個減るので)、全部を$1$回以上取り出すということは頂点の数が$N$、辺の数が$N-1$の木構造だと考えることができます。あとはクラスカル法と同様に行なうことで答えが求められます。
PriorityQueueを使ったのですが、これはpollで最小値を返すので手に入る得点は一度負に変換して、出力時にひっくり返してます。
E.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、M、Aの受け取り
int N = System.in.nextInt();
int M = System.in.nextInt();
int[] A = System.in.nextInt(N);
//ヒープ(PriorityQueue)
//Pairはjavafx.util.Pairみたいな実装にしてある(Keyで比較するようにしてある)
PriorityQueue<Pair<Integer,Pair<Integer,Integer>>> heap = new PriorityQueue<>();
//iとjに辺を張ったときの得点を記録
for(int i=0;i<N;i++){
for(int j=i+1;j<N;j++){
//得点の大きい方を取り出すために負数にしておく
heap.add(new Pair<>(-(int)((System.modPow(A[i],A[j],M)+System.modPow(A[j],A[i],M))%M),new Pair<>(i,j)));
}
}
//合計得点
long ans = 0;
//閉路になってしまわないか確認するようのUnionFind(内容はアルゴ式のものと一緒のはず)
UnionFind uf = new UnionFind(N);
//全部結ばれるまで繰り返す
while(uf.groupCount()>1){
//最大得点の取り出し
Pair<Integer,Pair<Integer,Integer>> temp = heap.poll();
int cost = temp.getKey();
Pair<Integer,Integer> pair = temp.getValue();
//辺が張れたら加算
if(uf.unite(pair.getKey(),pair.getValue()))
ans += cost;
}
//負数になっているので反転して出力
System.out.println(-ans);
System.out.close();
}
}
こんな簡単に求まるんだ･･･と解いていて感心してしまいました。
追記
cirno3153さんから教えてもらいましたが、PriorityQueueはコンストラクタにComparator.reverseOrder()を渡してあげれば逆順にできるようです。
教えていただき、ありがとうございます！
感想
A,B;易しい
C:Cにしては結構易しい？
D:難しい･･･Cとの差がでかい･･･
E:言われれば確かに･･･と思うが、本番中には気付かないな･･･
って感じでした。
二回連続で3完なので、レートが･･･溶けていく･･･。