結果

問題 No.1170 Never Want to Walk
ユーザー nc_researchnc_research
提出日時 2021-09-29 16:44:06
言語 Java21
(openjdk 21)
結果
TLE  
実行時間 -
コード長 2,326 bytes
コンパイル時間 3,406 ms
コンパイル使用メモリ 79,396 KB
実行使用メモリ 116,092 KB
最終ジャッジ日時 2024-07-16 12:20:49
合計ジャッジ時間 14,906 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 110 ms
46,512 KB
testcase_01 AC 117 ms
41,512 KB
testcase_02 AC 103 ms
40,120 KB
testcase_03 AC 104 ms
40,288 KB
testcase_04 AC 118 ms
41,336 KB
testcase_05 AC 118 ms
41,020 KB
testcase_06 AC 124 ms
41,472 KB
testcase_07 AC 114 ms
40,112 KB
testcase_08 AC 122 ms
41,400 KB
testcase_09 AC 118 ms
41,076 KB
testcase_10 AC 116 ms
41,128 KB
testcase_11 AC 124 ms
41,252 KB
testcase_12 AC 360 ms
51,620 KB
testcase_13 AC 581 ms
52,168 KB
testcase_14 AC 745 ms
55,192 KB
testcase_15 AC 437 ms
51,396 KB
testcase_16 AC 404 ms
52,712 KB
testcase_17 AC 620 ms
54,868 KB
testcase_18 AC 310 ms
49,492 KB
testcase_19 AC 368 ms
50,188 KB
testcase_20 AC 703 ms
54,800 KB
testcase_21 AC 363 ms
52,100 KB
testcase_22 TLE -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.Scanner;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.HashMap;

public class App 
{
    public static void main( String[] args )
    {
        // 1. 入力の受け取り
        Scanner scan = new Scanner(System.in);
        String first_line = scan.nextLine();
        String second_line = scan.nextLine();
        scan.close();

        // 2. 入力から，N，A，B，x.get(i)を抽出
        int n = Integer.valueOf(first_line.split(" ")[0]);
        int a = Integer.valueOf(first_line.split(" ")[1]);
        int b = Integer.valueOf(first_line.split(" ")[2]);
        ArrayList<Integer> x = new ArrayList<Integer>();
        String[] x_str = second_line.split(" ");
        for(int i = 0; i < x_str.length; i++){
            x.add(Integer.valueOf(x_str[i]));
        }

        // 3. 各駅iから1回以下で移動可能な駅リストを計算（計算量：o(N^2)）
        HashMap<Integer, HashSet<Integer>> can_move_from_index = new HashMap<Integer, HashSet<Integer>>();

        // 3.1 0回で移動可能な駅を格納
        for(int i = 0; i < x.size(); i++){
            can_move_from_index.put(i, new HashSet<Integer>());
            can_move_from_index.get(i).add(i);
        }
        // 3.2 1回で移動可能な駅を格納
        for(int i = 0; i < x.size(); i++){
            for(int j = i; j < x.size(); j++){
                if(x.get(j) - x.get(i) < a) continue;
                if(x.get(j) - x.get(i) > b) break;
                can_move_from_index.get(i).add(j);
                can_move_from_index.get(j).add(i);
            }
        }

        // 4. 各駅から2回以上で移動可能な駅リストの計算（計算量o(N^2)）
        for(int i = 0; i < x.size(); i++){
            for(int j = 0; j < x.size(); j++){
                if(can_move_from_index.get(i).contains(j)){
                    int size_before_add = can_move_from_index.get(i).size();
                    can_move_from_index.get(i).addAll(can_move_from_index.get(j));
                    int size_after_add = can_move_from_index.get(i).size();
                    if(size_before_add < size_after_add){
                        j = 0;
                    }
                }
            }
            System.out.println(can_move_from_index.get(i).size());
        }
    }
}
0