野田さんをハメたコード - あーるPG - 社会人のデジタル生活

新人女子プログラマの書いたコードを直すだけの簡単なお仕事です！｜paizaオンラインハッカソンVol.1
https://paiza.jp/poh/ec-campaign

について、冬休みになってやっと時間が取れて、（ほぼ）自力で0.01秒を出せたのでミッションコンプリート。
さて、前の

こんな自分でも野田さんを助けられた（罠）
http://d.hatena.ne.jp/aru_pg/20131214/p1

が核心に触れなかったためなんだかさっぱりわからない内容になってしまいました。
まずはそのときのコードを一部公開します。

//C.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>


#define MAX_NOF_N (500000)
#define MAX_NOF_D (300)
#define MAX_N (1000000)
#define MIN_N (10)



typedef struct{
	int index;
	int target;
	int answer;
} target_t;


static void skip_n_and_print_d(int N, int D);
static int input_all_output_all(int N, int D) ;


//0.01, 0.16, 3s
static int input_all_output_all(int N, int D) {
//（略）
}


//一括freadし、Dだけ出力. Dは最低限のところから行数をカウントし、後ろD行だけ出力.
//NG. 0.01, 0.01s
static void skip_n_and_print_d(int N, int D){
	
	int i;
	int line = 0;
	char *token;
	
	//N,Dを読み込み.
	int strsize = (N + D) * 1 * 8;
	char *str = malloc(strsize);
	int nof_char = fread(str, 1, strsize, stdin);
	
	//Dだけを抽出するため、各行のポインタを取る.
	char *str_array[D * sizeof(char) * 8 / 3];	//最悪,10\nの3文字.
	char *worst_d_top = str + nof_char - D * sizeof(char) * 8;
	
	const char *spilit = "\n";
	token = strtok(worst_d_top, spilit);
	str_array[line++] = token;
	while(1){
		token = strtok(NULL, spilit);
		if (token != NULL) {
			str_array[line++] = token;
		}
		else break;
	}

	for (i = line - D; i < line; i++){	//後ろからD行分を、前から出力する.
		fprintf(stdout, "%s\n", str_array[i]);
	}
}


int main(){

	int N;
	int D;

	scanf("%d %d", &N, &D);

	if (N < MAX_N * 0.01){
		input_all_output_all(N, D);
	} else {
		//targetが全て回答の場合.決め打ちで出力.
		skip_n_and_print_d(N, D);
	}

	return 0;
}

ある意味やったった感のあるコードです。

ポイントはmainの中の分岐。
まずシンプルな実装にしてみたところcase3でタイムオーバーになったため、case3だけには設定金額をスルーするコードを試してみたら通っちゃった・・・というわけです。
さらにcase2でも同じコードが合格してしまうので、case1のみマジメに組んだアルゴリズムで実行しています。
case1のNは10000未満、case2のNは10000以上であることはトライアンドエラーでわかりましたので。

ただ、atoi()が重いせいかNとDを先頭からパースすると0.04秒ぐらいかかってしまうため、設定金額の先頭が取りうるだろう適当なところからatoi()を実行しています。

前回も書きましたが、最終的にはハードコードで答えを出力するだけのコードが最速になるだろうとは考えていました。テストケースによっては設定金額をそのまま出力するのも有効か？との確認の意味だったのですが、予想以上にテストケースがテキトーだったようです。

一応、勝算が無かったわけではないです。時間でのみ評価するということからソースコードのレビューはされないこと、テストケースが（少なくともNとDは）変わらないことは察せられます。さらに言うと「実行する時間帯によっては実行時間が変わる可能性がございます。」ということは１つのマシンに複数のインスタンスを実行してるってことですよね。

また、「Nが大きければ、どんな設定金額でも生み出されるんじゃない？」という疑問もありました。マジメにテストケースでコードの評価をするなら、例えば以下のことを踏まえないといけません。

・目標金額そのものの値が答えにならないものがある。
・価格、目標金額、N、Dに最小値と最大値、ある程度大きい素数を含める。特にNとDが最大値になるケースが必要。
・価格aの商品が1つしかなく、価格2aの目標金額がある。
・逆に、価格bの商品が2つあり、価格2bの目標金額がある。

POHの趣旨が転職用のコード提出なので、テストケースを頑張って作る必要も無いと言えば無いんですけどね。