プログラミングを上達させたい

プログラミングの勉強を始めた、情報学専攻の大学院生です。モチベーション維持のため、ブログに勉強したことを書いていきます。→就職。IT全然関係ない仕事をしています

北海道大学と日立のやつをやりました(AtCoder)

とってもとっても久々の更新。
なんか急にプログラミングしたい欲が出てきて、AtCoderにアクセスしてみたら、なんとマラソン型(っていうんですかね?)のコンテストをやっているではありませんか!
「Hokkaido Univ.& Hitachi 2nd New-concept Computing Contest 2017」というタイトルです。
上位50位は記念品をもらえるらしいとのことだったので、そこを目指してやってみました。


hokudai-hitachi2017-2.contest.atcoder.jp

グラフの問題です。
グラフVとグラフVembの頂点を対応させ、定められた採点方法でより高得点が出るようにしてください。というものです。

とりあえず、ちょっとずつ点を伸ばした、その過程を書いていきます。ちなみにJavaです。
また、僕のコードにはとってもとっても長い「テンプレート」があるのですが、毎回書くと長すぎ大明神なので、この記事の最後に書いています。

さてさて。

①"とりあえず提出"
こういうコンテストでは、とりあえず一回「形式に合っているだけ」の提出をします。
・出力が合っているか
・点数のノリはどんなもんか(上位との差などのノリを把握)
するためです。
今回は、Vの頂点 と Vembの頂点 を"番号が同じやつ1個ずつで割り当てる"という提出を初めにしました。
つまり、
Vの頂点1 - Vembの頂点1
Vの頂点2 - Vembの頂点2
・・・・
というわけですね。
こんなコードです。 ※テンプレート部分は省いているため、このコードだけでは動かない。注意。

