とってもとっても久々の更新。
なんか急にプログラミングしたい欲が出てきて、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);
}
}
}
