※説明を書き加えました(2022/07/06)
はじめに
今回はCまでしか解けなかった(本番中はBまで)ので、そこまで解説します。
では、見ていきましょう。
※自分のテンプレートに、1行に複数の整数があったとき用のメソッドが無いので一度String[]として受け取ってから処理しています。
A - A to Z String 2
問題文はこちら
単純に文字列を作ってもいいですが、計算だけで実装しましょう。
各文字がN個続けて並んでいるのでAを0番目、Bを1番目…としていくと、XはtN+r(0≦r<N,0≦t<26)と表せることからX番目の文字はt番目だとわかります。
しかし単純にX/Nでtを求めれば良い(rはN未満なので切り捨てられ、純粋にtを求めることが出来る)と言うわけではないです。例えば、N=2、X=3と与えられればBと正しく出力されると思いますがX=4だった場合、X/Nは2になってしまい、2番目の文字であるCが出力されてしまいます(AABBCC･･･となるため正解はB)。これはXが0番目からではなく1番目から始まることに起因します。ですので、X-1番目の文字を調べるようにすれば正しく出力されます(つまり、(X-1)/N)。
なお、char型で今回は実装しているので(X-1)/Nに'A'を足してcharでキャストしています。
import java.io.*;
class Main{
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter pw = new PrintWriter(System.out);
public static void main(String[] args)throws IOException{
//N、Xを文字列として受け取ってから数値変換
String[] str = reads(" ");
int N = Integer.parseInt(str[0]);
int X = Integer.parseInt(str[1]);
//説明の式を実装
println((char)(((X-1)/N)+'A'));
flush();
}
/*
reads(str) :String型配列として取得(str区切り)
println(T) :Tを出力(改行アリ)
flush() :flushする
*/
public static String[] reads(String str)throws IOException{
return br.readLine().split(str);
}
public static void println(Object T){
pw.println(T);
}
public static void flush(){
pw.flush();
}
}
提出前に-1することに気づけたのが非常に嬉しかったです。ペナルティもらわなくて済みました。
B - 1D Pawn
問題文はこちら
問題文に書かれている操作をそのまま実装しましょう。
N個のマスを準備するのですが、同一マスに複数のコマは存在しないこととA、L共に最初のマスを1番目としていることからboolean[N+1]で宣言してしまった方が楽そうです。コンテスト中に上手い実装が思いつかなかったので、L番目のコマを探すときはfor文で先頭から一つずつ数えました。
import java.io.*;
class Main{
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter pw = new PrintWriter(System.out);
public static void main(String[] args)throws IOException{
//N、K、Qを文字列として受け取ってから数値変換
String[] str = reads(" ");
int N = Integer.parseInt(str[0]);
int K = Integer.parseInt(str[1]);
int Q = Integer.parseInt(str[2]);
//A、Lの取得
int[] A = readInt(K);
int[] L = readInt(Q);
//マス目の準備&コマを配置
boolean[] masu = new boolean[N+1];
for(int i=0;i<K;i++){
masu[A[i]] = true;
}
//順に操作をしていく
for(int i=0;i<Q;i++){
//何個目のコマか管理するtemp、コマの位置を管理するpointを準備
int temp = 0,point = -1;
//最初から順に目的のコマを探す
for(int j=1;j<N;j++){
//コマがあるか？
if(masu[j]){
//目的のコマか？
if(L[i]==++temp){
point = j;
break;
}
}
}
//隣にコマがあるか一番右なら動かさない
if(masu[point+1] || point==-1){
continue;
}
//コマを動かす
masu[point] = false;
masu[point+1] = true;
}
//コマがある場所を探して順に出力
for(int i=1;i<=N;i++){
//コマがある？
if(masu[i]){
print(i);
print(" ");
}
}
//最後改行してflush
println();
flush();
}
/*
readInt(n) :n型配列として取得(空白区切り)
reads(str) :String型配列として取得(str区切り)
print(T) :Tを出力
println() :改行を出力
flush() :flushする
*/
public static int[] readInt(int n)throws IOException{
int[] ans = new int[n];
String[] str = br.readLine().split(" ");
for(int i=0;i<n;i++){
ans[i] = Integer.parseInt(str[i]);
}
return ans;
}
public static String[] reads(String str)throws IOException{
return br.readLine().split(str);
}
public static void print(Object T){
pw.print(T);
}
public static void println(){
pw.println();
}
public static void flush(){
pw.flush();
}
}
特には悩まないですね。
コマの順番は絶対に前後しないので(隣にあると動かないので)、mapで「何番目か」と「どこにあるか」を管理して解いても面白そうですね。
C - Robot Takahashi
問題文はこちら
最初は二分探索で解こうとしたんですが結局どこが間違っているのかわからず断念…。
WをTreeMapに記録していくのですが(キーは体重+1)、大人の場合は値を-1、子どもの場合は値を+1します。これはXを最小値から徐々に大きくしていったときに、ある大人の体重よりもXが大きくなったらその大人を子どもと誤判定してしまう、ある子どもの体重よりもXが大きくなったらその子どもを子どもと正しく判定できるからです。
初期状態では全員大人と判断しているので、そこからXを大きくしていったときの増減をTreeMapに記録したという感じでしょうか。
※なお、この解法はcirno3153さんの解説を参考にしました。ありがとうございます。
import java.io.*;
import java.util.*;
class Main{
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter pw = new PrintWriter(System.out);
public static void main(String[] args)throws IOException{
//Nの取得
int N = readInt();
//Sをchar型配列として取得
char[] ch = read().toCharArray();
//大人の人数を記録
int count = 0;
for(int i=0;i<N;i++){
if(ch[i]=='1')
count++;
}
//大人だけ、子供だけならさっさと終わらせる
if(count==N||count==0){
println(N);
flush();
System.exit(0);
}
//WをString型配列として取得
String[] str = reads(" ");
//変化量記録用map(昇順じゃないと困るのでTreeMap)
TreeMap<Integer,Integer> changeOfAns = new TreeMap<Integer,Integer>();
//Wを順に見ていく
for(int i=0;i<str.length;i++){
//数値変換して格納
int temp = parseInt(str[i]);
//これは大人の体重？
if(ch[i]=='1'){
//Xを増やすと大人は子供と判定されるので-1
if(changeOfAns.get(temp+1)==null)
changeOfAns.put(temp+1,-1);
else
changeOfAns.replace(temp+1,changeOfAns.get(temp+1)-1);
}
else{
//Xを増やすと大人と判定されていた子供が子供と判定されるので+1
if(changeOfAns.get(temp+1)==null)
changeOfAns.put(temp+1,1);
else
changeOfAns.replace(temp+1,changeOfAns.get(temp+1)+1);
}
}
//初期状態を格納(全員大人判定なので、大人の数=正しく判定できる数)
int temp = count;
int answer = temp;
//順にXを大きくしていってtempに逐一記録
for(int i : changeOfAns.keySet()){
temp += changeOfAns.get(i);
//今最高値更新してる？
if(answer<temp)
answer = temp;
}
//答えを出力
println(answer);
flush();
}
/*
readInt() :1行に数字一つのみある時用
read() :1行をそのまま取得
reads(str) :String型配列として取得(str区切り)
println(T) :Tを出力(改行アリ)
flush() :flushする
parseInt(str) :strをintに変換(変換ミスを検知できない)
*/
public static int readInt()throws IOException{
return Integer.parseInt(br.readLine());
}
public static String read()throws IOException{
return br.readLine();
}
public static String[] reads(String str)throws IOException{
return br.readLine().split(str);
}
public static void println(Object T){
pw.println(T);
}
public static void flush(){
pw.flush();
}
public static int parseInt(String str){
char[] nums = str.toCharArray();
int ans = 0;
boolean plus = true;
if(nums[0]=='-'){
plus = false;
nums[0]='0';
}
for(int i=0;i<nums.length;i++){
ans = ans*10 + (int)(nums[i]-'0');
}
return plus ? ans : -ans;
}
}
二分探索でも解けるそうなので、もう少し理解を深めて再挑戦したいです。
感想
A：コーナーケースにだけ気をつければOK。
B：ちょっと重い実装ではあるけど、まだ易しい方。
C：ちょっと難しかった。これくらいは解けないとまずいな…。
って感じでした。
うーん…精進が足りないなと感じるコンテストでした…。
追記(D - Jumping Takahashi 2)
問題文はこちら
二分探索で求めました。
訓練回数$X$を何かしらの値に決めると、$X$回の訓練で全ジャンプ台に移動可能かは全頂点を始点としたBFSによって$\mathrm{O}(N^3)$で求めることが出来ます。また、訓練回数は$0$から適当な最大値$K$の範囲での二分探索となるので全体として$\mathrm{O}(N^3\mathrm{log}K)$で解を求められます(公式解説のまんまです)。
import java.util.Scanner;
import java.util.ArrayDeque;
class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
//Nの受け取り
int N = sc.nextInt();
//ジャンプ台の情報を管理するクラス
class Point{
long x,y,p;
Point(int x,int y,int p){
this.x = x;
this.y = y;
this.p = p;
}
}
//ジャンプ台の情報の受け取り
Point[] p = new Point[N];
for(int i=0;i<N;i++){
int x = sc.nextInt();
int y = sc.nextInt();
int P = sc.nextInt();
p[i] = new Point(x,y,P);
}
//適当な下限、上限の設定
long a = 0;
long b = Long.MAX_VALUE/(long)1e9;
long ans = b;
//二分探索
while(a-b<1){
long c = (a+b)/2;
//どこかのジャンプ台を始点にすると到達可能か？
boolean canSelect = false;
//全始点探索
for(int i=0;i<N;i++){
//到達済みか管理する配列
boolean[] isPassed = new boolean[N];
//BFS
ArrayDeque<Integer> bfs = new ArrayDeque<>();
bfs.add(i);
isPassed[i] = true;
while(!bfs.isEmpty()){
int now = bfs.pollFirst();
long power = p[now].p*c;
for(int j=0;j<N;j++){
if(isPassed[j])
continue;
if(power>=Math.abs(p[now].x-p[j].x)+Math.abs(p[now].y-p[j].y)){
isPassed[j] = true;
bfs.add(j);
}
}
}
//全ジャンプ台に到達可能だったかで変数を更新
boolean canReach = true;
for(boolean f:isPassed)
canReach &= f;
canSelect |= canReach;
}
//適切に上・下限を更新
if(canSelect)
b = (ans=c)-1;
else
a = c+1;
}
//答えの出力
System.out.println(ans);
}
}
本番中には気づけない解法だなぁ…。
追記(E - Addition and Multiplication 2)
問題文はこちら
公式解説の通りです。
import java.util.Scanner;
class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
//Nの受け取り
int N = sc.nextInt();
//各整数の値段と、その最小値を管理する変数
int[] C = new int[10];
int minValue = Integer.MAX_VALUE;
for(int i=1;i<=9;i++)
minValue = Math.min(minValue,C[i] = sc.nextInt());
//全体の長さ
int len = N/minValue;
//答えの生成
StringBuilder ans = new StringBuilder();
while(len-->0){
//大きい方から貪欲に
for(int i=9;i>0;i--)
if(len*minValue+C[i]<=N){
ans.append(i);
N -= C[i];
break;
}
}
//答えの出力
System.out.println(ans.toString());
}
}
貪欲で求められそうなのは気づいたんですが、じゃあどうするの？というところが思いつきませんでした…。