public class Main {
  public static void main(String[] args) {
    InputReader sc = new InputReader(System.in);
 
    int v = sc.nextInt();
    int e = sc.nextInt();
 
    int[][] ve = new int[e][2];
    for(int i = 0; i < e; i++){
      ve[i][0] = sc.nextInt();
      ve[i][1] = sc.nextInt();
    }
 
    int vemb = sc.nextInt();
    int eemb = sc.nextInt();
 
    int[][] veemb = new int[eemb][2];
    for(int i = 0; i < eemb; i++){
      veemb[i][0] = sc.nextInt();
      veemb[i][1] = sc.nextInt();      
    }
 
    for(int i = 0; i < v; i++){
      System.out.print("1 ");
      System.out.println(i + 1);
    }
  }

これの点数が676000点でした。高いのやら低いのやら。

②ちょっとずつコードいじる その1
ガッツリ点を取りに行くための方針を探るため、コードをちょっといじります。
ハッと思いついた、"番号が同じやつ1個ずつで割り当てる、ただしVのラストのやつにはVembの残り全てプレゼント"を書きました。

これはつまり、Vが頂点数10, Vembが頂点数25だとしたら、
Vの頂点1 - Vembの頂点1
Vの頂点2 - Vembの頂点2
・・・・
Vの頂点9 - Vembの頂点9
Vの頂点10 - Vembの頂点10,11,12,13,・・・,24,25
ということです。
これで、少しは点があがるのでは・・・?

public class Main {
  public static void main(String[] args) {
    InputReader sc = new InputReader(System.in);
 
    int v = sc.nextInt();
    int e = sc.nextInt();
 
    int[][] ve = new int[e][2];
    for(int i = 0; i < e; i++){
      ve[i][0] = sc.nextInt();
      ve[i][1] = sc.nextInt();
    }
 
    int vemb = sc.nextInt();
    int eemb = sc.nextInt();
 
    int[][] veemb = new int[eemb][2];
    for(int i = 0; i < eemb; i++){
      veemb[i][0] = sc.nextInt();
      veemb[i][1] = sc.nextInt();      
    }
 
    for(int i = 0; i < v - 1; i++){
      System.out.print("1 ");
      System.out.println(i + 1);
    }
    System.out.print(vemb - v + 1);
    for(int i = v; i <= vemb; i++){
      System.out.print(" ");
      System.out.print(i);
    }
 
    System.out.println("");
//1つの頂点に、順番に1つの頂点を
//ただし、最後のやつには、残った全部の頂点を 
  }

ドキドキの採点結果は・・・?なんと667833点と、少しダウン・・・
なぜ?と思って見返していると、採点基準の4番目「割り当てに使ったVembの頂点数を点数から引く」を見落としていました。
適当に頂点を割り当てまくるのはよくない、とのこと。


③ちょっとずつコードいじる その2
適当に割り当てまくるのがよくないなら、「ちゃんと実力者に多く割り当てる」にしてみようと考えました。
実力者=辺の数が多い者、ということで、「Vの、辺の数の割合に応じて、Vembの割り当ての数を決める」&「割り当ての方法に関しては、Vembを外から渦巻き状に割り当てていく」ことにしました。
コードはこんな感じ。

public class Main {
  public static void main(String[] args) {
    InputReader sc = new InputReader(System.in);
 
    int v = sc.nextInt();
    int e = sc.nextInt();
 
    int[][] ve = new int[e][2];
    int[] ecount = new int[v];
    for(int i = 0 ; i < v; i++){
      ecount[i] = 0;
    }
    for(int i = 0; i < e; i++){
      ve[i][0] = sc.nextInt();
      ve[i][1] = sc.nextInt();
      ecount[ve[i][0] - 1]++;
      ecount[ve[i][1] - 1]++;
    }
 
    int vemb = sc.nextInt();
    int eemb = sc.nextInt();
 
 
 
    int[][] veemb = new int[eemb][2];
    for(int i = 0; i < eemb; i++){
      veemb[i][0] = sc.nextInt();
      veemb[i][1] = sc.nextInt();      
    }
 
    //入力終わり
 
 
    //ぐるぐる回る順番の下準備
 
    int vsize_plus2 = (int)Math.sqrt(vemb) + 2;
    int[][] uzumaki_array = new int[vsize_plus2][vsize_plus2];
    for(int i = 0; i < vsize_plus2; i++){
      for(int j = 0; j < vsize_plus2; j++){
        if(i * j == 0 || i == vsize_plus2 - 1 || j == vsize_plus2 - 1){
          uzumaki_array[i][j] = 0;
        }else{
          uzumaki_array[i][j] = (i - 1) * (vsize_plus2 - 2) + j;
        }
      }
    }
 
    int[] uzumaki_numbers = new int[vemb];
    int[] tate = new int[4];
    int[] yoko = new int[4];
    tate[0] = 0; tate[1] = 1; tate[2] = 0; tate[3] = -1;
    yoko[0] = 1; yoko[1] = 0; yoko[2] = -1; yoko[3] = 0;
 
    int index = 0;
    int gyou = 1;
    int retsu = 1;
    int count = 0;
    while(index < vemb){
      while(uzumaki_array[gyou][retsu] > 0){
        uzumaki_numbers[index] = uzumaki_array[gyou][retsu];
        uzumaki_array[gyou][retsu] = 0;
        gyou += tate[count % 4];
        retsu += yoko[count % 4];
        index++;
      }
      gyou -= tate[count % 4];
      retsu -= yoko[count % 4];
      count++;
      gyou += tate[count % 4];
      retsu += yoko[count % 4];
    }
 
 
//各Vの頂点に、辺の数に応じてどれくらいVembの頂点をつけてあげるかざっくり決める
//うずまき状で
    int[] get_ratio = new int[v];
    for(int i = 0; i < v; i++){
      get_ratio[i] = (ecount[i] * vemb) / (2 * e);
      if(get_ratio[i] == 0){
        get_ratio[i] = 1; //空集合を作らないため
      }
    }
 
    int ansindex = 0;
    for(int i = 0; i < v - 1; i++){
      System.out.print(get_ratio[i]);
      for(int j = 0; j < get_ratio[i]; j++){
        System.out.print(" ");
        System.out.print(uzumaki_numbers[ansindex]);
        ansindex++;
      }
      System.out.println("");
    }
    System.out.print(vemb - ansindex);
    for(; ansindex < vemb; ansindex++){
      System.out.print(" ");
      System.out.print(uzumaki_numbers[ansindex]);
    }
    System.out.println("");
  }

しかし得点は615033点と、さらにダウン・・・なんやねんホンマ・・・
頂点を複数個割り当てる場合、相当上手く割り当てんと減点の方が大きくなるのだろうな、と予想。
ここからは"Vの1点-Vembの1点 を対応させる"方針でやっていきます。

④うずまきぐるぐる
1-1対応させて、とりあえず最初の回答を越えたい・・・!
Vembにおいて、端っこの点より中心の点の方が隣接頂点が多いということで、
『Vに置いて頂点が多い点に、Vembの中心から渦巻き状で割り当てていく』という方針でやってみました。

public class Main {
  public static void main(String[] args) {
    InputReader sc = new InputReader(System.in);
 
    int v = sc.nextInt();
    int e = sc.nextInt();
 
    int[][] ve = new int[e][2];
    int[] ecount = new int[v];
    for(int i = 0 ; i < v; i++){
      ecount[i] = 0;
    }
    for(int i = 0; i < e; i++){
      ve[i][0] = sc.nextInt();
      ve[i][1] = sc.nextInt();
      ecount[ve[i][0] - 1]++;
      ecount[ve[i][1] - 1]++;
    }
 
    int vemb = sc.nextInt();
    int eemb = sc.nextInt();
 
 
 
    int[][] veemb = new int[eemb][2];
    for(int i = 0; i < eemb; i++){
      veemb[i][0] = sc.nextInt();
      veemb[i][1] = sc.nextInt();      
    }
 
    //入力終わり
 
 
    //ぐるぐる回る順番の下準備
 
    int vsize_plus2 = (int)Math.sqrt(vemb) + 2;
    int[][] uzumaki_array = new int[vsize_plus2][vsize_plus2];
    for(int i = 0; i < vsize_plus2; i++){
      for(int j = 0; j < vsize_plus2; j++){
        if(i * j == 0 || i == vsize_plus2 - 1 || j == vsize_plus2 - 1){
          uzumaki_array[i][j] = 0;
        }else{
          uzumaki_array[i][j] = (i - 1) * (vsize_plus2 - 2) + j;
        }
      }
    }
 
    int[] uzumaki_numbers = new int[vemb];
    int[] tate = new int[4];
    int[] yoko = new int[4];
    tate[0] = 0; tate[1] = 1; tate[2] = 0; tate[3] = -1;
    yoko[0] = 1; yoko[1] = 0; yoko[2] = -1; yoko[3] = 0;
 
    int index = 0;
    int gyou = 1;
    int retsu = 1;
    int count = 0;
    while(index < vemb){
      while(uzumaki_array[gyou][retsu] > 0){
        uzumaki_numbers[index] = uzumaki_array[gyou][retsu];
        uzumaki_array[gyou][retsu] = 0;
        gyou += tate[count % 4];
        retsu += yoko[count % 4];
        index++;
      }
      gyou -= tate[count % 4];
      retsu -= yoko[count % 4];
      count++;
      gyou += tate[count % 4];
      retsu += yoko[count % 4];
    }
 
 
//各Vの頂点に、辺の数に応じてどれくらいVembの頂点をつけてあげるかざっくり決める
//うずまき状で
//中心からにするため、uzumaki_numbersを逆順にならびかえ
//ほんで、頂点数が多い順に中心から1つずつ割り当てていく
//極端なグラフには弱そうやけど・・・
 
    int[] keep = new int[vemb];
    for(int i = 0; i < vemb; i++){
      keep[i] = uzumaki_numbers[i];
    }
    for(int i = 0; i < vemb; i++){
      uzumaki_numbers[i] = keep[vemb - i - 1];
    }
    
    int[] ansArray = new int[v];
    for(int i = 0; i < v; i++){
      ansArray[i] = 0;
    }
    
    for(int ind = 0; ind < v; ind++){
      int max_e = -1;
      int max_index = -1;
      for(int i = 0; i < v; i++){
        if(ansArray [i] == 0 && ecount[i] > max_e){
          max_e = ecount[i];
          max_index = i;
        }
      }
      ansArray[max_index] = uzumaki_numbers[ind];
    }
 
    for(int i = 0; i < v; i++){
      System.out.print("1 ");
      System.out.println(ansArray[i]);
    }
 
  }

743400点!!!最初の点数をやっとこさ、やっとこさ超えたぞー!!!
ここからどうしようか・・・

⑤貪欲法っぽいこと
ここから頑張って賢いことしようとします。
まず、Vの頂点で辺が多いモノから順に、
「すでに割り当て済んでるやつだけの話で、もっとも点数が高くなるようにする」
という流れで割り当てを決めていきます。
貪欲法というやつみたいなことです。これが厳密に貪欲法になってるかはわかりません。

public class Main {
  public static void main(String[] args) {
    InputReader sc = new InputReader(System.in);
 
    int v = sc.nextInt();
    int e = sc.nextInt();
 
    int[][] ve = new int[e][2];
    int[] ecount = new int[v];
    for(int i = 0 ; i < v; i++){
      ecount[i] = 0;
    }
    for(int i = 0; i < e; i++){
      ve[i][0] = sc.nextInt();
      ve[i][1] = sc.nextInt();
      ecount[ve[i][0] - 1]++;
      ecount[ve[i][1] - 1]++;
    }
    
    int[] largerArray = new int[v];
    boolean[] checkArray = new boolean[v];
    for(int i = 0; i < v; i++){
      checkArray[i] = false;
    }
    for(int i = 0; i < v; i++){
      int maxind = -1;
      int nowmax = -1;
      for(int j = 0; j < v; j++){
        if(ecount[j] > nowmax && !checkArray[j]){
          nowmax = ecount[j];
          maxind = j;
        }
      }
      largerArray[i] = maxind;
      checkArray[maxind] = true;
    }
    
 
    
 
    int vemb = sc.nextInt();
    int eemb = sc.nextInt();
 
 
 
    int[][] veemb = new int[eemb][2];
    for(int i = 0; i < eemb; i++){
      veemb[i][0] = sc.nextInt();
      veemb[i][1] = sc.nextInt();      
    }
 
    //入力終わり
 
//一番辺の数が多い頂点を、Vembのど真ん中の点と対応させる
//それ以降は、辺の数が多い順に、Vembの1点と対応させていく
//その際、"その時点で一番大きい点数が取れるところ"に置いていく
//V-Vembの対応は1点-1点にするぜ
//貪欲法というやつやね
//割り当てが終わったVembの頂点をメモっておかないとね
 
    int max_e_ind = -1;
    int max_e = -1;
 
    for(int i = 0; i < v; i++){
      if(ecount[i] > max_e){
        max_e_ind = i;
        max_e = ecount[i];
      }
    }
 
 
    int[] ansArray = new int[v];
    for(int i = 0; i < v; i++){
      ansArray[i] = -1;
    }
    
 
    
    if(vemb % 2 == 0){
      ansArray[max_e_ind] = (vemb - (int)Math.sqrt(vemb))/ 2 - 1;
    }else{
      ansArray[max_e_ind] = (vemb + 1) / 2 - 1;
    }//一番辺が多い頂点に、Vembの中心を割り当て。
 
/*
Vemb内の2点で引き分けが出た場合、"より中心に近い方が勝ち"としたい
    int center_x = ansArray[max_e_ind] % (int)Math.sqrt(vemb);
    int center_y = ansArray[max_e_ind] / (int)Math.sqrt(vemb);
*/
    
/*
ここから
1.まだ割り当てをやっていないVの頂点の中で、一番辺が多いのを選ぶ
2.Vembの、割り当てられてない頂点を全部試して、一番点が高いやつに割り当てる
の繰り返し
*/
 
    int ippen = (int)Math.sqrt(vemb);
 
 
    for(int counter = 1; counter < v; counter++){
      int now_max_e_ind = largerArray[counter];//これで、次に割り当てをするVの頂点を決める
 
      
      int best_ind = -1;
      int best_score = -1;
      for(int i = 0; i < vemb; i++){//もしこのi in Vembの点を選んだ場合、で得点計算
        boolean check = false;
        for(int j = 0; j < v; j++){
          if(ansArray[j] == i){check = true;}
        }//もう割り当て住んでるやつはスキップ
        if(check){continue;}
        
        int now_score = 0;
        for(int j = 0; j < e; j++){//Vの各辺に対して
          int another_point = 0;
          if(ve[j][0] == now_max_e_ind + 1 && ansArray[ve[j][1] - 1] >= 0){
            another_point = ansArray[ve[j][1] - 1];
          }else if(ve[j][1] == now_max_e_ind + 1 && ansArray[ve[j][0] - 1] >= 0){
            another_point = ansArray[ve[j][0] - 1];
          }else{continue;}
          
          int now_point_x = i % ippen;
          int now_point_y = i / ippen;
          int another_point_x = another_point % ippen;
          int another_point_y = another_point / ippen;
          
          if(Math.abs(now_point_x - another_point_x) <= 1 && Math.abs(now_point_y - another_point_y) <= 1){
            now_score += 100;
          }
        }
 
        if(now_score > best_score){
          best_score = now_score;
          best_ind = i;
        }
      }
      ansArray[now_max_e_ind] = best_ind;
    }
 
    for(int i = 0; i < v; i++){
      System.out.print("1 ");
      System.out.println(ansArray[i] + 1);
    }
 
  }

ドキドキの点数は・・・
大幅に伸びて1346200点!!約2倍!!!
ただ、50位には遠く及ばず・・・(コンテスト終了の1日前の夜10時の時点で68位)
くそう!





僕のテンプレート

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.TreeSet;
 
 
 
public class Main {
  public static void main(String[] args) {
    InputReader sc = new InputReader(System.in);
 
//ここにいっぱいコードを書く
  }
 
