結果

問題 No.1170 Never Want to Walk
ユーザー nc_research
提出日時 2021-09-29 16:44:06
言語 Java
(openjdk 23)
結果
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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 20 TLE * 1 -- * 16
権限があれば一括ダウンロードができます

ソースコード

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