JOI2017/2018 予選参加記

競技プログラミング関係

結果

ABCEの4完(400点)でした うれしいね
コードを晒します

A 鉛筆 (Pencils)

int main() {
	int n, a, b, c, d;
	cin >> n >> a >> b >> c >> d;
	int ap = n / a;
	int cp = n / c;
	if (n % a != 0) {
		ap++;
	}
	if (n % c != 0) {
		cp++;
	}
	if (b* ap > d * cp) {
		cout << d* cp << endl;
	}
	else {
		cout << b * ap << endl;
	}
}

はい

B 双六 (Sugoroku)

int main() {
	int n, a, ans = 0, cnt = 0;
	cin >> n;
	REP(i, n) {
		cin >> a;
		if (a == 1) {
			cnt++;
		} else {
			ans = max(ans, cnt);
			cnt = 0;
		}
	}
	ans = max(ans, cnt);
	ans++;
	cout << ans << endl;
}

Aより実装楽で面白いね

C 幹線道路 (Trunk Road)

int main() {
	int h, w;
	int num[25][25];
	cin >> h >> w;
	REP(i, h) {
		REP(j, w) {
			cin >> num[i][j];
		}
	}
	int ans = INF;
	REP(a, h) {
		REP(b, w) {
			int tmp = 0;
			REP(i, h) {
				REP(j, w) {
					tmp += min(abs(i - a), abs(j - b)) * num[i][j];
				}
			}
			ans = min(ans, tmp);
		}
	}
	cout << ans << endl;
}

一瞬迷ったけど普通に全探索

D 水ようかん (Mizuyokan)

わけがわからないよ
bit全探索を書こうとするも書けないので0点

E 森林伐採（Deforestation）

int dx4[4] = {0,1,0,-1}, dy4[4] = {-1,0,1,0};
 
int main() {
	ll dp[31][31];
	dp[0][0] = 0;
	ll a[31][31];
	ll dist[31][31];
	ll h, w;
	cin >> h >> w;
	REP(i, 31) {
		REP(j, 31) {
			dist[i][j] = -1;
		}
	}
	dist[0][0] = 0;
	REP(i, h) {
		REP(j, w) {
			cin >> a[i][j];
		}
	}
	queue<P> que;
	que.push(P(0, 0));
	while (!que.empty()) {
		auto p = que.front(); que.pop();
		int di = p.first; int dj = p.second;
		REP(i, 4) {
			int nx = di + dx4[i]; int ny = dj + dy4[i];
			if (nx < 0 || ny < 0 || nx >= h || ny >= w) continue;
            ll COST = dp[di][dj] + (dist[di][dj] * 2 + 1) * a[nx][ny];
			if (dp[nx][ny] == COST && dist[nx][ny] > dist[di][dj] + 1) {
				dist[nx][ny] = min(dist[nx][ny], dist[di][dj] + 1);
				que.push(P(nx, ny));
			}else if (dist[nx][ny] == -1 || dp[nx][ny] > COST) {
				dp[nx][ny] = COST;
				dist[nx][ny] = dist[di][dj] + 1;
				que.push(P(nx, ny));
			}
		}
	}
	cout << dp[h - 1][w - 1] << endl;
}

拡張Dijkstraっていう分類の問題らしい
BFSをして特定のマスまでのコストとそのときの(0, 0)からの距離を持つだけ
なんでAC出来たんでしょうか 僕にも分かりません

追記

上のコードが限界だったのでちょっと手直ししました(2018/11/26)

int dx4[4] = {0,1,0,-1}, dy4[4] = {-1,0,1,0};
 
int main() {
    // 入力
    ll dp[31][31], a[31][31], dist[31][31];
    ll h, w;
    cin >> h >> w;
    REP(i, 31) {
        REP(j, 31) {
            dist[i][j] = -1;
        }
    }
    REP(i, h) {
        REP(j, w) {
            cin >> a[i][j];
        }
    }

    dist[0][0] = 0; // (0, 0)までの距離は0
    dp[0][0] = 0; // (0, 0)までのコストは0
    queue<P> que;
    que.push(P(0, 0)); // (0, 0)からスタート

    while (!que.empty()) {
        auto p = que.front(); que.pop();
        int x = p.first; int y = p.second; // もともといたマス

        REP(i, 4) {
            int nx = x + dx4[i]; int ny = y + dy4[i]; //四近傍で回す
            if (nx < 0 || ny < 0 || nx >= h || ny >= w) continue; // 領域内か判定
            ll cost = dp[x][y] + (dist[x][y] * 2 + 1) * a[nx][ny]; // https://twitter.com/6Lgug/status/1066718346509348864

            // 行っていないマスもしくは行っているけど現在のコストのほうが少ないなら更新
            if (dist[nx][ny] == -1 || dp[nx][ny] > cost) {
                dp[nx][ny] = cost;
                dist[nx][ny] = dist[x][y] + 1; // 距離は前のマスまでの距離+1なので
                que.push(P(nx, ny));
                continue;
            }

            // コストが同じでも距離が短いなら更新((nx, ny)以降のマスまでの最小コストが減りうるので)
            if(dp[nx][ny] == cost && dist[nx][ny] > dist[x][y] + 1) {
                dist[nx][ny] = dist[x][y] + 1;
                que.push(P(nx, ny));
            }
        }
    }
    cout << dp[h - 1][w - 1] << endl; // 出力
}

F L番目のK番目の数 (LthKthNumber)

全探索しようとしましたが書けませんでした

感想

3完+部分点しようと思っていたので嬉しい
が部分点も取れない実装力の無さには萎えました
(本戦行けるといいなあ...)

追記

本選行きます
0完太陽☼にならないようにがんばるぞい