 //ここからテンプレ
  static class InputReader {
      private InputStream stream;
      private byte[] buf = new byte[1024];
      private int curChar;
      private int numChars;
      private SpaceCharFilter filter;
 
      public InputReader(InputStream stream) {
          this.stream = stream;
      }
 
      public int next() {
          if (numChars == -1)
              throw new InputMismatchException();
          if (curChar >= numChars) {
              curChar = 0;
              try {
                  numChars = stream.read(buf);
              } catch (IOException e) {
                  throw new InputMismatchException();
              }
              if (numChars <= 0)
                  return -1;
          }
          return buf[curChar++];
      }
 
      public String nextStr() {
        int c = next();
        while(isSpaceChar(c)){c = next();}
        StringBuffer str = new StringBuffer();
        do{
          str.append((char)c);
          c = next();
        }while(!isSpaceChar(c));
        return str.toString();
      }
 
      public char nextChar() {
        int c = next();
        while(isSpaceChar(c)){c = next();}
        char ret;
        do{
          ret = (char)c;
          c = next();
        }while(!isSpaceChar(c));
        return ret;
      }
 
      public int nextInt() {
          int c = next();
          while (isSpaceChar(c))
              c = next();
          int sgn = 1;
          if (c == '-') {
              sgn = -1;
              c = next();
          }
          int res = 0;
          do {
              if (c < '0' || c > '9')
                  throw new InputMismatchException();
              res *= 10;
              res += c - '0';
              c = next();
          } while (!isSpaceChar(c));
          return res * sgn;
      }
 
      public boolean isSpaceChar(int c) {
          if (filter != null)
              return filter.isSpaceChar(c);
          return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
      }
 
      public interface SpaceCharFilter {
          public boolean isSpaceChar(int ch);
      }
  }
}