AOJ 0270 Modular Queryを解く

AIZU ONLINE JUDGE


単純にゴリ押し→ダメ 当たり前やな。

→まぁ解法思いつきませんわ

→解説スライド読む

→なるほどな、余りの区切り的なの探して枝刈り的な事をすればええのか

やってみる

AC


以下ソースコード

import java.util.Arrays;
import java.util.Scanner;

public class Main {
   //--- lt以下の要素を探索 ---//
   static int search(int[] c,int lt) {
      for(int i = lt; i >= 0; i--) {
         if(Arrays.binarySearch(c, i) >= 0) {
            return Arrays.binarySearch(c, i);
         }
      }
      return -1;
   }
   public static void main(String[] args) {
      Scanner stdIn = new Scanner(System.in);
      int N = stdIn.nextInt();
      int Q = stdIn.nextInt();
      int[] c = new int[N];
      for(int i = 0; i < N; i++) {
         c[i] = stdIn.nextInt();
      }
      Arrays.sort(c);
      for(int i = 0; i < Q; i++) {
         int max = 0;
         int q = stdIn.nextInt();
         for(int j = c.length-1; j >= 0; j--) {
            if(c[j] % q > max) max = c[j] % q;
            int tmp = search(c,c[j]-c[j]%q-1);
            if(tmp == -1) {
               break;
            }
            else {
               j = tmp+1;
            }
         }
         System.out.println(max);
      }

      

   }
}

参考解説
http://web-ext.u-aizu.ac.jp/pc-concours/2014/download/pastexam/2012final_editorial.pdf