はじめに
今回はEまで解けたのでEまで載せます。
なお、Cはコンテスト中のものも載せますがかなり汚いのでコンテスト後に解いたものも載せます。
では見ていきましょう。
A - 484558
問題文はこちら
printfでいけそうとは思ったのですが16進数の時の書式指定ってどう書くんだ･･･？ってなったのでif文で2文字にしました。
A.java
class Main{
static Library System = new Library(java.lang.System.in,java.lang.System.out);
public static void main(String[] args)throws IOException{
//Nの受け取り(16進数に変換して大文字に)
String N = Integer.toString(System.in.nextInt(),16).toUpperCase();
//1文字なら0を出力してからNの出力
if(N.length()==1)
System.out.print(0);
System.out.println(N);
System.out.close();
}
}
まぁ問題はないですね。
printfで出力する方法はcirno3153さんの解説にあります。
B - Maintain Multiple Sequences
問題文はこちら
ただ受け取って出力するだけですね。
B.java
class Main{
static Library System = new Library(java.lang.System.in,java.lang.System.out);
public static void main(String[] args)throws IOException{
//N、Qの受け取り
int N = System.in.nextInt();
int Q = System.in.nextInt();
//各配列の受け取り
int[][] list = new int[N][];
for(int i=0;i<N;i++){
int L = System.in.nextInt();
list[i] = System.in.nextInt(L);
}
//s、tを受け取って出力
while(Q-->0){
int s = System.in.nextInt()-1;
int t = System.in.nextInt()-1;
System.out.println(list[s][t]);
}
System.out.close();
}
}
Bにしては比較的簡単･･･？
C - Manga
問題文はこちら
最初はコンテスト中の解答です。
重複した本は違う本に替えた方が良いので重複を変数に記録しながらTreeSetに持っている本を記録しました。
その後は先頭から順に見ていき、抜けている本があれば重複を-2して補填。重複が足りなくなれば後ろの2冊を消費して補填しました。これを続けられるだけ続けて答えを出力します。
C.java
class Main{
static Library System = new Library(java.lang.System.in,java.lang.System.out);
public static void main(String[] args)throws IOException{
//Nの受け取り
int N = System.in.nextInt();
//重複なし数列を作るため用
TreeSet<Integer> list = new TreeSet<Integer>();
//重複を数える用
int tmp = 0;
//重複してればtmpに加算、重複してなければlistに追加
for(int i=0;i<N;i++){
int a = System.in.nextInt();
if(list.contains(a))
tmp++;
else
list.add(a);
}
//後ろからみたいのでイテレータで
Iterator<Integer> itr = list.descendingSet().iterator();
//今読み終わっている巻数
int now = 0;
//イテレータで参照し終わった巻数(念のため初期値は大きく)
int pin = (int)1e9;
while(true){
//読めるなら読んで終わり
if(list.contains(now+1)&&now+1<pin)
++now;
else{
//重複分で誤魔化せる？
if(tmp>1){
tmp -= 2;
++now;
}else{
//イテレータで後ろから2冊分取り出す(取り出せなければ終了)
if(itr.hasNext())
pin = itr.next();
else
break;
while(pin>now){
if(++tmp==2)
break;
if(itr.hasNext())
pin = itr.next();
else
break;
}
//ちゃんと2冊分取り出せた？
if(tmp==2){
tmp = 0;
++now;
}else
break;
}
}
}
//読めた巻数を出力
System.out.println(now);
System.out.close();
}
}
以下コンテスト後の解答です。
ある値$K$より大きい巻数の本を全て売ることでK巻まで読めるか？を二分探索することで解きました。
C改.java
class Main{
static Library System = new Library(java.lang.System.in,java.lang.System.out);
public static void main(String[] args)throws IOException{
//N、aの受け取り
int N = System.in.nextInt();
int[] A = System.in.nextInt(N);
//ソートしておく
System.sort(A);
//重複なしのものを作る用(setで良かったかも･･･？)
ArrayList<Integer> list = new ArrayList<Integer>();
list.add(A[0]);
//重複を数える
int tmp = 0;
for(int i=1;i<N;i++)
if(A[i-1]==A[i])
tmp++;
else
list.add(A[i]);
//重複なしでの所持数
int num = list.size();
//二分探索
int a=0,b=(int)1e9,ans = 0;
while(a-b<1){
int c = (a+b)/2;
//c以下の要素のindexを探す
int index = System.downsearch(list,c);
//読める巻数を計算
int book = index+1 + (tmp+num-index-1)/2;
if(book>=c)
a = (ans = c) + 1;
else
b = c - 1;
}
//答えの出力
System.out.println(ans);
System.out.close();
}
}
こっちの方が個人的にはわかりやすい解法な気がします。二分探索で解けるとはなかなか気づけませんね･･･。
D - Flip and Adjust
問題文はこちら
動的計画法で解きました。
$i$が作れるかどうかを$dp[i]$に記録しながら、HashMapに$i$をkeyとして経路も記録しておきました。
D.java
class Main{
static Library System = new Library(java.lang.System.in,java.lang.System.out);
public static void main(String[] args)throws IOException{
//N、S、a、bの受け取り
int N = System.in.nextInt();
int S = System.in.nextInt();
int[][] ab = System.in.nextInt(N,2);
//dp[i]:iが作れるか
boolean[] dp = new boolean[S+1];
//初期では0
dp[0] = true;
//経路記録用
HashMap<Integer,String> route = new HashMap<Integer,String>();
//初期値
route.put(0,"");
//先頭から1枚ずつ検証
for(int i=0;i<N;i++){
//今の状態から遷移した後用
boolean[] nextDp = new boolean[S+1];
HashMap<Integer,String> nextRoute = new HashMap<Integer,String>();
for(int j=0;j<=S;j++){
//jが作れているなら遷移
if(dp[j]){
if(j+ab[i][0]<=S){
nextDp[j+ab[i][0]] = true;
nextRoute.put(j+ab[i][0],route.get(j)+"H");
}
if(j+ab[i][1]<=S){
nextDp[j+ab[i][1]] = true;
nextRoute.put(j+ab[i][1],route.get(j)+"T");
}
}
}
dp = nextDp;
route = nextRoute;
}
//Sが作れた？
if(dp[S]){
System.out.println("Yes");
System.out.println(route.get(S));
}else
System.out.println("No");
System.out.close();
}
}
今思えば裏表しかないのでStringで記録するんじゃなくてboolean型配列で記録してもよかったかなぁとか思いました。
E - Subsequence Path
問題文はこちら
動的計画法みたいに解きました。
$E$の部分列のみしか調べなくて良いので、HashMapに今の場所をkey、今の場所までの最短距離をvalueに持たせるようにしてEの先頭から調べて行けば良いです。
E.java
class Main{
static Library System = new Library(java.lang.System.in,java.lang.System.out);
public static void main(String[] args)throws IOException{
//N、M、K、道、Eの受け取り
int N = System.in.nextInt();
int M = System.in.nextInt();
int K = System.in.nextInt();
int[][] route = System.in.nextInt(M,3);
int[] E = System.in.nextInt(K);
//dpみたいなことをやる用
HashMap<Integer,Long> list = new HashMap<Integer,Long>();
//Eを先頭から見ていく
for(int r:E){
//0-indexedなので-1
--r;
//1から伸びる道なら無条件で追加
if(route[r][0]==1){
//すでに情報があるなら最小値で更新
if(list.get(route[r][1])!=null){
list.put(route[r][1],
Math.min(list.get(route[r][1]),route[r][2]));
}else{
list.put(route[r][1],(long)route[r][2]);
}
//始点がlistにある？
}else if(list.get(route[r][0])!=null){
long before = list.get(route[r][0]);
//もし終点がすでにあるなら最小値で更新
if(list.get(route[r][1])!=null){
list.put(route[r][1],
Math.min(list.get(route[r][1]),route[r][2]+before));
}else{
list.put(route[r][1],route[r][2]+before);
}
}
}
//Nまでの最小経路があるならそれを、ないなら-1
if(list.get(N)!=null)
System.out.println(list.get(N));
else
System.out.println(-1);
System.out.close();
}
}
公式解説みたいに普通に配列でdpやる方法もあるみたいです。というか、その方が良いのかな･･･？
感想
A、B:易しい
C:一度TLEもらって焦って汚いコードを書いてしまった･･･
D:公式解説みたいな経路復元のやり方が出てこなかった･･･
E:正直通ると思ってなかった。気付けばそんなに難しくはない･･･？
って感じでした。
二回目の5完でした。5完安定させたいな･･･。