[伯俊]2869号:カタツムリが行きたい-Java(Java)

この問題はカタツムリが1日登って、また1日滑って、それから所望の高さの棒の先端まで繰り返し登ったことです.昼間は登り、夜は山頂まで滑っても滑らないのが特徴で、時間は0.15秒に制限されています.

Step 0. 解答コード

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
public class Raise_Snail {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		int up = Integer.parseInt(st.nextToken());
		int down = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());

		int move = up - down; //실질적인 하루 이동 거리(올라간 거리 - 내려간 거리)
		int safe_m = m - up; //up+down이 무조건 일어나는 날들의 마지노선을 구해줄 때 사용
		if(safe_m == 0) {
			System.out.println(1);
			return;
		}
		int day = safe_m / move;
		 if (day * move + up >= m) {
			System.out.println(day + 1);
		} else{
			System.out.println(day + 2);
		}
			
		
	}
}

問題を見ると時間制限がないようで、時間がきついので、何か修飾したいようですが、まずfor文で答えました.やはりタイムアウトですねタイムアウト正解率は20%くらいなので

Step 1. 質問へのアクセス

カタツムリは1日基準で昼間は上昇し、夜は滑って倒れます.また、頂上までは滑らないと書かれています.例えば、1日3メートル、距離1メートル、5メートルまで登る必要がある場合は、初日は3メートル->3メートル->2メートルに位置します.翌日は2メートル→5メートルでピークに達し、4メートルに滑らない.それを意識して、どんな方法で解決したいのか考えました.考えた結果,1日で実際に移動した距離(上昇距離−下降距離,move変数)を求め,その後move(実際の移動距離)が無条件に運行しているマギールートの日付を求め,そのマギールートの当日にさらに上昇した距離(up)を加えた.ここでマギーコース日を求めたのは、私たちが求めた最終日にカタツムリがちょうど距離を合わせれば滑らず、そうでなければ滑ることがないため、無条件に滑るマギーコースを求めたからです.例えば、5、2および17が入力されると、カタツムリは1日3メートル移動する(5−2).しかし、あなたが望む高さに達すると、5メートル移動します.そこで、まず移動3 mの日付を求め、本来移動していた5 mを移動してから移動できるようにすれば、2日後に上部に到着し、5 m移動し、所望の高さに達したら翌日に到着します.つまり、私たちは私たちが望んでいる日の前日か前日を救い、私たちが望んでいる日を安全に救ったということです.

Step 2. 問題を解く

まず、この問題には時間制限がある.最初はScannerクラスを使用しましたが、タイムアウトが発生したためBufferReaderを使用します.Scannerに比べてBuffer時間は長いが、複数のデータを受信すると速度が速くなる.欠点はString形式でしかデータを受信できないのでIntergerを使うことです.ParseIntなどを使用して形状を変更する必要があります.また、自身がエラー値を受け取るとエラーになるためIOエラー処理が投げ出される.

1.上昇距離、摺動距離、目標高さの上昇、下降、mが得られた。

		int up = Integer.parseInt(st.nextToken());
		int down = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());

時間制限のため、BufferReaderを使用し、StringTokenizerをスペースに分割し、NextTokenにロードします.Stringタイプなのでintタイプに変換しました

2.実際の移動距離(move)とmoveが無条件に発生した日付を求めるために、必要な変数(safem)を作成し、それを利用して私たちが探している最終日付を求める。

safem変数の説明を追加:ターゲット高さ-移動距離.例えば、4、2、21が入力された場合、21−4=>17が入力されたことを示す.この17は、17 mまでの実際の移動距離(move)が無条件に発生することを意味する.すなわち,17 mまでは無条件に4−2人2 m増加するので,安全m(17)/2(move)=>16が保証され,2 mごとに8日間移動する.それから16メートル、それに移動していた4メートルを加えて、21メートルか21メートルを超えると、翌日に着きます.21メートルに達しなければ、2日後に着きます.これらの内容を式で3番目に説明するday変数に分けます.

		int move = up - down; //실질적인 하루 이동 거리(올라간 거리 - 내려간 거리)
		int safe_m = m - up; //up+down이 무조건 일어나는 날들의 마지노선을 구해줄 때 사용
        if(safe_m == 0) {
			System.out.println(1);
			return;
		}

safem=0は目標高さを表します.上昇高さが0であれば、すぐに目標に達します.たとえば、7、4、7は、初日に7メートル上に進むと、目標を達成できます.この場合、1を直接印刷してメソッドを終了します.

3.dayでは、実際の移動距離を、魔道の刃を求める際に使用するsafemに割り当て、実際の移動距離の魔道を求める。(本説明は、上記「安全m変数の説明を追加する」セクションの内容です。)その後day変数に+up(高さ)(高さを上げると一日が過ぎた)を加え、直接目標高さに達したり超えたりしたら翌日に到着します。そうしないと翌日には到着せず、翌日に到着します。

が最後に翌日に到着できなかったのは、上記の例のように4、2、21と言えば17 mまでが安全であるため、8日間で2 mごとに16 mまで移動するからである.ここで2日目は4 m移動、16+4=>20 m、21 m未満、2 m滑って19 mから4 m移動、21 mに到着して終了です.つまり、最後のルート刃の高さと実際の移動距離の結果が同じであれば(例えば、2メートル移動ごとに、ちょうど17メートルに合えば翌日21メートルに到達するが、現実は16メートルで終わる.)翌日には到着できるのでそうではないかもしれません.

		 int day = safe_m / move;
		 if (day * move + up >= m) {
			System.out.println(day + 1);
		} else{
			System.out.println(day + 2);
		}

最後に式で翌日到着するか2日後に到着するかを手に入れた.

に感銘を与える

これは良い問題であり,スキャン以外のI/O手段を用い,処理速度の観点からも良い問題である.他の人も公式を1行に書く場合がありますが、これからもっと勉強して、もっと簡潔な公式を作る能力を高めたいと思います.
出典:白駿2869号https://www.acmicpc.net/problem/2869