はじめに
レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】(以下，100問精選)があまりにも秀逸な記事だったので，これを基にプログラミングの勉強をしようと思います．100問精選の記事には，練習問題として100問掲載されているので，C言語で100問分を解いてみます．C言語でAtCoderを解いてみた！という記事は少ないため，この記事が何等かの形で参考になれば幸いです．また，具体的なテクニックについての話も今後記事にしていきたいと思います(例えば，競プロでのC言語の入出力周りの実装方法など)．
ちなみに，pythonで100問精選を解かれている方もいるそうです
→【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part1/22】
注意！
この記事には，間違い/非効率的なコードが多く含まれている可能性があります．ですが，ACをとれることは確認済です．
問題1-10
1
問題のポイント
scanf, printfの基本的な使い方を覚える
簡単な全探索を行う
解答
#include <stdio.h>
int main(void)
{
int x, y;
int cnt;
int sum;
while(1){
scanf("%d%d",&y, &x);
if(x == 0 && y == 0){
break;
}
cnt = 0;
for(int i = 1; i <= y; i++){
for(int j = i + 1; j <= y; j++){
for(int k = j + 1; k <= y; k++){
sum = i + j + k;
if(sum == x){
cnt++;
}
}
}
}
printf("%d\n",cnt);
}
return 0;
}
2
問題のポイント
約数を求める
%を用いた剰余の計算
割り切れるかどうかの判定
解答
#include<stdio.h>
int main(void){
int N;
scanf("%d", &N);
int cnt = 0;
for(int i = 1;i <= N; i = i+2){
int yakusu_cnt;
yakusu_cnt = 0;
for(int j = 1;j <= i;j++){
if(i % j == 0){
yakusu_cnt++;
}
}
if(yakusu_cnt == 8){
cnt++;
}
}
printf("%d\n",cnt);
return 0;
}
3
問題のポイント
文字列の入力の処理
(解法によっては)文字列の長さの調べ方
解答
#include <stdio.h>
#include <string.h>
int main(int argc, char *args[])
{
char s[10];
scanf("%s", s);
//文字列の長さを調べる
int n;
n = strlen(s);
int ans = 0;
int cnt = 0;
for(int i=0;i < n;i++){
if(s[i] == 'A' || s[i] == 'C' ||s[i] == 'G' ||s[i] == 'T' ){
cnt++;
}
else{
cnt = 0;
}
if(ans < cnt){
ans = cnt;
}
}
printf("%d\n", ans);
return 0;
}
4
問題のポイント
max関数を定義する
桁落ち対策(long int，long long int を用いる)
long int を用いるとき，printf("%ld", n);のように%ldとする(%dではだめ)
解答
#include<stdio.h>
int max(int a, int b){return a > b ? a : b;}
int main(void){
int n, m;
scanf("%d%d", &n, &m);
int a[n][m];
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
scanf("%d", &a[i][j]);
}
}
long int ans, score;
ans = 0;
for(int i = 0; i < m; i++){
for(int j = i + 1; j < m; j++){
score = 0;
for(int k = 0; k < n; k++){
score += max(a[k][i], a[k][j]);
}
if(score > ans){
ans = score;
}
}
}
printf("%ld", ans);
return 0;
}
5
問題のポイント
工夫して全探索を行う
解答
#include<stdio.h>
int min(int a, int b){return a < b ? a : b;}
int max(int a, int b){return a > b ? a : b;}
int main(void){
int a, b, c, x, y;
scanf("%d%d%d%d%d", &a, &b, &c, &x, &y);
//ABピザを使わない場合の値段
int notAB_price = a * x + b * y;
//ABピザのみの場合の値段
int all_AB = c * max(x, y) * 2;
//ABピザを廃棄がないように買い，足りない分はAピザもしくはBピザ単体で買う場合の値段
int withAB_price;
withAB_price = c * min(x, y) * 2;//ABピザの値段
if(x < y){
withAB_price += (y - x) * b;//Bピザの必要枚数が多い場合は買い足す
}else if(y < x){
withAB_price += (x - y) * a;
}
int ans = min(withAB_price, min(notAB_price, all_AB));
printf("%d\n", ans);
return 0;
}
6
問題のポイント
文字列の扱いに慣れる
複数行の文字列入力の対処法
解答
#include<stdio.h>
#include <stdlib.h>
int max(int a, int b){return a > b ? a : b;}
int main(void){
int n;
scanf("%d", &n);
char a[30001] = {};
scanf("%s", a);
int ans = 0;
for(int i = 0;i < 10; i++){
for(int j = 0;j < 10;j++){
for(int k = 0; k < 10; k++){
int cnt;
cnt = 0;
for(int l = 0;l < n;l++){
if(a[l] == i + '0' && cnt == 0){
cnt++;
}else if(a[l] == j + '0' && cnt == 1){
cnt++;
}else if(a[l] == k + '0' && cnt == 2){
cnt++;
}
if(cnt == 3){
ans++;
break;
}
}
}
}
}
printf("%d\n", ans);
return 0;
}
7
問題のポイント
二分探索，ソート，ビットマップなどを用いた計算時間とメモリを意識した実装
解答
#include<stdio.h>
#include<stdlib.h>
int max(a, b){return a > b ? a : b;}
int isHani(a, b){
if((a < 0) || (a > 5000)){
return 0;
}
if((b < 0) || (b > 5000)){
return 0;
}
return 1;
}
short int dot[5001][5001];
short int a[3000], b[3000];
int main(void){
int n;
scanf("%d", &n);
for(int i = 0; i < n; i++){
scanf("%d%d", &a[i], &b[i]);
}
for(int i = 0; i < 5001; i++){
for(int j = 0; j < 5001; j++){
dot[i][j] = 0;
}
}
for(int i = 0; i < n; i++){
dot[a[i]][b[i]] = 1;
}
int ans = 0;
int a31, b31, a41, b41;
int a32, b32, a42, b42;
for(int i = 0; i < n; i++){
for(int j = i + 1; j < n; j++){
a31 = -b[j] + b[i] + a[i];
b31 = a[j] - a[i] + b[i];
a41 = a31 + a[j] - a[i];
b41 = b31 + b[j] - b[i];
a32 = b[j] - b[i] + a[i];
b32 = a[i] - a[j] + b[i];
a42 = a32 + a[j] - a[i];
b42 = b32 + b[j] - b[i];
if(isHani(a31, b31) && isHani(a41, b41)){
if(dot[a31][b31] && dot[a41][b41]){
ans = max(ans, (a[i] - a[j]) * (a[i] - a[j]) + (b[i] - b[j]) * (b[i] - b[j]));
}}
if(isHani(a32, b32) && isHani(a42, b42)){
if(dot[a32][b32] && dot[a42][b42]){
ans = max(ans, (a[i] - a[j]) * (a[i] - a[j]) + (b[i] - b[j]) * (b[i] - b[j]));
}}
}
}
printf("%d\n",ans);
return 0;
}
8
問題のポイント
sortの方法
abs関数の使い方
解答
#include <stdio.h>
#include <stdlib.h>
int max(int a, int b){return a > b ? a : b;}
int compare_int(const void *a, const void *b)
{
return *(long long int*)a - *(long long int*)b;
}
int main(void)
{
int n;
scanf("%d", &n);
long long int a[30], b[30];
int i;
for(i = 0; i < n; i++){
scanf("%lld%lld", &a[i], &b[i]);
}
qsort(a, n, sizeof(long long int), compare_int);
qsort(b, n, sizeof(long long int), compare_int);
int med_n;
if(n % 2 == 0){
med_n = n / 2;
}else
{
med_n = (n - 1) / 2;
}
int ent = a[med_n], ext = b[med_n];
long long int ans = 0;
for(i = 0; i < n; i++){
ans += abs(ent - a[i]) + (b[i] - a[i]) + abs(ext - b[i]);
}
printf("%lld\n", ans);
return 0;
}
9
問題のポイント
どのようにfor文を回すと効率的かを方針立てる
解答
#include <stdio.h>
int main(void){
int m;
scanf("%d", &m);
int i;
int sx[200], sy[200];
for(i = 0; i < m; i++){
scanf("%d%d", &sx[i], &sy[i]);
}
int n;
scanf("%d", &n);
int hx[1000], hy[1000];
for(i = 0; i < n; i++){
scanf("%d%d", &hx[i], &hy[i]);
}
int j, k, mov_x, mov_y, flag;
for(i = 0; i < n; i++){
//sx[i]とhx[j]を一致させる
mov_x = hx[i] - sx[0];
mov_y = hy[i] - sy[0];
//移動量の候補は出たので，移動量に対して本当に星座が一致するか確認
for(j = 1; j < m; j++){
flag = 0;
for(k = 0; k < n; k++){
if(sx[j] + mov_x == hx[k] && sy[j] + mov_y == hy[k]){
flag = 1;
break;
}
}
if(flag == 0){
break;
}
if(j == m - 1){
printf("%d %d\n", mov_x, mov_y);
return 0;
}
}
}
}
10
問題のポイント
真面目にbit全探索で行うと，TLEが出た(ただ，工夫次第で回避できるかも)
制限時間内に解いている人の解答を見ると，再帰関数，DPを用いているため，満点を取るには他の手法を用いるとよい
解答
bit全探索によるコード(TLE)
#include <stdio.h>
#include <stdlib.h>
int compare_int(const void *a, const void *b)
{
return - *(int*)a + *(int*)b;
}
int main(void){
int n, a[20], q, m[200], sum, isprint, ii, bit, i;
scanf("%d", &n);
for(i = 0; i < n; i++){
scanf("%d", &a[i]);
}
scanf("%d", &q);
for(i = 0; i < q; i++){
scanf("%d", &m[i]);
}
qsort(a, n, sizeof(int), compare_int);
for(ii = 0; ii < q; ii++){
isprint = 0;
for(bit = 0; bit < (1<<n); ++bit){
sum = 0;
for (i = 0; i < n; ++i) {
if (bit & (1<<i)){
sum += a[i];
if(sum >= m[ii]){
break;
}
}
}
if(sum == m[ii]){
isprint = 1;
printf("yes\n");
break;
}
}
if(isprint == 0){
printf("no\n");
}
}
return 0;
}
DPを使った方法
#include <stdio.h>
#include <stdlib.h>
int compare_int(const void *a, const void *b)
{
return - *(int*)a + *(int*)b;
}
int main(void){
int n, a[20], q, m[200], sum, isprint, ii, bit, i, s[2001], j;
scanf("%d", &n);
for(i = 0; i < n; i++){
scanf("%d", &a[i]);
}
scanf("%d", &q);
for(i = 0; i < q; i++){
scanf("%d", &m[i]);
}
for(i = 0; i < 2001; i++){
s[i] = 0;
}
for(i = 0; i < n; i++){
for(j = 2000; j > 0; j--){
if(s[j] == 1 && j + a[i] <= 2000){
s[j + a[i]] = 1;
}
}
s[a[i]] = 1;
}
for(i = 0; i < q; i++){
if(s[m[i]] == 1){
printf("yes\n");
}else{
printf("no\n");
}
}
return 0;
}
問題11-20
11
問題のポイント
bit全探索のコードの組み方
複雑な入力に対しての対処
解答
#include <stdio.h>
int main(void){
int n, m;
int p[10], k[10], s[10][10];
int bit;
int ans = 0;
int i, j, cnt;
scanf("%d%d", &n, &m);
for(i = 0; i < m; i++){
scanf("%d", &k[i]);
for(j = 0; j < k[i]; j++){
scanf("%d", &s[i][j]);
}
}
for(i = 0; i < m; i++){
scanf("%d", &p[i]);
}
for(bit = 0; bit < (1<<n); ++bit){//スイッチパターンをbit全探索するループ
for(i = 0; i < m; i++){//i番目のスイッチのonoffを調べる
cnt = 0;
for(j = 0; j < k[i]; j++){
if(bit & (1 << (s[i][j] - 1))){//この -1 を忘れない(これで20分悩んだ)
cnt++;
}
}
if(cnt%2 != p[i]){//i番目のスイッチがoffの場合は諦めて次のスイッチパターンに入る
break;
}
if(i == (m - 1)){
ans++;
}
}
}
printf("%d\n", ans);
}
12
問題のポイント
比較的難しい問題に対処するコード力
解答
#include <stdio.h>
int max(int a, int b){return a > b ? a : b;}
int main(void){
int n, m;
int x[1000], y[1000];
int i, j;
scanf("%d%d", &n, &m);
for(i = 0; i < m; i++){
scanf("%d%d", &x[i], &y[i]);
x[i]--;
y[i]--;
}
int bit, member, memb[12], k, ans, flag;
ans = 0;
for(bit = 0; bit < (1 << n); ++bit){//bit探索のループ
member = 0;
for(i = 0; i < n; i++){
memb[i] = 0;
}
for(i = 0; i < n; i++){//あるbitの組が，すべての人間関係の条件を満たしていることを確認する
if(bit & (1 << i)){
memb[member++] = i;//memb[]には，派閥のメンバーを記録する
}
}
for(i = 0; i < member; i++){
for(j = i+1; j < member; j++){
//memb[i]とmemb[j]の人間関係がリストに入っているか確認
//入っていない場合はgotoで次のループへ
//入っている場合は次のfor文へ
flag = 0;
for(k = 0; k < m; k++){
if(x[k] == memb[i] && y[k] == memb[j]){
flag = 1;
break;
}
}
if(flag == 0){
goto LAST;
}
}
}
ans = max(ans, member);
LAST:
;
}
printf("%d\n", ans);
return 0;
}
13
問題のポイント
より複雑なbit全探索の実装
どうすれば計算時間を短縮できるかを見極める(変数の上限値が不自然に小さい場合は，それがヒントかもしれない)
解答
#include <stdio.h>
int max(int a, int b){return a > b ? a : b;}
int main(void){
int r, c;
scanf("%d%d", &r, &c);
int i, j, k;
int a[10][10000];
for(i = 0; i < r; i++){//第一成分がr，第二成分がc
for(j = 0; j < c; j++){
scanf("%d", &a[i][j]);
}
}
int bit;
int ans = 0;
int a_r[10][10000];
int row_cnt, maisu;
for(bit = 0; bit < (1 << r); ++bit){
//縦列をひっくり返したときの裏表の状態を計算する
for(i = 0; i < r; i++){
if(bit & (1 << i)){
for(j = 0; j < c; j++){
a_r[i][j] = (a[i][j] == 1) ? 0 : 1;
}
}else
{
for(j = 0; j < c; j++){
a_r[i][j] = a[i][j];
}
}
}
maisu = 0;
for(i = 0; i < c; i++){
row_cnt = 0;
for(j = 0; j < r; j++){
row_cnt += a_r[j][i];
}
maisu += max(row_cnt, r - row_cnt);
}
ans = max(ans, maisu);
}
printf("%d\n", ans);
return 0;
}
14
問題のポイント
入力の値が$a < 10^9$などのように，$10^9$より小さいことが保証されている場合は，ギリギリint型で扱える(int型で扱える最大値は$2147483647\approx2\times10^9$)．ただし，これらの値を足したり掛けたりする場合は桁落ちの可能性があるので注意．今回は入力はint型で扱える．
10個のテストケースがあり，5個はACを取れたのに，残りの5個はWAの場合は，桁落ちが起きている，というミスを犯している場合が多い(気がする)
解答
#include <stdio.h>
int main(void){
int n, k;
scanf("%d%d", &n, &k);
int a[15];
int i, j;
for(i = 0; i < n; i++){
scanf("%d", &a[i]);
}
long long int ans = 999999999999999;
int bit;
int a_temp[15];
int can_see = 0;
int maxh = 0;
long long int cost;
for(bit = 0; bit < (1 << n); ++bit){
cost = 0;
can_see = 0;
for(i = 0; i < n; i++){
a_temp[i] = a[i];
}
for(i = 0; i < n; i++){
if(bit & (1 << i)){
can_see++;
//0番目から(i-1)番目までの建物の高さの最大値を求める
//ただしi = 0のときは0
maxh = 0;
for(j = 0; j <= i - 1; j++){
maxh = maxh > a_temp[j] ? maxh : a_temp[j];
}
//i番目の高さをmaxh+1以上にする
if(a_temp[i] < maxh + 1){
cost += maxh + 1 - a_temp[i];
a_temp[i] = maxh + 1;
}
}
}
if(can_see >= k){
ans = ans < cost ? ans : cost;
}
}
printf("%lld\n", ans);
return 0;
}
15
問題のポイント
小数の扱い
順列全探索というお題でしたが，使わずに解いてしまいました・・・
解答
#include <stdio.h>
#include <math.h>
int main(void){
int n;
int i, j;
scanf("%d", &n);
int x[8], y[8];
for(i = 0; i < n; i++){
scanf("%d%d", &x[i], &y[i]);
}
double ans = 0.;
for(i = 0; i < n; i++){
for(j = i + 1; j < n; j++){
ans += sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));
}
}
int comb = n*(n - 1)/2;
ans = ans/comb*(n-1);
printf("%.8lf\n", ans);
}
16
問題のポイント
辞書式列挙の実装
解答
#include <stdio.h>
int main(void){
int n;
scanf("%d", &n);
int i, j;
int p[8], q[8];
for(i = 0; i < n; i++){scanf("%d", &p[i]);}
for(i = 0; i < n; i++){scanf("%d", &q[i]);}
for(i = 0; i < n; i++){p[i]--; q[i]--;}
int a_temp[8];
//a_tempに初期値を入れる
//このa_tempに辞書順に逐次的に値を代入する
for(i = 0; i < n; i++){
a_temp[i] = i;
}
int cnt = 1;
int a, b;
int flag_a = 0, flag_b = 0;
int flag;
int go_next;
while(1){
for(i = 0; i < n; i++){
if(a_temp[i] != p[i]){
break;
}
if(i == n - 1){
a = cnt;
flag_a = 1;
}
}
for(i = 0; i < n; i++){
if(a_temp[i] != q[i]){
break;
}
if(i == n - 1){
b = cnt;
flag_b = 1;
}
}
if(flag_a == 1 && flag_b == 1){
break;
}
go_next = 0;
//a_tempを1つ進める処理を書く
do{
a_temp[n - 1] += 1;
for(i = 1; i < n; i++){
if(a_temp[n - i] == n){
a_temp[n - i] = 0;
a_temp[n - i - 1]++;
}
}
for(i = 0; i < n; i++){
flag = 0;
for(j = 0; j < n; j++){
if(a_temp[j] == i){
flag = 1;
break;
}
}
if(flag == 0){
break;
}
if(i == n - 1){
go_next = 1;
}
}
}while(go_next == 0);
cnt++;
}
printf("%d\n", a > b ? a - b : b - a);
return 0;
}
17
問題のポイント
いかにして順列全探索に落とし込むか？(順列全探索で解ける問題と知らされていなかったら，たぶん解けなかっただろうな・・・)
今までの16問と比較して，個人的に一番難しい問題でした
解答
#include <stdio.h>
int main(void){
int k;
scanf("%d", &k);
int r[8], c[8];
int i, j;
for(i = 0; i < k; i++){
scanf("%d%d", &r[i], &c[i]);
}
//クイーンの配置をa[]で全列挙する
//a[2]=3のとき，2列3行にクイーンがいる，という意味
//ただし，r, cで指定されたクイーン配置を満たさない場合はスキップ
//クイーンが襲撃できる場合もスキップ
//スキップする場合は，次のクイーン配置にa[]を更新する．
//初期配置はa[0]=0, a[1] = 1...のもの．
int a[8];
int flag;
int cnt;
int go_next;
for(i = 0; i < 8; i++){
a[i] = i;
}
while(1){
//r，cチェック
for(i = 0; i < k; i++){
if(a[r[i]] != c[i]){
goto NEXT;
}
}
//襲撃チェック
//辞書式でやっているので，斜め方向のチェックだけでよい
for(i = 0; i < 8; i++){//a[i]をチェック
for(j = 1; j + a[i] < 8, i + j < 8; j++){//斜め右下方向チェック(行，列番号が増加する方向)
if(j + a[i] == a[i + j]){
goto NEXT;
}
}
for(j = 1; - j + a[i] >= 0, i - j >= 0; j++){//斜め左下方向チェック(行が増加，列が減少する方向)
if(-j + a[i] == a[i - j]){
goto NEXT;
}
}
for(j = 1; - j + a[i] >= 0, i + j < 8; j++){//斜め左下方向チェック(行が増加，列が減少する方向)
if(-j + a[i] == a[i + j]){
goto NEXT;
}
}
for(j = 1; j + a[i] < 8, i - j >= 0; j++){//斜め左下方向チェック(行が増加，列が減少する方向)
if(j + a[i] == a[i - j]){
goto NEXT;
}
}
}
break;
NEXT:;
//次のa[]へ
go_next = 0;
do{
a[7] += 1;
for(i = 7; i >= 0; i--){
if(a[i] == 8){
a[i] = 0;
a[i - 1]++;
}
}
for(i = 0; i < 8; i++){//a[]のいずれかにiが含まれているかを調べる
flag = 0;
for(j = 0; j < 8; j++){
if(a[j] == i){
flag = 1;
break;
}
}
if(flag == 0){
break;
}
if(i == 7){
go_next = 1;
}
}
}while(go_next == 0);
}
for(i = 0; i < 8; i++){
for(j = 0; j < a[i]; j++){
printf(".");
}
printf("Q");
for(j = a[i]; j < 7; j++){
printf(".");
}
printf("\n");
}
}
18
問題のポイント
二分探索の実装
(コード実装はリスト探索（C言語）を参考にしました．)
解答
#include <stdio.h>
int binary_search (int list[], int list_size, int x) {
int left, right, mid;
left = 0;
right = list_size - 1;
while (left <= right) {
mid = (left + right)/2;
if(list[mid] == x){ return mid; }
else if (list[mid] < x){ left = mid + 1; }
else { right = mid - 1; }
}
return -1;
}
int main(void){
int n, q, i;
int s[100000], t[50000];
scanf("%d", &n);
for(i = 0; i < n; i++){scanf("%d", &s[i]);}
scanf("%d", &q);
for(i = 0; i < q; i++){scanf("%d", &t[i]);}
int ans = 0;
for(i = 0; i < q; i++){
if(binary_search(s, n, t[i]) != -1){
ans++;
}
}
printf("%d\n", ans);
}
19
問題のポイント
二分探索の実装，ただし18の実装とは少し違い，ソートされたリストからある値の要素を見つけ出すのではなく，ある値に一番近い値を見つけ出すために二分探索を使います．
解答
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int min(int a, int b){return a < b ? a : b;}
int compare_int(const void *a, const void *b)
{
return *(int*)a - *(int*)b;
}
int binary_search(int list[], int list_size, int x){
int left, right, mid;
left = 0;
right = list_size - 1;
while (left <= right) {
mid = (left + right)/2;
if(right - left == 1){
return left;
}else if(list[mid] < x){
left = mid;
}
else{
right = mid;
}
}
return -1;
}
int main(void){
int d;
scanf("%d", &d);
int n;
scanf("%d", &n);
int m;
scanf("%d", &m);
int i, j;
int dl[100001];
dl[0] = 0;
for(i = 1; i < n; i++){scanf("%d", &dl[i]);}
dl[n] = d;
int k[10000];
for(i = 0; i < m; i++){scanf("%d", &k[i]);}
qsort(dl, n + 1, sizeof(int), compare_int);
int mid;
int ans = 0;
int left;
for(i = 0; i < m; i++){
left = binary_search(dl, n + 1, k[i]);
ans += min(k[i] - dl[left], dl[left + 1] - k[i]);
}
printf("%d\n", ans);
}
20
問題のポイント
今までの二分探索と違い，同じ値が含まれているリストから探索する，という要素が含まれました．
解答
#include <stdio.h>
#include <stdlib.h>
long int compare_int(const void *a, const void *b)
{
return *(long int*)a - *(long int*)b;
}
long int binary_search_right(long int list[], long int list_size, long int x){
long int left, right, mid;
left = 0;
right = list_size - 1;
while (left <= right) {
mid = (left + right)/2;
if(list[left] < x && x <= list[right] && right - left == 1){
return left;
}else if(list[mid] < x){
left = mid;
}
else{
right = mid;
}
}
while(1){
printf("error");
}
}
long int binary_search_left(long int list[], long int list_size, long int x){
long int left, right, mid;
left = 0;
right = list_size - 1;
while (left <= right) {
mid = (left + right)/2;
if(list[left] <= x && x < list[right]&& right - left == 1){
return right;
}else if(list[mid] <= x){
left = mid;
}
else{
right = mid;
}
}
while(1){
printf("error");
}
}
int main(void){
int n, i;
scanf("%d", &n);
long int a[100001], b[100001], c[100001];
for(i = 0; i < n; i++){scanf("%ld", &a[i]);}
for(i = 0; i < n; i++){scanf("%ld", &b[i]);}
for(i = 0; i < n; i++){scanf("%ld", &c[i]);}
qsort(a, n, sizeof(long int), compare_int);
qsort(c, n, sizeof(long int), compare_int);
long int a_b, b_c, k;
long int ans = 0;
if(n == 1){
if(a[0] < b[0] && b[0] < c[0]){
printf("1\n");
return 0;
}else{
printf("0\n");
return 0;
}
}
for(i = 0; i < n; i++){
if(b[i] > a[n - 1]){
a_b = n;
}else if(b[i] <= a[0]){
a_b = 0;
}else{
a_b = binary_search_right(a, n, b[i]) + 1;//(条件を満たす最大の配置番号＋１)通りがある
}
if(b[i] >= c[n - 1]){
b_c = 0;
}else if(b[i] < c[0]){
b_c = n;
}else{
b_c = n - binary_search_left(c, n, b[i]);
}
ans += a_b * b_c;
}
printf("%ld\n", ans);
return 0;
}
問題21-30
21
問題のポイント
問題を効率よく見つける方法を見つける力
小数(double型)のソート(これを用いずにももちろんできますが・・・)
解答
#include <stdio.h>
#include <stdlib.h>
long int h[100001], s[100001];
long int n;
int compare( const void *p, const void *q ) {
if( *(double*)p > *(double*)q ) return 1;
if( *(double*)p < *(double*)q ) return -1;
return 0;
}
long int check_t(long int mid){
int i, j;
long int cnt;
double t[100001];
for(i = 0; i < n; i++){
t[i] = (mid - h[i])/s[i];
}
qsort(t, n, sizeof(double), compare);
for(i = 0; i < n; i++){
if(t[i] >= i){
}else{
return 0;
}
}
return 1;
}
int main(void){
scanf("%ld", &n);
int i;
for(i = 0; i < n; i++){
scanf("%ld%ld", &h[i], &s[i]);
}
long int q_min, q_max;
long int tmp;
q_min = h[0];
q_max = h[0] + s[0] * (n - 1);
for(i = 1; i < n; i++){
tmp = h[i] + s[i] * (n - 1);
q_min = q_min < h[i] ? h[i] : q_min;
q_max = q_max < tmp ? tmp : q_max;
}
q_max++;
q_min--;
long int mid;
while(1){
mid = q_min + (q_max - q_min) / 2;
if(q_max - q_min == 1){
break;
}else if(check_t(mid)){
q_max = mid;
}else{
q_min = mid;
}
//printf("%ld %ld %ld\n", mid, q_max, q_min);
}
printf("%ld\n", q_max);
}
22
問題のポイント
私は三分探索を使いました．
解答
#include <stdio.h>
#include <math.h>
double p;
double func(double x){
return x + p / pow(2, x/1.5);
}
int main(void){
double pmin, pmax, mid1, mid2;
scanf("%lf", &p);
pmin = 0;
pmax = p + 1;
while(pmax - pmin >= 10e-10){
mid1 = func(pmin + (pmax - pmin)/3);
mid2 = func(pmin + (pmax - pmin)/3*2);
if(mid1 > mid2){
pmin = pmin + (pmax - pmin)/3;
}else{
pmax = pmin + (pmax - pmin)/3*2;
}
}
printf("%.10lf", func(pmin));
}
23
問題のポイント
どうすれば二分探索の問題に落とし込めるか？
効率のよい解法は？⇒これは，それぞれの計算の処理の計算時間のオーダーを把握しておかないときついと思います．
つまり，例えばソートの計算時間は高々$O(n \log n)$，みたいなやつです．
それを考えると解けるのかなと思います．私はわからなかったので解説を見たのですが．
追記：半分全列挙というアルゴリズムを知っている必要があるようです．この問題は半分全列挙を勉強した後の方がいいと思います．
解答
#include <stdio.h>
#include <stdlib.h>
long int p2[1002001];
long int compare_int(const void *a, const void *b)
{
return *(long int*)a - *(long int*)b;
}
int main(void){
long int n, m;
scanf("%ld%ld", &n, &m);
long int p[1001];
long int i, j;
p[0] = 0;
for(i = 1; i < n + 1; i++){
scanf("%ld", &p[i]);
}
for(i = 0; i < n + 1; i++){
for(j = 0; j < n + 1; j++){
p2[i + j*(n + 1)] = p[i] + p[j];
}
}
qsort(p2, (n+1)*(n+1), sizeof(long int), compare_int);
long int ans = 0;
long int left, right, mid;
long int k;
for(i = 0; i < (n+1)*(n+1); i++){
k = p2[i];
left = 0;
right = (n+1)*(n+1) - 1;
if(p2[right] + k <= m){
left = right;
}else{
while(right - left > 1){
mid = (right + left) / 2;
if(p2[mid] + k <= m){
left = mid;
}else{
right = mid;
}
}
}
if(p2[left] + k <= m){
ans = ans < p2[left] + k ? p2[left] + k: ans;
}
}
printf("%ld\n", ans);
return 0;
}
24
問題のポイント
基本的な深さ優先探索の実装(帰りがけ順，行きがけ順)
何気に入力の実装が面倒な問題(難しいわけではないが)
解答
#include <stdio.h>
int u[100], k[100], v[100][100], d[100], f[100];
int t = 0;
int DFS(int x){
int i;
t++;
d[x] = t;
for(i = 0; i < k[x]; i++){
if(d[v[x][i]]){
continue;
}
DFS(v[x][i]);
}
t++;
f[x] = t;
}
int main(void){
int n;
scanf("%d", &n);
int i, j;
for(i = 0; i < n; i++){
scanf("%d", &u[i]);//いらない
scanf("%d", &k[i]);
for(j = 0; j < k[i]; j++){
scanf("%d", &v[i][j]);
v[i][j]--;//節点番号を0~N-1の範囲に変更
}
d[i] = 0;
f[i] = 0;
}
while(t < n*2){
for(i = 0; i < n; i++){
if(d[i] == 0){
DFS(i);
break;
}
}
}
for(i = 0; i < n; i++){
printf("%d %d %d\n", i+1, d[i], f[i]);
}
return 0;
}
25
問題のポイント
深さ探索っぽくない問題ですが，深さ探索で解ける問題(きっと慣れている人からしたら一瞬で深さ探索の問題だとわかるんだと思うのですが・・・)
私は上下左右斜めに移動する，というコードをべた書きで書きましたが，もっときれいに書けると思います．
解答
#include <stdio.h>
int c[50][50];
int w, h;
int isRange(int h_i, int w_i){
if(h_i < 0 || w_i < 0){
return 0;
}
if(h_i >= h || w_i >= w){
return 0;
}
return 1;
}
int DFS(int h_i, int w_i){
c[h_i][w_i] = 0;
if(isRange(h_i + 1, w_i)){
if(c[h_i + 1][w_i] == 1){
DFS(h_i + 1, w_i);
}
}
if(isRange(h_i - 1, w_i)){
if(c[h_i - 1][w_i] == 1){
DFS(h_i - 1, w_i);
}
}
if(isRange(h_i, w_i + 1)){
if(c[h_i][w_i + 1] == 1){
DFS(h_i, w_i + 1);
}
}
if(isRange(h_i, w_i - 1)){
if(c[h_i][w_i - 1] == 1){
DFS(h_i, w_i - 1);
}
}
if(isRange(h_i + 1, w_i + 1)){
if(c[h_i + 1][w_i + 1] == 1){
DFS(h_i + 1, w_i + 1);
}
}
if(isRange(h_i + 1, w_i - 1)){
if(c[h_i + 1][w_i - 1] == 1){
DFS(h_i + 1, w_i - 1);
}
}
if(isRange(h_i - 1, w_i + 1)){
if(c[h_i - 1][w_i + 1] == 1){
DFS(h_i - 1, w_i + 1);
}
}
if(isRange(h_i - 1, w_i - 1)){
if(c[h_i - 1][w_i - 1] == 1){
DFS(h_i - 1, w_i - 1);
}
}
}
int main(void){
int ans;
int i, j;
while(1){
scanf("%d%d", &w, &h);
if(w == 0 && h == 0){
break;
}
for(i = 0; i < h; i++){
for(j = 0; j < w; j++){
scanf("%d", &c[i][j]);
}
}
ans = 0;
for(i = 0; i < h; i++){
for(j = 0; j < w; j++){
if(c[i][j]){
DFS(i, j);
ans++;
}
}
}
printf("%d\n", ans);
}
}
26
問題のポイント
解法は様々ですが，私は動的配列を用いました(tree[200000][200000]だと，メモリ不足になる)
検索すればいくつか解法が出てくるので，参考になると思います．
解答
#include <stdio.h>
#include <stdlib.h>
int ans[200000];
int n, q;
int a[200000], b[200000], p[200000], x[200000];
int *tree[200000];
int cnt[200000];
int cnts[200000];
int DFS(int now_v, int before_v) {//v:現在の頂点 bv:前にいた頂点
int i, new_v;
for(i = 0; i < cnt[now_v]; i++){//iをvの個数分だけループ
new_v = tree[now_v][i];//お隣の頂点
if (before_v != new_v){//逆流を防ぐため，自分が前にいたところには行かない
ans[new_v] += ans[now_v];
DFS(new_v, now_v);//現在の自分の位置を，前にいたところに変え，お隣の頂点に移動
}
}
return 0;
}
int main(void){
scanf("%d%d", &n, &q);
int i, j;
for(i = 0; i < n; i++){
cnt[i] = 0;
ans[i] = 0;
cnts[i] = 0;
}
for(i = 0; i < n - 1; i++){
scanf("%d%d", &a[i], &b[i]);
a[i]--;
b[i]--;
cnt[a[i]]++;
cnt[b[i]]++;
}
for(i = 0; i < q; i++){
scanf("%d%d", &p[i], &x[i]);
p[i]--;
}
//普通にメモリ確保すると足りなくなるので，可変長配列で確保する
for(i = 0; i < n; i++){
tree[i] = (int *)malloc(sizeof(int)*(cnt[i] + 1));
if(tree[i] == NULL){
return 0;
}
}
for(i = 0; i < n - 1; i++){
tree[a[i]][cnts[a[i]]] = b[i];
tree[b[i]][cnts[b[i]]] = a[i];
cnts[a[i]]++;
cnts[b[i]]++;
}
for(i = 0; i < q; i++) {
ans[p[i]] += x[i];
}
DFS(0, -1);
for(i = 0; i < n; i++){
printf("%d", ans[i]);
if(i == n - 1){
break;
}
printf(" ");
}
printf("\n");
return 0;
}
27
問題のポイント
深さ優先で解くのは変わりないですが，探索した後にもとに戻すという動作(探索時に，1が代入されている薄氷のマスに0を代入しますが，探索が終わった後にまた1に戻すという動作)が必要です．他は25と似ています．
解答
#include <stdio.h>
int m, n;
int DFS(int row, int col,int depth, int c[][90]){
int i, j;
c[row][col] = 0;
depth++;
int d_temp1 = 0;
int d_temp2 = 0;
int d_temp3 = 0;
int d_temp4 = 0;
if(row + 1 < n){
if(c[row + 1][col]){
d_temp1 = DFS(row + 1, col, depth, c);
}
}
if(row - 1 >= 0){
if(c[row - 1][col]){
d_temp2 = DFS(row - 1, col, depth, c);
}
}
if(col + 1 < m){
if(c[row][col + 1]){
d_temp3 = DFS(row, col + 1, depth, c);
}
}
if(col - 1 >= 0){
if(c[row][col - 1]){
d_temp4 = DFS(row, col - 1, depth, c);
}
}
int rtn;
rtn = depth > d_temp1 ? depth : d_temp1;
rtn = rtn > d_temp2 ? rtn : d_temp2;
rtn = rtn > d_temp3 ? rtn : d_temp3;
rtn = rtn > d_temp4 ? rtn : d_temp4;//もっと簡潔に書けないのかなあ
c[row][col] = 1;
return rtn;
}
int main(void){
scanf("%d%d", &m, &n);
int c[90][90];
int i, j;
for(i = 0; i < n; i++){
for(j = 0; j < m; j++){
scanf("%d", &c[i][j]);
}
}
int depth;
int ans = 0;
for(i = 0; i < n; i++){
for(j = 0; j < m; j++){
if(c[i][j]){
depth = DFS(i, j, 0, c);
ans = ans > depth ? ans : depth;
}
}
}
printf("%d\n", ans);
}
28
問題のポイント
幅優先探索の実装(C言語で実装例を示しているのは少なかったです・・・)
解答
#include <stdio.h>
int main(void){
int i, j, u[100], n, k[100], v[100][100];
scanf("%d", &n);
for(i = 0; i < n; i++){
scanf("%d", &u[i]);
scanf("%d", &k[i]);
for(j = 0; j < k[i]; j++){
scanf("%d", &v[u[i] - 1][j]);
v[i][j]--;
}
}
int queue[100];
int dist[100];
int l = 0, r = 1;//l:先頭の配列，r:データ個数(=次にqueueに代入するときの配列番号)
int v_i;
int nv;
for(i = 0; i < n; i++){
dist[i] = -1;
}
int ii;
dist[0] = 0;
queue[0] = 0;
while(l != r){
v_i = queue[l];//先頭データを取り出し
l++;//先頭データを更新(いわゆるpop)
for(i = 0; i < k[v_i]; i++){
nv = v[v_i][i];
if(dist[nv] != -1){//未発見であれば
continue;
}
queue[r] = nv;//データを追加
r++;//データ個数も追加
dist[nv] = dist[v_i] + 1;
}
}
for(i = 0; i < n; i++){
printf("%d %d\n", i+1, dist[i]);
}
}
29
問題のポイント
幅優先だが，今回は迷路の最短経路の長さを見つけ出す問題
マス目系の問題が出たら，DFS/BFSで解ける問題と思ったほうが良いかもしれない．
100問精選のページにもリンクがあったが，こちらの記事にDFS/BFSの特徴の違いなど書いてあり分かりやすかった．
解答
#include <stdio.h>
int main(void){
int R, C;
int sy, sx, gy, gx;
char m[51][51];
int i, j;
char m_tmp[51];
scanf("%d%d", &R, &C);
scanf("%d%d", &sy, &sx);
scanf("%d%d", &gy, &gx);
sy--; sx--; gy--; gx--;
for(i = 0; i < R; i++){
scanf("%s", m_tmp);
for(j = 0; j < C; j++){
m[i][j] = m_tmp[j];
}
}
int queue[2500][2];
int dist[50][50];
for(i = 0; i < R; i++){
for(j = 0; j < C; j++){
dist[i][j] = -1;
}
}
int l, r;
l = 0;
r = 1;
int x, y;
dist[sy][sx] = 0;
queue[0][0] = sy;
queue[0][1] = sx;
while(dist[gy][gx] == -1){
y = queue[l][0];
x = queue[l][1];
l++;
if(dist[y + 1][x] == -1 && m[y + 1][x] == '.'){
queue[r][0] = y + 1;
queue[r][1] = x;
dist[y + 1][x] = dist[y][x] + 1;
r++;
}
if(dist[y - 1][x] == -1 && m[y - 1][x] == '.'){
queue[r][0] = y - 1;
queue[r][1] = x;
dist[y - 1][x] = dist[y][x] + 1;
r++;
}
if(dist[y][x + 1] == -1 && m[y][x + 1] == '.'){
queue[r][0] = y;
queue[r][1] = x + 1;
dist[y][x + 1] = dist[y][x] + 1;
r++;
}
if(dist[y][x - 1] == -1 && m[y][x - 1] == '.'){
queue[r][0] = y;
queue[r][1] = x - 1;
dist[y][x - 1] = dist[y][x] + 1;
r++;
}
}
printf("%d\n", dist[gy][gx]);
}
30
問題のポイント
実装つらい
解答
# include <stdio.h>
# include <stdlib.h>
int H, W, N;
int isRange(int i, int j){
if(i < 0){
return 0;
}
if(j < 0){
return 0;
}
if(i > H - 1){
return 0;
}
if(j > W - 1){
return 0;
}
return 1;
}
int queue[1000000][2];
char c[1001][1001];
int c_dist[1000][1000];
char n_list[] = {'0','1','2','3','4','5','6','7','8','9'};
int main(void){
int i, j, k;
scanf("%d%d%d", &H, &W, &N);
int sn[10][2];
char s_tmp[1001];
for(i = 0; i < H; i++){
scanf("%s", s_tmp);
for(j = 0; j < W; j++){
switch(s_tmp[j]){
case '.':
c[i][j] = 0;
break;
case 'S':
c[i][j] = 0;
sn[0][1] = j;
sn[0][0] = i;
break;
case 'X':
c[i][j] = -1;
break;
default:
c[i][j] = 0;
for(k = 1; k <= N; k++){
if(n_list[k] == s_tmp[j]){
sn[k][1] = j;
sn[k][0] = i;
}
}
}
}
}
int tmp[2], tmp_[2];
int l, r;
int ans = 0;
for(i = 1; i <= N; i++){
l = 0;
r = 1;
queue[0][0] = sn[i - 1][0];//スタート地点をqueueの先頭に
queue[0][1] = sn[i - 1][1];
for(j = 0; j < H; j++){
for(k = 0; k < W; k++){
c_dist[j][k] = -1;
}
}
c_dist[queue[0][0]][queue[0][1]] = 0;
while(c_dist[sn[i][0]][sn[i][1]] == -1){
tmp[0] = queue[l][0];
tmp[1] = queue[l][1];
l++;
tmp_[0] = tmp[0] + 1;
tmp_[1] = tmp[1];
if(isRange(tmp_[0], tmp_[1]) && c[tmp_[0]][tmp_[1]] != -1 && c_dist[tmp_[0]][tmp_[1]] == -1){
queue[r][0] = tmp_[0];
queue[r][1] = tmp_[1];
r++;
c_dist[tmp_[0]][tmp_[1]] = c_dist[tmp[0]][tmp[1]] + 1;
}
tmp_[0] = tmp[0] - 1;
tmp_[1] = tmp[1];
if(isRange(tmp_[0], tmp_[1]) && c[tmp_[0]][tmp_[1]] != -1 && c_dist[tmp_[0]][tmp_[1]] == -1){
queue[r][0] = tmp_[0];
queue[r][1] = tmp_[1];
r++;
c_dist[tmp_[0]][tmp_[1]] = c_dist[tmp[0]][tmp[1]] + 1;
}
tmp_[0] = tmp[0];
tmp_[1] = tmp[1] + 1;
if(isRange(tmp_[0], tmp_[1]) && c[tmp_[0]][tmp_[1]] != -1 && c_dist[tmp_[0]][tmp_[1]] == -1){
queue[r][0] = tmp_[0];
queue[r][1] = tmp_[1];
r++;
c_dist[tmp_[0]][tmp_[1]] = c_dist[tmp[0]][tmp[1]] + 1;
}
tmp_[0] = tmp[0];
tmp_[1] = tmp[1] - 1;
if(isRange(tmp_[0], tmp_[1]) && c[tmp_[0]][tmp_[1]] != -1 && c_dist[tmp_[0]][tmp_[1]] == -1){
queue[r][0] = tmp_[0];
queue[r][1] = tmp_[1];
r++;
c_dist[tmp_[0]][tmp_[1]] = c_dist[tmp[0]][tmp[1]] + 1;
}
}
ans += c_dist[sn[i][0]][sn[i][1]];
}
printf("%d\n", ans);
return 0;
}
問題31-40
31
問題のポイント
正直解説見ないと分からなかったです(泣)
結局，ある空地が建物の内部か外部かを判定できればいいわけですが，その処理方法を思いつきませんでした．どうしても建物があるところを起点として考えてしまいがいちですよね・・・
解答
# include <stdio.h>
int w, h;
int isRange(int i, int j){
if(i < 0 || j < 0 || i > h + 2 || j > w + 2){
return 0;
}
return 1;
}
int main(void){
int i, j, k;
scanf("%d%d", &w, &h);
int c[102][102];
int isSearch[102][102];
int isNaibu[102][102];
for(i = 0; i < 102; i++){
for(j = 0; j < 102; j++){
isNaibu[i][j] = 1;
}
}
for(i = 1; i < h + 1; i++){
for(j = 1; j < w + 1; j++){
scanf("%d", &c[i][j]);
}
}
int ans = 0;
int queue[10500][2], r, l;
int qi, qj, qi_, qj_;
queue[0][0] = 0;
queue[0][1] = 0;
r = 1;
l = 0;
while(r != l){
qi = queue[l][0];
qj = queue[l][1];
l++;
for(i = 0; i < 6; i++){
switch (i){
case 0:
qi_ = qi;
qj_ = qj + 1;
break;
case 1:
qi_ = qi;
qj_ = qj - 1;
break;
case 2://右下
if(qi % 2 == 0){
qi_ = qi + 1;
qj_ = qj;
}else{
qi_ = qi + 1;
qj_ = qj + 1;
}
break;
case 3://左下
if(qi % 2 == 0){
qi_ = qi + 1;
qj_ = qj - 1;
}else{
qi_ = qi + 1;
qj_ = qj;
}
break;
case 4://右上
if(qi % 2 == 0){
qi_ = qi - 1;
qj_ = qj;
}else{
qi_ = qi - 1;
qj_ = qj + 1;
}
break;
case 5://左上
if(qi % 2 == 0){
qi_ = qi - 1;
qj_ = qj - 1;
}else{
qi_ = qi - 1;
qj_ = qj;
}
break;
}
if(isRange(qi_, qj_) && c[qi_][qj_] == 0 && isNaibu[qi_][qj_] == 1){
isNaibu[qi_][qj_] = 0;
queue[r][0] = qi_;
queue[r][1] = qj_;
r++;
}
}
}
// for(i = 0; i < h + 2; i++){
// for(j = 0; j < w + 2; j++){
// printf("%d ", isNaibu[i][j]);
// }
// printf("\n");
// }
for(qi = 1; qi < h+1; qi++){
for(qj = 1; qj < w+1; qj++){
if(isNaibu[qi][qj] == 0){
continue;
}
for(i = 0; i < 6; i++){
switch (i){
case 0:
qi_ = qi;
qj_ = qj + 1;
break;
case 1:
qi_ = qi;
qj_ = qj - 1;
break;
case 2://右下
if(qi % 2 == 0){
qi_ = qi + 1;
qj_ = qj;
}else{
qi_ = qi + 1;
qj_ = qj + 1;
}
break;
case 3://左下
if(qi % 2 == 0){
qi_ = qi + 1;
qj_ = qj - 1;
}else{
qi_ = qi + 1;
qj_ = qj;
}
break;
case 4://右上
if(qi % 2 == 0){
qi_ = qi - 1;
qj_ = qj;
}else{
qi_ = qi - 1;
qj_ = qj + 1;
}
break;
case 5://左上
if(qi % 2 == 0){
qi_ = qi - 1;
qj_ = qj - 1;
}else{
qi_ = qi - 1;
qj_ = qj;
}
break;
}
if(isNaibu[qi_][qj_] == 0){
ans++;
}
}
}
}
printf("%d\n", ans);
return 0;
}
32
問題のポイント
迷路問題ですが，今度は特定のマスに行けないという問題ではなく，マスとマスの間に壁があるという問題に変わりました．
scanの処理や隣のマスに通れるかの判定が少し煩雑になっただけで，これまでの問題が解けていれば難しくはないはずです．
解答
# include <stdio.h>
int w, h;
int isRange(int i, int j){
if(i < 0 || j < 0 || i > h - 1 || j > w - 1){
return 0;
}
return 1;
}
int main(void){
int i, j, k;
int wall1[30][29];
int wall2[29][30];
int dist[30][30];
int qi[900], qj[900], _i, _j, l, r, i_tmp, j_tmp;
char kuhaku;
while(1){
scanf("%d%d", &w, &h);
if(w == 0 && h == 0){
break;
}
scanf("%c", &kuhaku);
for(j = 0; j < w - 1; j++){
scanf("%d", &wall1[0][j]);//縦の壁
}
for(i = 0; i < h - 1; i++){
for(j = 0; j < w; j++){
scanf("%d", &wall2[i][j]);//横の壁
}
scanf("%c", &kuhaku);
for(j = 0; j < w - 1; j++){
scanf("%d", &wall1[i + 1][j]);
}
}
for(i = 0; i < h; i++){
for(j = 0; j < w; j++){
dist[i][j] = 0;
}
}
dist[0][0] = 1;
l = 0;
r = 1;
qi[0] = 0;
qj[0] = 0;
while(l != r){
_i = qi[l];
_j = qj[l];
l++;
//下に移動する場合
i_tmp = _i + 1;
j_tmp = _j;
if(isRange(i_tmp, j_tmp) && dist[i_tmp][j_tmp] == 0 && wall2[_i][_j] == 0){
dist[i_tmp][j_tmp] = dist[_i][_j] + 1;
qi[r] = i_tmp;
qj[r] = j_tmp;
r++;
}
//上に移動
i_tmp = _i - 1;
j_tmp = _j;
if(isRange(i_tmp, j_tmp) && dist[i_tmp][j_tmp] == 0 && wall2[_i - 1][_j] == 0){
dist[i_tmp][j_tmp] = dist[_i][_j] + 1;
qi[r] = i_tmp;
qj[r] = j_tmp;
r++;
}
//右に移動
i_tmp = _i;
j_tmp = _j + 1;
if(isRange(i_tmp, j_tmp) && dist[i_tmp][j_tmp] == 0 && wall1[_i][_j] == 0){
dist[i_tmp][j_tmp] = dist[_i][_j] + 1;
qi[r] = i_tmp;
qj[r] = j_tmp;
r++;
}
//左に移動
i_tmp = _i;
j_tmp = _j - 1;
if(isRange(i_tmp, j_tmp) && dist[i_tmp][j_tmp] == 0 && wall1[_i][_j - 1] == 0){
dist[i_tmp][j_tmp] = dist[_i][_j] + 1;
qi[r] = i_tmp;
qj[r] = j_tmp;
r++;
}
}
printf("%d\n", dist[h - 1][w - 1]);
}
return 0;
}
33
問題のポイント
DPで解くんですが，最後に一工夫が必要です．
とはいっても少し考えたらできると思うのですが．
解答
#include <stdio.h>
int H, N, W;
int isRange(int i, int j){
if(i < 0 || j < 0 || i > H - 1 || j > W - 1){
return 0;
}
return 1;
}
int main(void){
scanf("%d%d", &H, &W);
int s[50][50];
int i, j;
char tmp[51];
int black_cnt = 0;
for(i = 0; i < H; i++){
scanf("%s", tmp);
for(j = 0; j < W; j++){
if(tmp[j] == '.'){
s[i][j] = 1;
}else if(tmp[j] == '#'){
s[i][j] = 0;
black_cnt++;
}
}
}
int l = 0;
int r = 1;
int queue[2500][2], dist_mat[50][50], q_tmp[2], ii, jj;
queue[0][0] = 0;
queue[0][1] = 0;
for(i = 0; i < H; i++){
for(j = 0; j < W; j++){
dist_mat[i][j] = -1;
}
}
dist_mat[0][0] = 0;
while(l != r){
q_tmp[0] = queue[l][0];
q_tmp[1] = queue[l][1];
l++;
ii = q_tmp[0] + 1;
jj = q_tmp[1];
if(isRange(ii, jj) && s[ii][jj] && dist_mat[ii][jj] == -1){
dist_mat[ii][jj] = dist_mat[q_tmp[0]][q_tmp[1]] + 1;
queue[r][0] = ii;
queue[r][1] = jj;
r++;
}
ii = q_tmp[0] - 1;
jj = q_tmp[1];
if(isRange(ii, jj) && s[ii][jj] && dist_mat[ii][jj] == -1){
dist_mat[ii][jj] = dist_mat[q_tmp[0]][q_tmp[1]] + 1;
queue[r][0] = ii;
queue[r][1] = jj;
r++;
}
ii = q_tmp[0];
jj = q_tmp[1] + 1;
if(isRange(ii, jj) && s[ii][jj] && dist_mat[ii][jj] == -1){
dist_mat[ii][jj] = dist_mat[q_tmp[0]][q_tmp[1]] + 1;
queue[r][0] = ii;
queue[r][1] = jj;
r++;
}
ii = q_tmp[0];
jj = q_tmp[1] - 1;
if(isRange(ii, jj) && s[ii][jj] && dist_mat[ii][jj] == -1){
dist_mat[ii][jj] = dist_mat[q_tmp[0]][q_tmp[1]] + 1;
queue[r][0] = ii;
queue[r][1] = jj;
r++;
}
}
int dist = dist_mat[H - 1][W - 1];
if(dist == -1){
printf("%d\n", -1);
return 0;
}
//塗りつぶせないマスは，移動にかかったマス目距離+1マス=dist+1
//迷路の全体のマスはH*W,うち黒マスはblack_cnt
//なので，ans = H*W - black_cnt - (dist + 1)
int ans;
ans = H * W - black_cnt - (dist + 1);
printf("%d\n", ans);
return 0;
}
34
問題のポイント
こんな問題，ノーミスでできるよね！！(私は\nを忘れてエラーを食らった模様)
解答
#include <stdio.h>
int main(void){
int n;
scanf("%d", &n);
if(n == 0){
printf("1\n");
return 0;
}
if(n == 1){
printf("1\n");
return 0;
}
int a[45];
a[0] = 1;
a[1] = 1;
for(int i = 2; i <= n; i++){
a[i] = a[i-1] + a[i-2];
}
printf("%d\n", a[n]);
return 0;
}
35
問題のポイント
34よりDPっぽく(？)なったので，それをうまく実装できるか
解答
#include <stdio.h>
int max(int a, int b){return a > b ? a : b;}
int main(void){
int N, W;
scanf("%d%d", &N, &W);
int i, j;
int w[10001], v[10001];
for(i = 0; i < N; i++){
scanf("%d%d", &v[i], &w[i]);
}
int c[101][10001];
//int c[101][101];
for(i = 0; i < W; i++){
c[0][i] = 0;
}
for(i = 1; i <= N; i++){
for(j = 0; j <= W; j++){
if(j < w[i-1]){
c[i][j] = c[i-1][j];
}else{
c[i][j] = max(c[i-1][j-w[i-1]] + v[i-1], c[i-1][j]);
}
}
}
printf("%d\n", c[N][W]);
return 0;
}
36
問題のポイント
同一の商品を複数個選ぶことのできるナップザック商品，上のものと少し式が違ってきます．
解答
#include <stdio.h>
int max(int a, int b){return a > b ? a : b;}
int c[101][10001];
int main(void){
int N, W;
int i, j;
int v[101], w[10001];
scanf("%d%d", &N, &W);
for(i = 0; i < N; i++){
scanf("%d%d", &v[i], &w[i]);
}
for(i = 0; i <= W; i++){
c[0][i] = 0;
}
for(i = 0; i < N; i++){
for(j = 0; j <= W; j++){
if(j < w[i]){
c[i + 1][j] = c[i][j];
}else{
c[i + 1][j] = max(c[i + 1][j - w[i]] + v[i], c[i][j]);
}
}
}
printf("%d\n", c[N][W]);
}
37
問題のポイント
これまでは最大値を求めていたのに対し，今回は最小値を求める問題です．少しだけ変えるだけですぐできます．
余談ですが，DPってインクリメントのミスをしがちな気がするので，しっかりなれる必要がありますね．
解答
#include <stdio.h>
int d[21][50001];
int max(int a, int b){return a > b ? a : b;}
int min(int a, int b){return a > b ? b : a;}
int main(void){
int N, M;
scanf("%d%d", &N, &M);
int c[20];
int i, j;
for(i = 0; i < M; i++){
scanf("%d", &c[i]);
}
for(i = 0; i <= N; i++){
d[0][i] = i;
}
for(i = 0; i < M; i++){
for(j = 0; j <= N; j++){
if(j < c[i]){
d[i + 1][j] = d[i][j];
}else{
d[i + 1][j] = min(d[i][j], d[i + 1][j - c[i]] + 1);
}
}
}
printf("%d\n", d[M][N]);
return 0;
}
38
問題のポイント
この問題，初見ではどう解けばいいのか難しいです(特に漸化式の一般化のところ)．
知っていれば解けるんでしょうけど・・・
私は，この記事を参考にして解きました．
解答
#include <stdio.h>
#include <string.h>
int max(int a, int b){return a > b ? a : b;}
int min(int a, int b){return a > b ? b : a;}
int d[1001][1001];
int main(void){
int n;
scanf("%d", &n);
int i, j, k;
char x[1001], y[1001];
int xlen;
int ylen;
char x_list[150][1001], y_list[150][1001];
for(k = 0; k < n; k++){
scanf("%s", x);
scanf("%s", y);
xlen = strlen(x);
ylen = strlen(y);
for(i = 0; i <= xlen; i++){
d[0][i] = 0;
}
for(i = 0; i <= ylen; i++){
d[i][0] = 0;
}
for(i = 0; i < xlen; i++){
for(j = 0; j < ylen; j++){
if(x[i] == y[j]){
d[i + 1][j + 1] = d[i][j] + 1;
}else{
d[i + 1][j + 1] = max(d[i + 1][j], d[i][j + 1]);
}
}
}
printf("%d\n", d[xlen][ylen]);
}
return 0;
}
39
問題のポイント
DPの定式化がツボです．
さらに，桁落ち，インクリメントを間違えないようにする，など注意が必要です．
問題文の$2^{63}-1$個を超えない，っていうのは，おそらくlong long int を使わないと無理ですよ，ってことでしょうか
(どの型が何bitか，をしっかり把握する必要があることを痛感させられました)
解答
#include <stdio.h>
int main(void){
int n;
int i, j, k;
scanf("%d", &n);
int c[100];
for(i = 0; i < n; i++){
scanf("%d", &c[i]);
}
long long int dp[21][100];
for(i = 0; i < 21; i++){
dp[i][0] = 0;
}
dp[c[0]][0] = 1;
for(i = 1; i < n - 1; i++){
for(j = 0; j <= 20; j++){
if(j-c[i] < 0){
dp[j][i] = dp[j+c[i]][i-1];
}else if(j+c[i] > 20){
dp[j][i] = dp[j-c[i]][i-1];
}
else{
dp[j][i] = dp[j-c[i]][i-1] + dp[j+c[i]][i-1];
}
}
}
printf("%lld\n", dp[c[n-1]][n-2]);
return 0;
}
40
問題のポイント
同じく漸化式を立てればいいのですが，漸化式には過去2日分の食事データが必要なので面倒です．
問題の解説にもあるとおり，オーバーフローにならないよう，気を付けないといけません．
(適時10000で割らないと，long long int 型を使ってもオーバーフローになりました．)
解答
#include <stdio.h>
int main(void){
int n, k;
int i, j, m;
scanf("%d%d", &n, &k);
int plan[100];
for(i = 0; i < n; i++){
plan[i] = -1;
}
int day, plan_day;
for(i = 0; i < k; i++){
scanf("%d%d", &day, &plan_day);
plan[day-1] = plan_day - 1;
//n日目の予定が1のとき，plan配列の(n-1)番目に0を代入する．
//予定がない場合は-1
}
long long int dp[100][3][3];//day : today s plan: 1 day ago plans
for(i = 0; i < 3; i++){
for(j = 0; j < 3; j++){
for(k = 1; k < n; k++){
dp[k][i][j] = 0;
}
}
}
//初期条件として，最初の2日分を代入
if(plan[0] == -1 && plan[1] == -1){//予定なし→予定なし
for(i = 0; i < 3; i++){
for(j = 0; j < 3; j++){
dp[1][i][j] = 1;
}
}
}else if(plan[0] == -1 && plan[1] != -1){//予定なし→予定あり
for(i = 0; i < 3; i++){
dp[1][plan[1]][i] = 1;
}
}else if(plan[0] != -1 && plan[1] == -1){//予定あり→予定なし
for(i = 0; i < 3; i++){
dp[1][i][plan[0]] = 1;
}
}else if(plan[0] != -1 && plan[1] != -1){
dp[1][plan[1]][plan[0]] = 1;
}
for(i = 2; i < n; i++){
if(plan[i] != -1){//今日の用事がある場合は
//dp[i][plan[i]][0] = dp[i - 1][0][1:3];
for(j = 0; j < 3; j++){
for(k = 0; k < 3; k++){
if(plan[i] == k && k == j){
continue;
}
dp[i][plan[i]][k] += dp[i - 1][k][j];
dp[i][plan[i]][k] = dp[i][plan[i]][k] % 10000;
}
}
}else{
for(j = 0; j < 3; j++){
for(k = 0; k < 3; k++){
for(m = 0; m < 3; m++){
if(j == k && k == m){
continue;
}
dp[i][j][k] += dp[i - 1][k][m];
dp[i][j][k] = dp[i][j][k] % 10000;
}
}
}
}
}
long long int ans = 0;
for(i = 0; i < 3; i++){
for(j = 0; j < 3; j++){
ans += dp[n-1][i][j];
}
}
ans = ans % 10000;
printf("%lld\n", ans);
}
問題41-50
41
問題のポイント
条件付きのDPです．制約条件がかかっている場合に評価値を最大にするよう実装する必要があります．このような絶対値の和を求める問題もDPで求まるとは少し驚きです．
ちなみに，解説にはDPよりさらに効率のよい解法が紹介されています．
解答
# include <stdio.h>
int abs(int a, int b){return a > b ? a - b: b - a;}
int max(int a, int b){return a > b ? a : b;}
int main(void){
int D, N;
int m_large = -100000000;
scanf("%d%d", &D, &N);
int i, j, k;
int T[200], A[200], B[200], C[200];
for(i = 0; i < D; i++){
scanf("%d", &T[i]);
}
for(i = 0; i < N; i++){
scanf("%d%d%d", &A[i], &B[i], &C[i]);
}
int dp[200][200];
for(i = 0; i < N; i++){
if(A[i] <= T[0] && T[0] <= B[i]){
dp[0][i] = 0;
}else{
dp[0][i] = m_large;
}
}
//ある服iからjに変えたときの派手さの差の絶対値を求める
int hadesa[200][200];
for(i = 0; i < N; i++){
for(j = 0; j < N; j++){
hadesa[i][j] = abs(C[i], C[j]);
}
}
int ii;
for(i = 0; i < D; i++){
for(j = 0; j < N; j++){
dp[i+1][j] = m_large;
if(A[j] <= T[i+1] && T[i+1] <= B[j]){
for(ii = 0; ii < N; ii++){
dp[i+1][j] = max(dp[i+1][j], dp[i][ii] + hadesa[ii][j]);
}
}
}
}
int ans = m_large;
for(i = 0; i < N; i++){
ans = max(dp[D-1][i], ans);
}
printf("%d\n", ans);
return 0;
}
42
問題のポイント
これもDPをきちっと組めれば解答までたどり着くはずです．
解答
# include <stdio.h>
int dp[1001][1001];
int min(int a, int b){return a > b ? b : a;}
int main(void){
int large_num = 1000000000;
int N, M;//M:days N:citys
scanf("%d%d", &N, &M);
int i, j;
int c[1000], d[1000];
for(i = 0; i < N; i++){
scanf("%d", &d[i]);
}
for(i = 0; i < M; i++){
scanf("%d", &c[i]);
}
for(i = 0; i <= M; i++){
for(j = 0; j <= N; j++){
dp[i][j] = large_num;
}
}
for(i = 0; i <= M; i++){
dp[i][0] = 0;//初期条件:都市0に居続けるニートは疲労度0
}
int mov, stay;
for(i = 0; i < M; i++){
for(j = 1; j <= N; j++){
mov = dp[i][j - 1] + d[j - 1]*c[i];
stay = dp[i][j];
dp[i + 1][j] = min(mov, stay);
}
}
printf("%d\n", dp[M][N]);
return 0;
}
43
問題のポイント
DPっぽくないのですが，実はDPで解くと効率がいいっていう問題ですね．
今回はDPの練習問題として解いていますが，実践では思いつくんでしょうか．
問題をうまいことすると実は漸化式が立てられることに気づけばいいんでしょうか，これ実践でDPで解けるやんって気づいたら気持ちいいでしょうね．
解答
#include <stdio.h>
int min(int a, int b){return a > b ? b : a;}
int main(void){
int N;
scanf("%d", &N);
int i, j, k;
char tmp[999];
int c[5][999];
for(i = 0; i < 5; i++){
scanf("%s", tmp);
for(j = 0; j < N; j++){
if(tmp[j] == '#'){
c[i][j] = -1;
}
if(tmp[j] == 'R'){
c[i][j] = 0;
}
if(tmp[j] == 'B'){
c[i][j] = 1;
}
if(tmp[j] == 'W'){
c[i][j] = 2;
}
}
}
int dp[999][3];
int cnt;
for(j = 0; j < 3; j++){
cnt = 0;
for(i = 0; i < 5; i++){
if(c[i][0] != j){
cnt++;
}
}
dp[0][j] = cnt;
}
int col;
for(col = 1; col < N; col++){
for(i = 0; i < 3; i++){//色
cnt = 0;
for(j = 0; j < 5; j++){
if(c[j][col] != i){
cnt++;
}
}
if(i == 0){
dp[col][i] = min(dp[col-1][1], dp[col-1][2]) + cnt;
}else if(i == 2){
dp[col][i] = min(dp[col-1][1], dp[col-1][0]) + cnt;
}else if(i == 1){
dp[col][i] = min(dp[col-1][2], dp[col-1][0]) + cnt;
}
}
}
int ans;
ans = min(dp[N - 1][0], dp[N - 1][1]);
ans = min(ans, dp[N - 1][2]);
printf("%d\n", ans);
}
44
問題のポイント
最初にint c[200][1000000]としてDPで解くと，メモリーエラーになります．
なので，それをうまく回避することがpointだと思います．
そもそも，もっとうまいDPのやり方があるのかもしれないのですが．
解答
#include <stdio.h>
int c[2][1000000];//1: 個数 2:和
int large_n = 10000000;
int input_list[100000];
int polo(int x){return x*(x+1)*(x+2)/6;}
int min(int a, int b){return a > b ? b : a;}
int main(void){
int n, i, j, k;
int polo_l[200], cnt;
cnt = 0;
for(i = 0; i < 200; i++){
polo_l[cnt] = polo(i+1);
cnt++;
}
int polo_odd[200], polo_i;
cnt = 0;
for(i = 0; i < 250; i++){
if(polo(i) % 2 == 1){
polo_odd[cnt] = polo(i);
cnt++;
}
}
int len = 0;
while(1){
scanf("%d", &n);
if(n == 0){
break;
}
input_list[len] = n;
len++;
}
for(i = 0; i <= 1000000; i++){//0個しかないと何も作れぬ
c[0][i] = large_n;
}
c[0][0] = 0;
for(i = 1; i < 200; i++){
polo_i = polo_l[i - 1];
for(j = 0; j < 1000000; j++){//和のループ
if(polo_i > j){
c[1][j] = c[0][j];
}else{
c[1][j] = min(c[0][j], c[1][j - polo_i] + 1);
}
}
for(k = 0; k < 1000000 ; k++){
c[0][k] = c[1][k];
}
}
int ans_list1[100000];
for(i = 0; i < len; i++){
ans_list1[i] = c[0][input_list[i]];
}
/////////////////////////////////////////ここから奇数の和
for(i = 0; i <= 1000000; i++){//0個しかないと何も作れぬ
c[0][i] = large_n;
}
c[0][0] = 0;
for(i = 1; i <= cnt; i++){
polo_i = polo_odd[i - 1];
for(j = 0; j < 1000000; j++){//和のループ
if(polo_i > j){
c[1][j] = c[0][j];
}else{
c[1][j] = min(c[0][j], c[1][j - polo_i] + 1);
}
}
for(k = 0; k < 1000000 ; k++){
c[0][k] = c[1][k];
}
}
int ans_list2[100000];
for(i = 0; i < len; i++){
ans_list2[i] = c[0][input_list[i]];
}
for(i = 0; i < len; i++){
printf("%d %d", ans_list1[i], ans_list2[i]);
printf("\n");
}
return 0;
}
45
問題のポイント
DPの組み方にも工夫が必要です．
for文を使って逐次的に更新していくわけですが，一番外側のfor文はDPを使う時点で自ずと決まってきますが，その内側のfor文をどうするか，を考える必要がありました．
解答
#include <stdio.h>
int sq(int a){return a*a;}
int min(int a, int b){return a > b ? b : a;}
int main(void){
int i, j, k;
int large_n = 1000000000;
while(1){
int N, M;
scanf("%d%d", &N, &M);
if(N == 0 && M == 0){
break;
}
int c[16], x[20000];
for(i = 0; i < M; i++){
scanf("%d", &c[i]);//サンプルのリスト：長さM
}
for(i = 0; i < N; i++){
scanf("%d", &x[i]);//データのリスト：長さN
}
int dp[2][256];
for(i = 0; i < 256; i++){
dp[0][i] = large_n;
dp[1][i] = large_n;
}
dp[0][128] = 0;
int j_tmp;
for(i = 0; i < N; i++){
for(j = 0; j < 256; j++){
for(k = 0; k < M; k++){
j_tmp = j + c[k];
j_tmp = j_tmp < 0 ? 0: j_tmp;
j_tmp = j_tmp > 255 ? 255: j_tmp;
dp[1][j_tmp] = min(dp[0][j] + sq(j_tmp - x[i]), dp[1][j_tmp]);
}
}
for(j = 0; j < 256; j++){
dp[0][j] = dp[1][j];
dp[1][j] = large_n;
}
}
int ans = large_n;
for(i = 0; i < 256; i++){
ans = min(dp[0][i], ans);
}
printf("%d\n", ans);
}
return 0;
}
46
問題のポイント
行列の計算ってこうやって効率的にやっているんですね，とちょっと驚きました．他にもいろいろ効率的なやり方があるんでしょうけど．ぐぐれば色々出てくるので，それを参考にして解きました．配列番号を間違えずにコードを組む必要があります．
解答
# include <stdio.h>
long long int min(long long int a, long long int b){return a < b ? a : b;}
int main(void){
int n, i, j, k;
scanf("%d", &n);
int r[100], c[100], q[101];
int large_N = 10000000;
for(i = 0; i < n; i++){
scanf("%d%d", &r[i], &c[i]);
q[i + 1] = c[i];
}
q[0] = r[0];
long long int dp[100][100];
for(i = 0; i < n; i++){
dp[i][i] = 0;
}
int row, col;
long long int tmp;
for(i = 1; i <= n; i++){
for(j = 0; j < n - i; j++){
row = j;
col = i + j;
dp[row][col] = large_N;
for(k = 0; k < i; k++){
tmp = q[row]*q[col-i+k+1]*q[col + 1];
dp[row][col] = min(dp[row][col], dp[row][col-i+k] + dp[row + 1 + k][col] + tmp);
}
}
}
printf("%lld\n", dp[0][n-1]);
}
47
問題のポイント
円環構造となり少しいままでの問題とは違いますが，これもDPで解けます．
私はdp[食べた個数-1][何個目のケーキから食べたか]で記録したのですが，問題の解説はもっとスマートに解いているそうです．
解答
#include <stdio.h>
long long int dp[2000][2000];
int main(void){
long long int small_n = -1000000000;
small_n *= 2000;
int n;
scanf("%d", &n);
int i, j;
int a[2000];
for(i = 0; i < n; i++){
scanf("%d", &a[i]);
}
for(i = 0; i < n; i++){
dp[0][i] = a[i];//1成分：(二人が)食べた個数-1，2成分：何番目のケーキから
}
long long int l, r, tmp1, tmp2;
for(i = 1; i < n; i++){//i:食べた個数
if(i % 2 == 1){//IOIのターン
for(j = 0; j < n; j++){
tmp1 = small_n;
tmp2 = small_n;
//パターン1
l = j - 1;
r = j + i;
if(l < 0){
l += n;
}
if(r >= n){
r -= n;
}
if(a[l] <= a[r]){
tmp1 = dp[i-1][j];
}
//パターン2
l = j;
r = j + i + 1;
if(r >= n){
r -= n;
}
if(a[l] >= a[r]){
if(j + 1 < n){
tmp2 = dp[i-1][j+1];
}else{
tmp2 = dp[i-1][j+1-n];
}
}
dp[i][j] = tmp1 > tmp2 ? tmp1 : tmp2;
}
}else if(i % 2 == 0){
//パターン1
for(j = 0; j < n; j++){
if(i + j < n){
tmp1 = dp[i-1][j] + a[j+i];
}else{
tmp1 = dp[i-1][j] + a[j+i-n];
}
if(j+1 < n){
tmp2 = dp[i-1][j+1] + a[j];
}else{
tmp2 = dp[i-1][j+1-n] + a[j];
}
dp[i][j] = tmp1 > tmp2 ? tmp1 : tmp2;
}
}
}
long long int ans = small_n;
for(i = 0; i < n; i++){
ans = ans > dp[n-1][i] ? ans : dp[n-1][i];
}
printf("%lld\n", ans);
}
48
問題のポイント
DPの練習になるいい問題です．
100問精選のサイトにもリンクが張られていたこちらのサイトをほとんど真似しました．
解答
#include <stdio.h>
#include<math.h>
int max(int a, int b){return a > b ? a : b;}
int main(void){
int n, w[300];
int dp[301][301];//区間[i, j)で完全に取り除くことのできるブロック数
int i, j, k;
int r, l, m;
while(1){
scanf("%d", &n);
if(n == 0){
break;
}
for(i = 0; i < n; i++){
scanf("%d", &w[i]);
}
for(i = 0; i <= n; i++){
for(j = 0; j <= n; j++){
dp[i][j] = 0;
}
}
for(k = 2; k <= n; k++){//何個のブロックを取るか
for(l = 0; l < n; l++){
r = k + l;
if(r > n){
continue;
}
if(dp[l + 1][r - 1] == k - 2 && abs(w[l] - w[r - 1]) <= 1){
dp[l][r] = k;
}
for(m = l; m <= r; m++){
dp[l][r] = max(dp[l][r] , dp[l][m] + dp[m][r]);
}
}
}
printf("%d\n", dp[0][n]);
}
return 0;
}
49
問題のポイント
bit DPの問題です．
bit計算に慣れなければと思いました．
解答
# include <stdio.h>
int large_n = 1000000;
int dp[1 << 15][15];
int dist[15][15];
int min(int a, int b){return a < b ? a : b;}
int main(void){
int v, e;
scanf("%d%d", &v, &e);
int i, j, k, m;
for(i = 0; i < v; i++){
for(j = 0; j < v; j++){
dist[i][j] = large_n;
}
}
int s, t, d;
for(i = 0; i < e; i++){
scanf("%d%d%d", &s, &t, &d);
dist[s][t] = d;
}
int ans = large_n/10;
for(int orig = 0; orig < v; orig++){
for(i = 0; i < v; i++){
for(j = 0; j < (1 << v); j++){
dp[j][i] = large_n;
}
}
for(i = 0; i < v; i++){
dp[0][i] = 0;
}
for(i = 0; i < v; i++){
dp[1 << i][i] = dist[orig][i];
}
int bit = 0;
for(i = 2; i <= v; i++){
for(bit = 0; bit < (1 << v); bit++){
if(__builtin_popcount(bit) != i){
continue;
}
for(j = 0; j < v; j++){
if(bit & (1 << j)){//j 番目のフラグが立っている場合
//ここから，dp[bit][j]を求める，
dp[bit][j] = large_n;
for(m = 0; m < v; m++){//最後から2番目の町mでfor文を回す
if(j == m){//最後から1番目とかぶったらスルー
continue;
}
if(bit & (1 << m)){//訪れた都市の中に最後から2番目の町が入っている場合のみ実行
int val = dp[bit & ~(1 << j)][m] + dist[m][j];
dp[bit][j] = min(dp[bit][j], val);
}
}
}
}
}
}
for(i = 0; i < v; i++){
if(ans > dp[(1 << v) - 1][i]){
ans = min(ans, dp[(1 << v) - 1][orig]);
}
}
}
if(ans == large_n/10){
printf("-1\n");
return 0;
}
printf("%d\n", ans);
}
50
問題のポイント
時間管理の機能を付け足すだけです．
解答
#include <stdio.h>
long long int dist[16][16], time[16][16];
long long int dp[1 << 16][16], dp_cnt[1 << 16][16];
long long int large_n = 100000000000000000;
int main(void){
int n, m;
scanf("%d%d", &n, &m);
int i, j, k;
long long int _s, _t, _d, _time;
for(i = 0; i < n; i++){
for(j = 0; j < n; j++){
dist[i][j] = large_n;
time[i][j] = 0;
}
}
for(i = 0; i < m; i++){
scanf("%lld%lld%lld%lld", &_s, &_t, &_d, &_time);
dist[_s-1][_t-1] = _d;
dist[_t-1][_s-1] = _d;
time[_s-1][_t-1] = _time;
time[_t-1][_s-1] = _time;
}
for(i = 0; i < n; i++){
for(j = 0; j < (1 << n); j++){
dp[j][i] = large_n;
dp_cnt[j][i] = 0;
}
}
for(i = 0; i < n; i++){
dp[0][i] = 0;
dp_cnt[0][i] = 0;
}
for(i = 0; i < n; i++){
if(time[0][i] < dist[0][i]){
dp[1 << i][i] = large_n;
dp_cnt[1 << i][i] = 0;
}else{
dp[1 << i][i] = dist[0][i];
dp_cnt[1 << i][i] = 1;
}
}
long long int bit;
for(i = 2; i <= n; i++){
for(bit = 0; bit < (1 << n); bit++){
if(__builtin_popcount(bit) != i){
continue;
}
for(j = 0; j < n; j++){
if(bit & (1 << j) == 0){
continue;
}
dp[bit][j] = large_n;
for(int m = 0; m < n; m++){
if(j == m){
continue;
}
if(bit & (1 << m)){
long long int val = dp[bit & ~(1 << j)][m] + dist[m][j];
if(val > time[m][j]){
val = large_n;
}
if(dp[bit][j] > val){
dp[bit][j] = val;
dp_cnt[bit][j] = dp_cnt[bit & ~(1 << j)][m];
}else if(dp[bit][j] == val){
dp_cnt[bit][j] += dp_cnt[bit & ~(1 << j)][m];
}
}
}
}
}
}
if(dp[(1 << n) - 1][0] == large_n){
printf("IMPOSSIBLE\n");
}else{
printf("%lld %lld\n",dp[(1 << n) - 1][0], dp_cnt[(1 << n) - 1][0]);
}
return 0;
}
問題51-60
51
問題のポイント
セールスマン問題が解けたら楽勝でしょ！
解答
#include <stdio.h>
int dp[1000][1 << 3];
int main(void){
int n;
scanf("%d", &n);
int i, j, k;
char tmp[1001];
int seki[1000];
scanf("%s", tmp);
for(i = 0; i < n; i++){
if(tmp[i] == 'J'){
seki[i] = 0;
}else if(tmp[i] == 'O'){
seki[i] = 1;
}else if(tmp[i] == 'I'){
seki[i] = 2;
}else{
printf("error\n");
return 0;
}
}
for(i = 0; i < 1 << 3; i++){
if((i & 1 << 0) && (i & 1 << seki[0])){//Jがいれば
dp[0][i] = 1;
}else{
dp[0][i] = 0;
}
}
for(int days = 1; days < n; days++){//厳密にはdays = 日数マイナス1
for(i = 0; i < 1 << 3; i++){
dp[days][i] = 0;
if(i & 1 << seki[days]){//責任者がいない場合は0
//何もしない
}else{
continue;
}
for(j = 0; j < 1 << 3; j++){//昨日のメンバ(bit形式)
//昨日と今日で共通の人物がいれば足す
if(i & j){
dp[days][i] += dp[days-1][j];
}
}
dp[days][i] %= 10007;
}
}
int ans = 0;
for(i = 0; i < 1 << 3; i++){
ans += dp[n - 1][i];
}
ans %= 10007;
printf("%d\n", ans);
return 0;
}
52
問題のポイント
さすがに，べたに巡回セールスマン問題を解かせる問題はべたすぎるので，
おそらく，競技プログラミングの実践ではこういう一ひねり必要なbitDP問題が出るんでしょうか．
難しいですね．
解答
#include <stdio.h>
long long int dp[(1 << 21)];//1048576 = 2^20
long long int s[20][100001];
long long int bit_len[(1 << 20)];
long long int min(long long int a, long long int b){return a < b ? a : b;}
int main(void){
long long int large_n = 10000000;
long long int n, m;
long long int i, j, k;
long long int a[100000];
long long int len[20];
long long int val;
unsigned int bit;
scanf("%lld%lld", &n, &m);
for(i = 0; i < m; i++){
len[i] = 0;
}
for(i = 0; i < n; i++){
scanf("%lld", &a[i]);
a[i]--;
len[a[i]]++;
}
for(i = 0; i < (1 << m); i++){
bit_len[i] = 0;
for(j = 0; j < m; j++){
if(i & (1 << j)){
bit_len[i] += len[j];
}
}
}
for(i = 0; i < m; i++){
for(j = 0; j < n + 1; j++){
if(j == 0){
s[i][j] = 0;
}else{
if(a[j-1] == i){
s[i][j] = s[i][j-1];
}else{
s[i][j] = s[i][j-1] + 1;
}
}
}
}
for(i = 0; i < (1 << m); i++){
dp[i] = large_n;
}
dp[0] = 0;
for(i = 1; i <= m; i++){
for(bit = 0; bit < (1 << m); bit++){
if(__builtin_popcount(bit) != i){
continue;
}
dp[bit] = large_n;
for(j = 0; j < m; j++){
//j番目のbitにフラグが立っている場合のみ実行，それ以外はスキップ
if(bit & (1 << j)){
}else{
continue;
}
val = s[j][bit_len[bit]] - s[j][bit_len[bit] - len[j]];
val += dp[bit & ~(1 << j)];
dp[bit] = min(dp[bit], val);
}
}
}
printf("%lld\n", dp[(1 << m) - 1]);
}
53
問題のポイント
最長増加部分列について理解し，実装することがポイントです．
なんとなくわかったようなわからないような．
また，二分探索の実装も必要です．同じ要素が含まれている二分探索，苦手なんですよね．いつかきちんとした形で整理したいです．
解答
#include <stdio.h>
int main(void){
int n;
scanf("%d", &n);
int a[100000];
int i, j;
int large_n = 2000000000;
for(i = 0; i < n; i++){
scanf("%d", &a[i]);
}
int b[100000], l, r;
for(i = 0; i < n; i++){
b[i] = large_n;
}
j = 0;
b[0] = a[0];
for(i = 1; i < n; i++){
if(b[j] < a[i]){
j++;
b[j] = a[i];
}else if(b[j] == a[i]){
continue;
}else if(b[0] >= a[i]){
b[0] = a[i];
continue;
}else{
l = 0;
r = j;
while(r - l != 1){
int mid = (r + l)/2;
if(b[mid] < a[i]){
l = mid;
}else if(b[mid] > a[i]){
r = mid;
}else if(b[mid] == a[i]){
r--;
}
}
b[r] = a[i];
}
}
for(i = 0; i < n; i++){
if(b[i] == large_n){
printf("%d\n", i);
return 0;
}
}
printf("%d\n", n);
return 0;
}
54
問題のポイント
いやこれほとんど問題53のコピペでいけるやーん
解答
#include <stdio.h>
int main(void){
int n;
scanf("%d", &n);
int c[30000], b[30000];
int i, j, k;
for(i = 0; i < n; i++){
scanf("%d", &c[i]);
}
int large_n = 2000000000, l, r;
for(i = 0; i < n; i++){
b[i] = large_n;
}
j = 0;
b[0] = c[0];
for(i = 1; i < n; i++){
if(b[j] < c[i]){
j++;
b[j] = c[i];
}else if(b[j] == c[i]){
continue;
}else if(b[0] >= c[i]){
b[0] = c[i];
continue;
}else{
l = 0;
r = j;
while(r - l != 1){
int mid = (r + l)/2;
if(b[mid] < c[i]){
l = mid;
}else if(b[mid] > c[i]){
r = mid;
}else if(b[mid] == c[i]){
r--;
}
}
b[r] = c[i];
}
}
for(i = 0; i < n; i++){
if(b[i] == large_n){
printf("%d\n", n - i);
return 0;
}
}
printf("%d\n", 0);
return 0;
}
55
問題のポイント
100問精選のサイトには，その他DP(最長増加部分列問題)の問題として紹介されていましたが，この考え方で解くとTLEする気がします(私のコードの方法が間違っていただけかもしれませんが)．確かに，最長増加部分列問題っぽい問題ですが．
解説を見ると，どうやら違う解法が紹介されていたので，その方法で解きました．
解答
#include <stdio.h>
int main(void){
int n;
int a[100000];
int b[100000];
int i, j, k;
scanf("%d", &n);
for(i = 0; i < n; i++){
scanf("%d", &a[i]);
}
b[0] = a[n-1];
int cnt = 1;
int mid;
for(i = n - 2; i >= 0; i--){
int tmp = 0;
//塗る事の出来る色をカウント
//a[i]を何かの色で塗りたい
//bはソートされているため，b[j] > a[i]を満たす最小のb[j]をとるjの値を二分探索で求める
if(b[cnt - 1] <= a[i]){
b[cnt] = a[i];
j = cnt;
cnt++;
}else if(b[0] > a[i]){
j = 0;
b[j] = a[i];
}else{
int r = cnt;
int l = 0;
while(r - l != 1){
mid = (r + l) / 2;
if(b[mid] < a[i]){
l = mid;
}else if(b[mid] > a[i]){
r = mid;
}else{
l = mid;
}
}
j = r;
b[j] = a[i];
}
}
printf("%d\n", cnt);
return 0;
}
56
問題のポイント
ダイグストラ法の実装
解答
#include <stdio.h>
#include <stdlib.h>
long long int largeN = 1000000000000;
int i, j, k;
int V, E, R;
int s[500000], t[500000];
long long int d[500000];
int *tree[500000], *tree_dist[500000];
int cnt[500000];
int cnts[500000];
int queue[500000], queue_d[500000], dist;
int main(void){
scanf("%d%d%d", &V, &E, &R);
for(i = 0; i < V; i++){
cnt[i] = 0;
cnts[i] = 0;
}
for(i = 0; i < E; i++){
scanf("%d%d%d", &s[i], &t[i], &d[i]);
cnt[s[i]]++;
}
for(i = 0; i < V; i++){
tree[i] = (int *)malloc(sizeof(int)*(cnt[i] + 1));
if(tree[i] == NULL){
return 0;
}
}
for(i = 0; i < V; i++){
tree_dist[i] = (int *)malloc(sizeof(int)*(cnt[i] + 1));
if(tree_dist[i] == NULL){
return 0;
}
}
for(i = 0; i < E; i++){
tree[s[i]][cnts[s[i]]] = t[i];
tree_dist[s[i]][cnts[s[i]]] = d[i];
cnts[s[i]]++;
}
for(i = 0; i < V; i++){
d[i] = largeN;
}
int q;
int l = 0;
int r = 1;
queue[0] = R;
queue_d[0] = 0;
d[R] = 0;
while(l != r){
q = queue[l];
dist = queue_d[l];
l++;
if(dist > d[q]){
continue;
}
for(i = 0; i < cnt[q]; i++){
if(d[tree[q][i]] > tree_dist[q][i] + dist){
queue[r] = tree[q][i];
queue_d[r] = tree_dist[q][i] + dist;
d[tree[q][i]] = tree_dist[q][i] + dist;
r++;
}
}
}
for(i = 0; i < V; i++){
if(d[i] == largeN){
printf("INF\n");
}else{
printf("%lld\n", d[i]);
}
}
}
57
問題のポイント
56の問題を少し改変するだけです．
解答
#include <stdio.h>
#include <stdlib.h>
int tree[100][1000], tree_dist[100][1000], tree_cnt[100];
int s, e;
int C, D, E;
int dist[100];
int queue[1000], queue_d[1000];
int main(void){
int n, k;
scanf("%d%d", &n, &k);
int d;
int i, j;
for(i = 0; i < n; i++){
tree_cnt[i] = 0;
}
int large_n = 1000000000;
for(i = 0; i < k; i++){
int lin1;
scanf("%d", &lin1);
if(lin1 == 0){//注文票
scanf("%d%d", &s, &e);
s--;
e--;
for(j = 0; j < n; j++){
dist[j] = large_n;
}
dist[s] = 0;
int r = 1;
int l = 0;
queue[0] = s;
queue_d[0] = 0;
while(r != l){
int q = queue[l];
int q_dist = queue_d[l];
l++;
if(q_dist > dist[q]){
continue;
}
for(int ii = 0; ii < tree_cnt[q]; ii++){
if(dist[tree[q][ii]] > tree_dist[q][ii] + q_dist){
queue[r] = tree[q][ii];
queue_d[r] = tree_dist[q][ii] + q_dist;
dist[tree[q][ii]] = tree_dist[q][ii] + q_dist;
r++;
}
}
}
if(dist[e] == large_n){
printf("-1\n");
}else{
printf("%d\n", dist[e]);
}
}else if(lin1 == 1){//運航情報
scanf("%d%d%d", &C, &D, &E);
C--;
D--;
tree[C][tree_cnt[C]] = D;
tree[D][tree_cnt[D]] = C;
tree_dist[C][tree_cnt[C]] = E;
tree_dist[D][tree_cnt[D]] = E;
tree_cnt[C]++;
tree_cnt[D]++;
}
}
return 0;
}
58
問題のポイント
ダイグストラ法も使うのですが，どちらかというと実装問題に近いですね．
解答
#include <stdio.h>
#include <stdlib.h>
int *tree[100000];
long long int large_int_n = 1000000000000000;
int queue[1000000];
int cnt[100000], cnts[100000];
int a[200000], b[200000];
int c[100000];
long long int cost[100000];
int dist_from_kiken[100000];
long long int queue_cost[1000000];
long long int cost_sum[100000];
int main(void){
int n, m, k, s;
scanf("%d%d%d%d", &n, &m, &k, &s);
int p, q;
scanf("%d%d", &p, &q);
int i, j;
for(i = 0; i < n; i++){
cnt[i] = 0;
cnts[i] = 0;
}
for(i = 0; i < k; i++){
scanf("%d", &c[i]);
c[i]--;
}
for(i = 0; i < m; i++){
scanf("%d%d", &a[i], &b[i]);
a[i]--;
b[i]--;
cnt[a[i]]++;
cnt[b[i]]++;
}
//tree形式に変換
for(i = 0; i < n; i++){
tree[i] = (int *)malloc(sizeof(int)*(cnt[i] + 1));
if(tree[i] == NULL){
return 0;
}
}
for(i = 0; i < m; i++){
tree[a[i]][cnts[a[i]]] = b[i];
tree[b[i]][cnts[b[i]]] = a[i];
cnts[a[i]]++;
cnts[b[i]]++;
}
//危険な町or安全な町orゾンビ町を判別し，価格を記録
for(i = 0; i < n; i++){
dist_from_kiken[i] = -100;
}
//幅優先探索で計算
int r = 0;
int l = 0;
for(i = 0; i < k; i++){
queue[i] = c[i];
r++;
dist_from_kiken[c[i]] = 0;
}
int q_i;
while(r != l){
q_i = queue[l];
l++;
for(i = 0; i < cnt[q_i]; i++){
//tree[q_i][i]をqueueに入れる，探索済みでなければ
if(dist_from_kiken[tree[q_i][i]] == -100){
queue[r] = tree[q_i][i];
dist_from_kiken[tree[q_i][i]] = dist_from_kiken[q_i] + 1;
r++;
}
}
}
for(i = 0; i < n; i++){
if(dist_from_kiken[i] == -100){
cost[i] = p;
}else if(dist_from_kiken[i] == 0){
cost[i] = large_int_n;
}else if(dist_from_kiken[i] <= s){
cost[i] = q;
}else{
cost[i] = p;
}
}
cost[n-1] = 0;
long long int ans = 0;
//ダイグストラ法を用い，コスト最小の経路を求める
for(i = 0; i < n; i++){
cost_sum[i] = large_int_n;
}
cost_sum[0] = 0;
r = 1;
l = 0;
queue[0] = 0;
queue_cost[0] = 0;
cost_sum[0] = 0;
while(r != l){
q_i = queue[l];
long long int q_cost = queue_cost[l];
l++;
if(cost_sum[q_i] < q_cost){
continue;
}
for(i = 0; i < cnt[q_i]; i++){
//tree[q_i][i]をqueueに入れる
int q_j = tree[q_i][i];
if(cost_sum[q_j] > cost[q_j] + q_cost){
cost_sum[q_j] = cost[q_j] + q_cost;
queue_cost[r] = cost[q_j] + q_cost;
queue[r] = q_j;
r++;
}
}
}
printf("%lld\n", cost_sum[n-1]);
return 0;
}
59
問題のポイント
これも実装が重いです．
解答
#include <stdio.h>
#include <stdlib.h>
int *tree[5000];
int *cost[5000];
int *bl_r[5000];
int cnt[5000], cnts[5000];
int queue[500000];
int queue_cost[500000];
int dist[5000][5000];
int large_n = 100000000;
int cost_sum[5000];
int main(void){
int i, j;
int n, k;
scanf("%d%d", &n, &k);
int c[5000], R[5000];
for(i = 0; i < n; i++){
cnt[i] = 0;
cnts[i] = 0;
}
for(i = 0; i < n; i++){
scanf("%d%d", &c[i], &R[i]);
}
int a[10000], b[10000];
for(i = 0; i < k; i++){
scanf("%d%d", &a[i], &b[i]);
a[i]--;
b[i]--;
cnt[a[i]]++;
cnt[b[i]]++;
}
for(i = 0; i < n; i++){
tree[i] = (int *)malloc(sizeof(int)*(cnt[i] + 1));
if(tree[i] == NULL){
return 0;
}
}
for(i = 0; i < k; i++){
tree[a[i]][cnts[a[i]]] = b[i];
tree[b[i]][cnts[b[i]]] = a[i];
cnts[a[i]]++;
cnts[b[i]]++;
}
for(i = 0; i < n; i++){
for(j = 0; j < n; j++){
dist[i][j] = large_n;
}
}
int p, q;
//1:町pから町1~nまでの最短経路を求めるwith幅優先探索
for(p = 0; p < n; p++){
int r = 1;
int l = 0;
queue[0] = p;
dist[p][p] = 0;
while(r != l){
int q_i = queue[l];
l++;
for(i = 0; i < cnt[q_i]; i++){
j = tree[q_i][i];
if(dist[p][j] > dist[p][q_i] + 1){
dist[p][j] = dist[p][q_i] + 1;
queue[r] = j;
r++;
}
}
}
}
//ある町からある町までの最短距離の計算：debug用
// for(i = 0; i < n; i++){
// for(j = 0; j < n; j++){
// printf("%d ", dist[i][j]);
// }
// printf("\n");
// }
for(i = 0; i < n; i++){
int cnt_r = 0;
for(j = 0; j < n; j++){
if(i == j){
continue;
}
if(dist[i][j] <= R[i]){
cnt_r++;
}
}
cnt[i] = cnt_r++;
cnts[i] = 0;
}
for(i = 0; i < n; i++){
cost[i] = (int *)malloc(sizeof(int)*(cnt[i] + 1));
if(cost[i] == NULL){
return 0;
}
}
for(i = 0; i < n; i++){
bl_r[i] = (int *)malloc(sizeof(int)*(cnt[i] + 1));
if(bl_r[i] == NULL){
return 0;
}
}
for(i = 0; i < n; i++){
for(j = 0; j < n; j++){
if(i == j){
continue;
}
if(dist[i][j] <= R[i]){
cost[i][cnts[i]] = c[i];
bl_r[i][cnts[i]] = j;
cnts[i]++;
}
}
}
for(i = 0; i < n; i++){
cost_sum[i] = large_n;
}
int r = 1;
int l = 0;
queue[0] = 0;
queue_cost[0] = 0;
cost_sum[0] = 0;
while(r != l){
int q_i = queue[l];
int q_i_cost = queue_cost[l];
l++;
if(q_i_cost > cost_sum[q_i]){
continue;
}
for(i = 0; i < cnt[q_i]; i++){
int cost_qi2j = cost[q_i][i];
if(cost_sum[bl_r[q_i][i]] > cost_qi2j + q_i_cost){
cost_sum[bl_r[q_i][i]] = cost_qi2j + q_i_cost;
queue_cost[r] = cost_qi2j + q_i_cost;
queue[r] = bl_r[q_i][i];
r++;
}
}
}
printf("%d\n", cost_sum[n-1]);
}
60
問題のポイント
ワーシャル・フロイド法の実装は簡単なので好きです．
ダイグストラ法の実装が大変だったので尚更好きになりました．
とはいえ計算量が・・・
解答
#include<stdio.h>
long long int dp[9900][9900];
long long int large_n = 100000000000000;
int main(void){
int v, e;
int i, j, k;
int s[9900], t[9900], d[9900];
scanf("%d%d", &v, &e);
for(i = 0; i < v; i++){
for(j = 0; j < v; j++){
dp[i][j] = large_n;
if(i == j){
dp[i][j] = 0;
}
}
}
for(i = 0; i < e; i++){
scanf("%d%d%d", &s[i], &t[i], &d[i]);
dp[s[i]][t[i]] = d[i];
}
for(k = 0; k < v; k++){
for(i = 0; i < v; i++){
for(j = 0; j < v; j++){
dp[i][j] = dp[i][j] > dp[i][k] + dp[k][j] ? dp[i][k] + dp[k][j] : dp[i][j];
}
}
}
for(i = 0; i < v; i++){
if(dp[i][i] < 0){
printf("NEGATIVE CYCLE\n");
return 0;
}
}
for(i = 0; i < v; i++){
for(j = 0; j < v; j++){
if(dp[i][j] > large_n/100){
printf("INF");
}else{
printf("%lld", dp[i][j]);
}
if(j == v - 1){
printf("\n");
}else{
printf(" ");
}
}
}
return 0;
}
問題61-70
61
問題のポイント
最後のmaxminを求めるところがちょっと面倒なだけで(C言語だといちいちループ回すの面倒・・・！！)，ワーシャル・フロイド法の実装が出来れば余裕です．
解答
#include<stdio.h>
int min(int a, int b){return a > b ? b : a;}
int max(int a, int b){return a < b ? b : a;}
int n, m;
int large_n = 1000000;
int dp[300][300];
int i, j, k;
int a[44850], b[44850], t[44850];
int main(void){
scanf("%d%d", &n, &m);
for(i = 0; i < n; i++){
for(j = 0; j < n; j++){
dp[i][j] = large_n;
}
dp[i][i] = 0;
}
for(i = 0; i < m; i++){
scanf("%d%d%d", &a[i], &b[i], &t[i]);
a[i]--;
b[i]--;
dp[a[i]][b[i]] = t[i];
dp[b[i]][a[i]] = t[i];
}
for(k = 0; k < n; k++){
for(i = 0; i < n; i++){
for(j = 0; j < n; j++){
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
}
}
}
int max_dp[300];
for(i = 0; i < n; i++){
max_dp[i] = dp[i][0];
for(j = 1; j < n; j++){
max_dp[i] = max(max_dp[i], dp[i][j]);
}
}
int min_d;
min_d = max_dp[0];
for(i = 1; i < n; i++){
min_d = min(min_d, max_dp[i]);
}
printf("%d\n", min_d);
return 0;
}
62
問題のポイント
経路検索の問題とは一風変わった設問ですが，ワーシャル・フロイド法で解けます．
解答
#include<stdio.h>
int min(int x, int y){return x > y ? y : x;}
int main(void){
int i, j, k;
int h, w;
int c[10][10];
int a[10], tmp;
scanf("%d%d", &h, &w);
for(i = 0; i < 10; i++){
for(j = 0; j < 10; j++){
scanf("%d", &c[i][j]);
}
}
for(i = 0; i < 10; i++){
a[i] = 0;
}
for(i = 0; i < h; i++){
for(j = 0; j < w; j++){
scanf("%d", &tmp);
if(tmp == -1){
continue;
}else{
a[tmp]++;
}
}
}
for(k = 0; k < 10; k++){
for(i = 0; i < 10; i++){
for(j = 0; j < 10; j++){
c[i][j] = min(c[i][j], c[i][k] + c[k][j]);
}
}
}
int ans = 0;
for(i = 0; i < 10; i++){
ans += a[i] * c[i][1];
}
printf("%d\n", ans);
return 0;
}
63
問題のポイント
直接ワーシャルフロイド法を適用する，というわけではないですが，問題の考え方がワーシャルフロイド法チックです．
グラフ理論って奥深いですね．
解答
#include <stdio.h>
long long int min(long long int a, long long int b){return a > b ? b : a;}
int main(void){
int i, j, k;
int n;
long long int a[300][300];
scanf("%d", &n);
for(i = 0; i < n; i++){
for(j = 0; j < n; j++){
scanf("%lld", &a[i][j]);
}
}
long long int large_n = 1000000000000;
long long int dist_min;
long long int d, d_tmp;
long long int ans = 0;
for(i = 0; i < n; i++){
for(j = 0; j < n; j++){
dist_min = large_n;
d = a[i][j];
/*この道路が必要かどうかを判定
ある道路kを介してもっと最短で移動できるような道路であれば，-1をprint
他のあらゆる道路を介しても，最短ではいけないような道路の場合，必要，ansに足す
すべての道路を介しても，イコール以上の場合は，不必要*/
for(k = 0; k < n; k++){
if(i == k || k == j){
continue;
}
d_tmp = a[i][k] + a[k][j];
if(d_tmp < d){
printf("-1\n");
return 0;
}
dist_min = min(dist_min, d_tmp);
}
if(dist_min > d){
ans += d;
}
}
}
printf("%lld\n", ans/2);
return 0;
}
64
問題のポイント
クラスカル法の実装がポイントです．
アルゴリズム自体は単純なのですが，Cで実装となるといろいろ手間です．
例えば，辺の情報(辺を結ぶ2つの頂点とその重さ)を重さ$w$を基準にソート，という処理にも手間がかかりました
(自分のやり方が効率のいい方法かどうかは分からないのですが)．
pythonなら1行で済むのに・・・
解答
#include <stdio.h>
#include <stdlib.h>
int stw[100000][3];
int stw_s[100000][3];
int par[10000];
int root(int x){
if(par[x] == x){return x;}
return par[x] = root(par[x]);
}
int unite(int x, int y){
int rx = root(x);
int ry = root(y);
if(rx == ry){
return 0;
}
par[rx] = ry;
return 1;
}
int compare_int(const void *a, const void *b)
{
return stw[*(int*)a][2] - stw[*(int*)(b)][2];
}
int same(int x, int y){
int rx = root(x);
int ry = root(y);
if(rx == ry){
return 1;
}
return 0;
}
int main(void){
int V, E;
int i, j, k;
int index_E[100000];
scanf("%d%d", &V, &E);
//辺が結ぶ頂点と重さの配列を，重さを基準にソートする
for(i = 0; i < E; i++){
scanf("%d%d%d", &stw[i][0], &stw[i][1], &stw[i][2]);
index_E[i] = i;
}
qsort(index_E, E, sizeof(int), compare_int);
for(i = 0;i < E; i++){
stw_s[i][0] = stw[index_E[i]][0];
stw_s[i][1] = stw[index_E[i]][1];
stw_s[i][2] = stw[index_E[i]][2];
}
//クラスカル法
for(i = 0; i < V; i++){
par[i] = i;
}
long long int ans = 0;
for(i = 0; i < E; i++){
//stw_s[i][]の辺を取り出す
if(same(stw_s[i][0], stw_s[i][1]) == 0){
unite(stw_s[i][0], stw_s[i][1]);
ans += stw_s[i][2];
}
}
printf("%lld\n", ans);
return 0;
}
65
問題のポイント
これもクラスカル法で解けます．
64の問題のコードをほぼ再利用できますね．
解答
#include<stdio.h>
#include <stdlib.h>
int stw[100000][3];
int stw_s[100000][3];
int par[100000];
int root(int x){
if(par[x] == x){return x;}
return par[x] = root(par[x]);
}
int unite(int x, int y){
int rx = root(x);
int ry = root(y);
if(rx == ry){
return 0;
}
par[rx] = ry;
return 1;
}
int compare_int(const void *a, const void *b)
{
return stw[*(int*)a][2] - stw[*(int*)(b)][2];
}
int same(int x, int y){
int rx = root(x);
int ry = root(y);
if(rx == ry){
return 1;
}
return 0;
}
int cost[100000];
int main(void){
int N, M, K;
int i, j, k;
int index_M[100000];
scanf("%d%d%d", &N, &M, &K);
for(i = 0; i < M; i++){
scanf("%d%d%d", &stw[i][0], &stw[i][1], &stw[i][2]);
}
int cnt = 0;
//辺が結ぶ頂点と重さの配列を，重さを基準にソートする
for(i = 0; i < M; i++){
index_M[i] = i;
}
qsort(index_M, M, sizeof(int), compare_int);
for(i = 0;i < M; i++){
stw_s[i][0] = stw[index_M[i]][0];
stw_s[i][1] = stw[index_M[i]][1];
stw_s[i][2] = stw[index_M[i]][2];
}
//クラスカル法
for(i = 0; i < N; i++){
par[i] = i;
}
long long int ans = 0;
for(i = 0; i < M; i++){
//stw_s[i][]の辺を取り出す
if(same(stw_s[i][0], stw_s[i][1]) == 0){
unite(stw_s[i][0], stw_s[i][1]);
cost[cnt] = stw_s[i][2];
cnt++;
}
}
for(i = 0; i < cnt - K + 1; i++){
ans += cost[i];
}
printf("%lld\n", ans);
return 0;
}
66
問題のポイント
これも64，65のコードを再利用できます．
c言語の場合だと，小数の精度に気を付ける必要があります．
私はfloat型を使ったのですが，doubleを使ったほうが良いと思います．
また，変数の型により，使う関数も異なってくるので注意です．
例えば，pow(double型のべき乗), powf(float型のべき乗), powl(long double型のべき乗)など．
(コード提出後に気付いたことなので，下のコードには反映されていません・・・)
解答
#include<stdio.h>
#include<math.h>
#include <stdlib.h>
float stw[4950][3];
float stw_s[4950][3];
int par[100];
int index_M[4950];
int root(int x){
if(par[x] == x){return x;}
return par[x] = root(par[x]);
}
int unite(int x, int y){
int rx = root(x);
int ry = root(y);
if(rx == ry){
return 0;
}
par[rx] = ry;
return 1;
}
int compare_float(const void *a, const void *b)
{
if(stw[*(int*)(a)][2] - stw[*(int*)(b)][2] > 0){
return 1;
}else if(stw[*(int*)(a)][2] - stw[*(int*)(b)][2] < 0){
return -1;
}else{
return 0;
}
}
int same(int x, int y){
int rx = root(x);
int ry = root(y);
if(rx == ry){
return 1;
}
return 0;
}
double ans_list[10000];
int cnt_ans = 0;
int main(void){
int N;
int i, j, k;
float X[100], Y[100], Z[100], R[100], d;
while(1){
scanf("%d", &N);
if(N == 0){
break;
}
for(i = 0; i < N; i++){
scanf("%f%f%f%f", &X[i], &Y[i], &Z[i], &R[i]);
}
int cnt = 0;
for(i = 0; i < N; i++){
for(j = i; j < N; j++){
if(i == j){
continue;
}
stw[cnt][0] = i;
stw[cnt][1] = j;
d = pow(pow(X[i] - X[j], 2) + pow(Y[i] - Y[j], 2) + pow(Z[i] - Z[j], 2), 0.5);
d -= (R[i] + R[j]);
stw[cnt][2] = d <= 0 ? 0 : d;
cnt++;
}
}
//辺が結ぶ頂点と重さの配列を，重さを基準にソートする
for(i = 0; i < cnt; i++){
index_M[i] = i;
}
qsort(index_M, cnt, sizeof(int), compare_float);
for(i = 0;i < cnt; i++){
stw_s[i][0] = stw[index_M[i]][0];
stw_s[i][1] = stw[index_M[i]][1];
stw_s[i][2] = stw[index_M[i]][2];
}
//クラスカル法
for(i = 0; i < N; i++){
par[i] = i;
}
double ans = 0;
for(i = 0; i < cnt; i++){
//stw_s[i][]の辺を取り出す
if(same(stw_s[i][0], stw_s[i][1]) == 0){
unite(stw_s[i][0], stw_s[i][1]);
ans += stw_s[i][2];
}
}
printf("%.3lf\n", ans);
}
return 0;
}
67
問題のポイント
一気にパターン的に解けなくなりました．
とはいえ，$x$座標方向，$y$座標方向のみに注目すると，一次元の問題になりますので，簡単になります．
解答
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int stw[200000][3];
int stw_s[200000][3];
int index_stw[200000];
int par[100000];
int x[100000], y[100000];
int root(int x){
if(par[x] == x){return x;}
return par[x] = root(par[x]);
}
int unite(int x, int y){
int rx = root(x);
int ry = root(y);
if(rx == ry){
return 0;
}
par[rx] = ry;
return 1;
}
int compare_int_x(const void *a, const void *b)
{
return x[*(int*)a] - x[*(int*)(b)];
}
int compare_int_y(const void *a, const void *b)
{
return y[*(int*)a] - y[*(int*)(b)];
}
int compare_int_stw(const void *a, const void *b)
{
return stw[*(int*)a][2] - stw[*(int*)(b)][2];
}
int same(int x, int y){
int rx = root(x);
int ry = root(y);
if(rx == ry){
return 1;
}
return 0;
}
int index_x[100000];
int index_y[100000];
int main(void){
int n;
int i, j, k;
scanf("%d", &n);
for(i = 0; i < n; i++){
scanf("%d%d", &x[i], &y[i]);
index_x[i] = i;
index_y[i] = i;
}
qsort(index_x, n, sizeof(int), compare_int_x);
qsort(index_y, n, sizeof(int), compare_int_y);
int cnt = 0;
for(i = 1; i < n; i++){
stw[cnt][0] = index_x[i];
stw[cnt][1] = index_x[i-1];
stw[cnt][2] = abs(x[index_x[i]] - x[index_x[i-1]]);
cnt++;
}
for(i = 1; i < n; i++){
stw[cnt][0] = index_y[i];
stw[cnt][1] = index_y[i-1];
stw[cnt][2] = abs(y[index_y[i]] - y[index_y[i-1]]);
cnt++;
}
for(i = 0; i < cnt; i++){
index_stw[i] = i;
}
qsort(index_stw, cnt, sizeof(int), compare_int_stw);
for(i = 0; i < cnt; i++){
stw_s[i][0] = stw[index_stw[i]][0];
stw_s[i][1] = stw[index_stw[i]][1];
stw_s[i][2] = stw[index_stw[i]][2];
}
//クラスカル法
for(i = 0; i < n; i++){
par[i] = i;
}
long long int ans = 0;
for(i = 0; i < cnt; i++){
//stw_s[i][]の辺を取り出す
if(same(stw_s[i][0], stw_s[i][1]) == 0){
unite(stw_s[i][0], stw_s[i][1]);
ans += stw_s[i][2];
}
}
printf("%lld\n", ans);
return 0;
}
68
問題のポイント
素数の判定
解答
while文を使ったほうが簡単だったかもしれません
#include <stdio.h>
#include <math.h>
int main(void){
int n;
scanf("%d", &n);
int n_temp = n;
int a[1000];
int cnt = 0;
for(int i = 2; i <= sqrt(n_temp); i++){
if(n_temp%i == 0){
n_temp /= i;
a[cnt] = i;
cnt++;
i--;
}
}
a[cnt] = n_temp; cnt++;
printf("%d:", n);
for(int i = 0; i < cnt; i++){
printf(" %d", a[i]);
}
printf("\n");
}
69
問題のポイント
累積和の考えが必要になると思います
解答
#include <stdio.h>
int isPrime(int n){
if(n == 1){
return 0;
}
if(n == 2){
return 1;
}
if(n == 3){
return 1;
}
if(n == 5){
return 1;
}
if(n%2 == 0){
return 0;
}
if(n%3 == 0){
return 0;
}
if(n%5 == 0){
return 0;
}
for(int i = 3; i*i <= n; i = i + 2){
if(n % i == 0){
return 0;}
}
return 1;
}
int main(void){
int q;
scanf("%d", &q);
int l[500000], r[500000];
int i, j;
int cnt;
for(i = 0; i < q; i++){
scanf("%d%d", &l[i], &r[i]);
}
int cumsum[500000];
cumsum[1] = 0;
for(i = 3; i <= 500000; i = i + 2){
if((isPrime(i) == 1) && (isPrime( (i + 1)/ 2) ) ){
cumsum[i] = cumsum[i-2] + 1;
}else
{
cumsum[i] = cumsum[i-2];
}
}
for(i = 0; i < q; i++){
if(l[i] == 1){
printf("%d\n", cumsum[r[i]]);
}else{
printf("%d\n", cumsum[r[i]] - cumsum[l[i] - 2]);
}
}
return 0;
}
70
問題のポイント
累乗の計算の実装
100問精選にもあったこちらの記事を参考にしました．
解答
#include <stdio.h>
long long int modpow(long long int a, long long int n, long long int mod){
long long int res = 1;
while(n > 0){
if(n & 1){
res = res * a % mod;
}
a = a * a % mod;
n >>= 1;
}
return res;
}
int main(void){
long long int m, n;
scanf("%lld%lld", &m, &n);
printf("%lld\n", modpow(m, n, 1000000007));
return 0;
}
問題71-80
71
問題のポイント
後から出てくる累積和の考えが必要です(なしでも解けるかもしれませんが)
なので，先に累積和の問題を解いてから戻ってくることをお勧めします
解答
#include <stdio.h>
long long int modpow(long long int a, long long int n, long long int mod){
long long int res = 1;
while(n > 0){
if(n & 1){
res = res * a % mod;
}
a = a * a % mod;
n >>= 1;
}
return res;
}
long long int d[119999];
int a[120000], c[120002];
long long int s[120000];
int main(void){
long long int large_n = 1000000007;
int i, j, k;
int n, q;
scanf("%d%d", &n, &q);
for(i = 0; i < n; i++){
scanf("%d", &a[i]);
}
c[0] = 1;
for(i = 0; i < q; i++){
scanf("%d", &c[i+1]);
}
c[q+1] = 1;
for(i = 1; i < n; i++){
d[i-1] = modpow(a[i - 1], a[i], large_n);
}
s[0] = 0;
for(i = 0; i < n - 1; i++){
s[i + 1] = s[i] + d[i];
s[i + 1] %= large_n;
}
long long int ans = 0, tmp;
for(i = 0; i < q + 1; i++){
int frm = c[i + 1] - 1;
int to = c[i] - 1;
int small_c = frm < to ? frm : to;
int large_c = frm < to ? to : frm;
tmp = s[large_c] - s[small_c];
tmp = tmp > 0 ? tmp : tmp + large_n;
tmp %= large_n;
ans += tmp;
}
printf("%lld\n", ans%large_n);
return 0;
}
72
問題のポイント
経路計算の問題です．
高校で勉強したやつですね．
組み合わせ計算のコード作成にはこちらのサイトを参考にしました．
解答
#include <stdio.h>
int mod = 1000000007;
const int MAX = 510000;
const int MOD = 1000000007;
long long fac[510000], finv[510000], inv[510000];
void COMinit() {
fac[0] = fac[1] = 1;
finv[0] = finv[1] = 1;
inv[1] = 1;
for (int i = 2; i < MAX; i++){
fac[i] = fac[i - 1] * i % MOD;
inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
finv[i] = finv[i - 1] * inv[i] % MOD;
}
}
long long COM(int n, int k){
if (n < k) return 0;
if (n < 0 || k < 0) return 0;
return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
int main(void){
int w, h;
scanf("%d%d", &w, &h);
COMinit();
printf("%lld\n", COM(w+h-2, w-1)% MOD);
}
73
問題のポイント
72の問題の亜種ですね．
うまくコンビネーションの計算に落とし込むことができるかどうかがポイントです．
解答
#include <stdio.h>
const int MAX = 1000001;
const int MOD = 1000000007;
long long fac[1000001], finv[1000001], inv[1000001];
void COMinit() {
fac[0] = fac[1] = 1;
finv[0] = finv[1] = 1;
inv[1] = 1;
for (int i = 2; i < MAX; i++){
fac[i] = fac[i - 1] * i % MOD;
inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
finv[i] = finv[i - 1] * inv[i] % MOD;
}
}
long long COM(int n, int k){
if (n < k) return 0;
if (n < 0 || k < 0) return 0;
return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
int main(void){
int x, y;
scanf("%d%d", &x, &y);
int n;
if((x + y) % 3 != 0){
printf("0\n");
return 0;
}
n = (x + y)/3;
int x_, y_;
x_ = x - n;
y_ = y - n;
if(x_ < 0 || y_ < 0){
printf("0\n");
return 0;
}
COMinit();
printf("%lld\n", COM(x_+y_, x_)% MOD);
return 0;
}
74
問題のポイント
これも，うまくコンビネーションの計算に落としこめるかどうかが重要です．
解答
#include<stdio.h>
const int MAX = 200001;
const int MOD = 1000000007;
long long fac[200001], finv[200001], inv[200001];
void COMinit() {
fac[0] = fac[1] = 1;
finv[0] = finv[1] = 1;
inv[1] = 1;
for (int i = 2; i < MAX; i++){
fac[i] = fac[i - 1] * i % MOD;
inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
finv[i] = finv[i - 1] * inv[i] % MOD;
}
}
long long COM(int n, int k){
if (n < k) return 0;
if (n < 0 || k < 0) return 0;
return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
int main(void){
int n, k;
scanf("%d%d", &n ,&k);
COMinit();
printf("%lld\n", COM(n + k - 1, k)% MOD);
return 0;
}
75
問題のポイント
よくわかりませんでした．
解説読んでACとれるコードを書いたものの，あんまり理解していません．
初心者の方はやるべきではないでしょう．
解答
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int a[200000], b[200000];
int *tree[200000], d[200000], cnt[200000], cnts[200000];
int n;
long long int modpow(long long int p, long long int n, long long int mod){
long long int res = 1;
while(n > 0){
if(n & 1){
res = res * p % mod;
}
p = p * p % mod;
n >>= 1;
}
return res;
}
long long int modinv(long long int p, long long int mod) {//逆元 p^{-1}の計算
return modpow(p, mod - 2, mod);
}
int DFS(int x, int y){//xが今いる頂点，yが前にいた頂点
int i;
int t = 1, t_tmp;
for(i = 0; i < cnt[x]; i++){
if(y == tree[x][i]){
continue;
}
t += DFS(tree[x][i], x);
}
d[x] = t;
return t;
}
int main(void){
int i, j;
long long int mod = 1000000007;
scanf("%d", &n);
for(i = 0; i < n; i++){
cnt[i] = 0;
cnts[i] = 0;
d[i] = 1;
}
for(i = 0; i < n - 1; i++){
scanf("%d%d", &a[i], &b[i]);
a[i]--;
b[i]--;
cnt[a[i]]++;
cnt[b[i]]++;
}
for(i = 0; i < n; i++){
tree[i] = (int *)malloc(sizeof(int) * (cnt[i] + 1));
if(tree[i] == NULL){
return 0;
}
}
for(i = 0; i < n; i++){
tree[a[i]][cnts[a[i]]] = b[i];
tree[b[i]][cnts[b[i]]] = a[i];
cnts[a[i]]++;
cnts[b[i]]++;
}
DFS(0, -1);
long long int bunnshi = 0;
int x1, x2;
for(i = 0; i < n-1; i++){
x1 = d[a[i]];
x2 = d[b[i]];
if(x1 > x2){
x1 = n - x2;
}else{
x2 = n - x1;
}
bunnshi += modpow(2, n, mod) + 1 - modpow(2, x1, mod) - modpow(2, x2, mod);
bunnshi %= mod;
}
bunnshi += modpow(2, n, mod) - 1 - modpow(2, n-1, mod) * n;
bunnshi %= mod;
long long int bunnbo = modinv(2, mod);//2の逆元
bunnbo = modpow(bunnbo, n, mod);//2の逆元をn乗する
long long int ans = bunnshi*bunnbo%mod;
while(ans < 0){
ans += mod;
}
printf("%lld\n", ans);
return 0;
}
76
問題のポイント
これも桁落ち注意です．ちゃんとテストケースに桁落ちしてないか確認できる入力例があるっていいですね．
累積和の基本的なアルゴリズムが理解できると思います．
解答
#include <stdio.h>
long long int max(long long int a,long long int b){return a > b ? a : b;}
int main(void){
int n;
long long int ans[3000];
scanf("%d", &n);
int i, j, k, a[3000];
for(i = 0; i < n; i++){
scanf("%d", &a[i]);
ans[i] = 0;
}
long long int s[3001];
for(i = 0; i < n + 1; i++){
if(i == 0){
s[i] = 0;
continue;
}
s[i] = s[i - 1] + a[i - 1];
}
for(k = 0; k < n; k++){
for(i = 0; i + k + 1 < n + 1; i++){
ans[k] = max(ans[k], s[i + k + 1] - s[i]);
}
}
for(i = 0; i < n; i++){
printf("%lld\n", ans[i]);
}
}
77
問題のポイント
うーん，累積和がダブルコンボで決められます．
累積和マニアにはたまらない問題ですね．
解答
# include <stdio.h>
int main(void){
int n, m;
int i, j, k;
scanf("%d%d", &n, &m);
long long int d[100000];
long long int s[100001];
s[0] = 0;
for(i = 0; i < n - 1; i++){
scanf("%lld", &d[i]);
s[i + 1] = d[i] + s[i];
}
long long int a[100000];
long long int s_a[100001];
s_a[0] = 0;
for(i = 0; i < m; i++){
scanf("%lld", &a[i]);
s_a[i + 1] = s_a[i] + a[i];
}
long long int ans = 0;
long long int dist;
for(i = 0; i < m; i++){
dist = s[s_a[i + 1]] - s[s_a[i]];
ans += dist > 0 ? dist : -dist;
ans %= 100000;
}
printf("%lld\n", ans);
return 0;
}
78
問題のポイント
累積和の考えを2次元に拡張する必要があります．
さらに，どの部分を足して，どの部分を引くかをある程度は考えないといけないです．
解答
#include <stdio.h>
int J[1001][1001], O[1001][1001], I[1001][1001];
int main(void){
int i, j;
int M, N;
for(i = 0; i < 1001; i++){
J[i][0] = 0;
J[0][i] = 0;
O[i][0] = 0;
O[0][i] = 0;
I[i][0] = 0;
I[0][i] = 0;
}
scanf("%d%d", &M, &N);
int K;
scanf("%d", &K);
char tmp[1001];
for(i = 0; i < M; i++){
scanf("%s", tmp);
for(j = 0; j < N; j++){
J[i + 1][j + 1] = J[i + 1][j] + J[i][j + 1] - J[i][j] ;
O[i + 1][j + 1] = O[i + 1][j] + O[i][j + 1] - O[i][j] ;
I[i + 1][j + 1] = I[i + 1][j] + I[i][j + 1] - I[i][j] ;
if(tmp[j] == 'J'){
J[i + 1][j + 1]++;
}
if(tmp[j] == 'O'){
O[i + 1][j + 1]++;
}
if(tmp[j] == 'I'){
I[i + 1][j + 1]++;
}
}
}
int a, b, c, d;
int ans1, ans2, ans3;
for(i = 0; i < K; i++){
scanf("%d%d%d%d", &a, &b, &c, &d);
ans1 = J[c][d] - J[a-1][d] - J[c][b-1] + J[a-1][b-1];
ans2 = O[c][d] - O[a-1][d] - O[c][b-1] + O[a-1][b-1];
ans3 = I[c][d] - I[a-1][d] - I[c][b-1] + I[a-1][b-1];
printf("%d %d %d\n",ans1 ,ans2, ans3);
}
return 0;
}
79
問題のポイント
うまく累積和の枠組みに落とし込む必要があります(これがなかなか難しい！)
解答
#include <stdio.h>
int L[200000], R[200000], p[100000], q[100000];
int main(void){
int N, M, Q;
int i, j, k;
int S[500][500];//1：スタート，2：ストップ
for(i = 0; i < 500; i++){
for(j = 0; j < 500; j++){
S[i][j] = 0;
}
}
scanf("%d%d%d", &N, &M, &Q);
for(i = 0; i < M; i++){
scanf("%d%d", &L[i], &R[i]);
S[L[i] - 1][R[i] - 1]++;
}
for(i = 0; i < N; i++){
for(j = 1; j < N; j++){
S[i][j] += S[i][j-1];
}
}
for(j = 0; j < N; j++){
for(i = N - 2; i >= 0; i--){
S[i][j] += S[i+1][j];
}
}
for(i = 0; i < Q; i++){
scanf("%d%d", &p[i], &q[i]);
printf("%d\n", S[p[i]-1][q[i]-1]);
}
}
80
問題のポイント
2つ上の惑星探査の問題と似てますね．
どの長方形がいいかの検討が必要ですが，意外にも全探索でいけました．
解答
#include <stdio.h>
long long int S[126][126];
int main(void){
long long int H, W, K, V;
int i, j, k, ii, jj, kk;
scanf("%lld%lld%lld%lld", &H, &W, &K, &V);
for(i = 0; i < 126; i++){
S[i][0] = 0;
S[0][i] = 0;
}
long long int a;
for(i = 0; i < H; i++){
for(j = 0; j < W; j++){
scanf("%lld", &a);
S[i+1][j+1] = S[i][j+1] + S[i+1][j] - S[i][j] + a;
}
}
long long int ans = 0, price, square;
for(i = 0; i < H + 1; i++){
for(ii = i + 1; ii < H + 1; ii++){
for(j = 0; j < W + 1; j++){
for(jj = j + 1; jj < W + 1; jj++){
square = (ii - i) * (jj - j);
price = S[ii][jj] + S[i][j] - S[i][jj] - S[ii][j] + square * K;
if(ans < square && price <= V){
ans = square;
}
}
}
}
}
printf("%lld\n", ans);
}
問題81-90
81
問題のポイント
いもす法の基本問題の実装
解答
#include <stdio.h>
int c[1000002];
int main(void){
int n;
int i, j;
int a, b;
for(i = 0; i < 1000002 ; i++){
c[i] = 0;
}
scanf("%d", &n);
for(i = 0; i < n; i++){
scanf("%d%d", &a, &b);
c[a]++;
c[b+1]--;
}
int score = c[0];
for(i = 0; i < 1000001 ; i++){
c[i + 1] += c[i];
if(score < c[i + 1]){
score = c[i + 1];
}
}
printf("%d\n", score);
}
82
問題のポイント
入力の処理が少し戸惑いますが，他はいもす法を用いれば簡単にできます．
AOJはトリッキーな入力フォーマットが多い気がしますね．
解答
#include <stdio.h>
char num[] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};
int main(void){
int n;
int i, j, k;
while(1){
scanf("%d", &n);
if(n == 0){
break;
}
char tmp;
int h, m, s;
int departure, arrival;
int sum[86401];//1 day = 86400 sec
for(i = 0; i < 86401; i++){
sum[i] = 0;
}
for(i = 0; i < n; i++){
scanf("%d%*c%d%*c%d", &h, &m, &s);
departure = (h * 60 + m)* 60 + s;
sum[departure]++;
scanf("%d%*c%d%*c%d", &h, &m, &s);
arrival = (h * 60 + m)* 60 + s;
sum[arrival]--;
}
int ans = sum[0];
for(i = 0; i < 86400; i++){
sum[i + 1] += sum[i];
if(ans < sum[i + 1]){
ans = sum[i + 1];
}
}
printf("%d\n", ans);
}
return 0;
}
83
問題のポイント
少し考察が必要ですが，たしかに累積法が楽ですね．
int型ですると桁落ちするので，long long int を使う必要があります．
というか，C言語だと適切な解法を用いればACとれるので，念のためにlong long int 型を常に使うよう意識した方がいいですね．今更ですが．
解答
#include <stdio.h>
long long int a[99999], b[99999], c[99999];
long long int p[100000];
long long int cnt[100000];
long long int ICprice[100000];
int main(void){
int n, m;
scanf("%d%d", &n, &m);
int i, j, k;
for(i = 0; i < m; i++){
scanf("%lld", &p[i]);
p[i]--;
}
for(i = 0; i < n-1 ; i++){
scanf("%lld%lld%lld", &a[i], &b[i], &c[i]);
}
//まず，ある鉄道iを何回通ったかを確認
for(i = 0; i < n; i++){
cnt[i] = 0;
}
long long int p_max, p_min;
for(i = 0; i < m - 1; i++){
p_max = p[i + 1] < p[i] ? p[i] : p[i + 1];
p_min = p[i + 1] < p[i] ? p[i + 1] : p[i];
cnt[p_max]--;
cnt[p_min]++;
}
for(i = 0; i < n - 2; i++){
cnt[i + 1] += cnt[i];
}
//次にすべてICを使った場合の運賃合計を計算(カード代は入れない)
long long int price_sum = 0;
ICprice[0] = 0;
for(i = 1; i < n; i++){
ICprice[i] = ICprice[i - 1] + b[i - 1];
}
for(i = 0; i < m - 1; i++){
p_max = p[i + 1] < p[i] ? p[i] : p[i + 1];
p_min = p[i + 1] < p[i] ? p[i + 1] : p[i];
price_sum += ICprice[p_max] - ICprice[p_min];
}
//printf("%lld\n", price_sum);
//もし，ICをかったほうが得だったらカード代を払い，
//そうでない場合は切符払いに切り替え
for(i = 0; i < n - 1; i++){
//カード＋IC料金×乗った回数<切符×乗った回数 なら，カードはらう
if(c[i] + b[i] * cnt[i] < a[i] * cnt[i]){
price_sum += c[i];
}else{//IC料金で計算していたので，差額金を戻す
price_sum -= cnt[i] * b[i];
price_sum += cnt[i] * a[i];
}
}
printf("%lld\n", price_sum);
return 0;
}
84
問題のポイント
いもす法で解けるのですが，どこの配列番号に+1したり―1したりすればいいのかの判断に戸惑います．ですが，それが分かればすぐ解けると思います．
さらに，解説ではいもす法以外のやり方で解いているので，読んでみるといいでしょう．
ちなみに私は+=1と書くべきところを=1としてしまい，30分くらい悩みました(泣)てか++とか使わんかい！
解答
#include <stdio.h>
int cnt1[5002][5002];
int cnt2[5002][5002];
int cnt3[5002][5002];
int main(void){
int n, m;
scanf("%d%d", &n, &m);
int i, j, k;
for(i = 0; i < n + 2; i++){
for(j = 0; j < n + 2; j++){
cnt1[i][j] = 0;
cnt2[i][j] = 0;
}
}
int a, b, x;
for(i = 0; i < m; i++){
scanf("%d%d%d", &a, &b, &x);
cnt1[a][b] += 1;
cnt1[a + x + 1][b + x + 1] += - 1;
cnt2[a + x + 1][b] += - 1;
cnt2[a + x + 1][b + x + 1] += 1;
}
for(i = 0; i < n + 2; i++){
for(j = 1; j < i + 1; j++){
if(i != 0){
cnt1[i][j] += cnt1[i - 1][j - 1];
}
cnt2[i][j] += cnt2[i][j - 1];
}
}
for(i = 0; i < n + 2; i++){
for(j = 0; j < i + 1; j++){
cnt3[i][j] = cnt1[i][j] + cnt2[i][j];
}
}
int ans = 0;
for(i = 1; i < n + 2; i++){
for(j = 0; j < i + 1; j++){
cnt3[i][j] += cnt3[i-1][j];
if(cnt3[i][j]){
ans++;
}
}
}
printf("%d\n", ans);
return 0;
}
85
問題のポイント
基本的なUnionFindアルゴリズムを参考に実装すればいいです．
解答
#include <stdio.h>
int par[10000];
int root(int x){
if(par[x] == x){return x;}
return par[x] = root(par[x]);
}
int unite(int x, int y){
int rx = root(x);
int ry = root(y);
if(rx == ry){
return 0;
}
par[rx] = ry;
return 1;
}
int same(int x, int y){
int rx = root(x);
int ry = root(y);
if(rx == ry){
return 1;
}
return 0;
}
int main(void){
int n ,q;
int i, j;
int a, b, c;
scanf("%d%d", &n, &q);
for(i = 0; i < n; i++){
par[i] = i;
}
for(i = 0; i < q; i++){
scanf("%d%d%d", &a, &b, &c);
if(a == 0){
unite(b, c);
}else{
if(same(b, c)){
printf("1\n");
}else{
printf("0\n");
}
}
}
return 0;
}
86
問題のポイント
これも上の問題の関数をほぼ使いまわしでよいです．
辺の数が少ないので，すべてのMについて，いちいちUnion-Findを構築して，検証するという方法で十分に事足ります．
頂点の番号が1からスタートするため，0スタートの配列番号で管理したい場合は--をする，といった細かいところには気をつけましょう．
解答
#include <stdio.h>
int par[50];
int root(int x){
if(par[x] == x){return x;}
return par[x] = root(par[x]);
}
int unite(int x, int y){
int rx = root(x);
int ry = root(y);
if(rx == ry){
return 0;
}
par[rx] = ry;
return 1;
}
int same(int x, int y){
int rx = root(x);
int ry = root(y);
if(rx == ry){
return 1;
}
return 0;
}
int main(void){
int N, M;
int i, j;
int a[1225], b[1225];
scanf("%d%d", &N, &M);
for(i = 0; i < M; i++){
scanf("%d%d", &a[i], &b[i]);
a[i]--;
b[i]--;
}
int ans = 0;
for(i = 0; i < M; i++){
for(j = 0; j < N; j++){
par[j] = j;
}
for(j = 0; j < M; j++){
if(i == j){
continue;
}
unite(a[j], b[j]);
}
if(same(a[i], b[i]) == 0){
ans++;
}
}
printf("%d\n", ans);
return 0;
}
87
問題のポイント
Union-Findのアルゴリズムを活用して解きます．
少し考えないといけないですね．
解答
#include <stdio.h>
int a[100000], b[100000], par[100000], root_cnt[100000];
int root(int x){
if(par[x] == x){return x;}
return par[x] = root(par[x]);
}
int unite(int x, int y){
int rx = root(x);
int ry = root(y);
if(rx == ry){
return 0;
}
par[rx] = ry;
return 1;
}
int same(int x, int y){
int rx = root(x);
int ry = root(y);
if(rx == ry){
return 1;
}
return 0;
}
long long int ans[100000];
int main(void){
long long int n, m;
int i, j, k;
scanf("%lld%lld", &n, &m);
for(i = 0; i < m; i++){
scanf("%d%d", &a[i], &b[i]);
a[i]--;
b[i]--;
}
for(i = 0; i < n; i++){
par[i] = i;
root_cnt[i] = 1;
}
ans[m-1] = n*(n-1)/2;
root_cnt[root(b[m-1])] += root_cnt[root(a[m-1])];
root_cnt[root(a[m-1])] = 0;
unite(a[m-1], b[m-1]);//bのrootにaが統合される
if(m-2 >= 0){
ans[m-2] = n*(n-1)/2 - 1;
}
for(i = m-2; i >= 0; i--){
if(same(a[i], b[i])){
ans[i-1] = ans[i];
}else{
ans[i-1] = ans[i] - root_cnt[root(b[i])] * root_cnt[root(a[i])];
root_cnt[root(b[i])] += root_cnt[root(a[i])];
root_cnt[root(a[i])] = 0;
unite(a[i], b[i]);//bのrootにaが統合される
}
}
for(i = 0; i < m; i++){
printf("%lld\n",ans[i]);
}
}
88
問題のポイント
圧縮の問題ですが，なかなか解説している記事が少ないですね．
100問精選の上級編の記事にもいくつか圧縮の問題があるそうなので，やってみたいところです．
解答見て解いたんですが，いまいち消化不足な感じです．
解答
#include <stdio.h>
int main(void){
int n;
scanf("%d", &n);
int i, j, k;
int c_old, c_new;
int c[100000];
for(i = 0; i < n; i++){
scanf("%d", &c[i]);
}
int r_index = 0;
int seq_cnt[100000];
seq_cnt[0] = 1;
int left_c = c[0];
int last_c = c[0];
for(i = 1; i < n; i++){
if(last_c == c[i]){
seq_cnt[r_index]++;
}else if(i % 2 == 1){//偶数番目の場合(iは0スタートなので)
if(r_index == 0){
seq_cnt[r_index]++;
left_c = c[i];
}else{
seq_cnt[r_index- 1] += seq_cnt[r_index] + 1;
r_index--;
}
}else{
r_index++;
seq_cnt[r_index] = 1;
}
last_c = c[i];
}
int ans = 0;
if(left_c == 0){
for(i = 0; i <= r_index; i = i + 2){
ans += seq_cnt[i];
}
}else{
for(i = 1; i <= r_index; i = i + 2){
ans += seq_cnt[i];
}
}
printf("%d\n", ans);
}
89
問題のポイント
どういう形式で圧縮するかがポイントのようです．
解答
#include <stdio.h>
int main(void){
int n;
scanf("%d", &n);
int c[100000];
int i, j;
for(i = 0; i < n; i++){
scanf("%d", &c[i]);
}
int r[100000];
int k = 0;
int last_c = c[0];
r[0] = 1;
for(i = 1; i < n; i++){
if(last_c == c[i]){
k++;
r[k] = 1;
}else{
r[k]++;
}
last_c = c[i];
}
int ans;
if(k == 0){
ans = r[0];
}else if(k == 1){
ans = r[0] + r[1];
}else{
ans = 0;
}
int tmp;
for(i = 0; i <= k - 2; i++){
tmp = r[i] + r[i + 1] + r[i + 2];
ans = ans < tmp ? tmp : ans;
}
printf("%d\n", ans);
}
90
問題のポイント
幾何問題です．
自分は二分探索で解いたんですが，解説を見るともっと単純に解けたんですね．難しく考えないようにしないと・・・
解答
# include <stdio.h>
# include <math.h>
double dist(double x1, double y1, double x2, double y2){
return pow((x2 - x1)*(x2 - x1) + (y2 - y1)*(y2 - y1), 0.5);
}
int main(void){
int n, m;
scanf("%d%d", &n, &m);
int i, j, k;
int x[100], y[100], r[100];
int x_m[100], y_m[100];
for(i = 0; i < n; i++){
scanf("%d%d%d", &x[i], &y[i], &r[i]);
}
for(i = 0; i < m; i++){
scanf("%d%d", &x_m[i], &y_m[i]);
}
if(m == 0){//設定できる円がない
double ans = 100000;
for(i = 0; i < n; i++){
ans = ans > r[i] ? r[i] : ans;
}
printf("%.10lf\n", ans);
return 0;
}
double min, max, mid;
int flag;
min = pow(10, -8);
max = pow(200, 2);
while(max - min >= pow(10, -10)){
mid = min + (max - min)/2;
flag = 0;
//printf("%.10lf %.10lf %.10lf\n", max, min, mid);
//判定フェーズ
for(i = 0; i < m; i++){
for(j = 0; j < n; j++){
if(dist(x_m[i], y_m[i], x[j], y[j]) < r[j] + mid){//重なってる
flag = 1;
break;
}
}
for(j = 0; j < m; j++){
if(i == j){
continue;
}
if(dist(x_m[i], y_m[i], x_m[j], y_m[j]) < 2*mid){//重なってる
flag = 1;
break;
}
}
if(flag == 1){
break;
}
}
if(flag == 1){
max = mid;
}else{
min = mid;
}
}
double ans = min;
for(i = 0; i < n; i++){
ans = ans > r[i] ? r[i] : ans;
}
printf("%.10lf\n", ans);
return 0;
}
問題91-100
91
問題のポイント
水筒が傾く様子をうまく場合分けできればそこまで難しくはないと思います．
逆関数，度数法と弧度法の変換の練習にもなります．
解答
# include <stdio.h>
#include <math.h>
double to_deg(double r) {
return r * 180.0 / (atan(1.0) * 4.0);
}
int main(void){
double a, b, x;
scanf("%lf%lf%lf", &a, &b, &x);
int ans;
if(a * a * b * 0.5 < x){
double h;//水が斜めになっている部分の長さ
h = a*a*b - x;
h /= a*a*0.5;
printf("%.10lf\n", to_deg(atan(h/a)));
}else{
double l;//水が斜めになっている部分の長さ
l = x / (a*b*0.5);
printf("%.10lf\n", to_deg(atan(b/l)));
}
return 0;
}
92
問題のポイント
ゲームにありそうな設定ですね
とはいえ，幅が5に限定されているので難しくないはずです
私は，ブロックを消す処理を全部べた書きで書いたのですが(6通りしかないので)，
幅が5列，消えるブロック数は最大3列なので，中央のブロックは必ず消えるという性質を生かしたらスマートに書けるかもしれません．
解答
#include <stdio.h>
int a[10][5];
int main(void){
int n;
int i, j;
while(1){
scanf("%d", &n);
if(n == 0){
break;
}
for(i = 0; i < n; i++){
scanf("%d%d%d%d%d", &a[i][0], &a[i][1], &a[i][2], &a[i][3], &a[i][4]);
}
int point = 0;
while(1){
int point_before = point;
for(i = 0; i < n; i++){
int u = a[i][0];
int v = a[i][1];
int w = a[i][2];
int x = a[i][3];
int y = a[i][4];
if(u != 0 && u == v && v == w && w == x && x == y){
point += u * 5;
a[i][0] = -1;
a[i][1] = -1;
a[i][2] = -1;
a[i][3] = -1;
a[i][4] = -1;
continue;
}else if(u != 0 && u == v && v == w && w == x){
point += u * 4;
a[i][0] = -1;
a[i][1] = -1;
a[i][2] = -1;
a[i][3] = -1;
}else if(v != 0 && v == w && w == x && x == y){
point += v * 4;
a[i][1] = -1;
a[i][2] = -1;
a[i][3] = -1;
a[i][4] = -1;
}else if(u != 0 && u == v && v == w){
point += w * 3;
a[i][0] = -1;
a[i][1] = -1;
a[i][2] = -1;
}else if(v != 0 && v == w && w == x){
point += w * 3;
a[i][1] = -1;
a[i][2] = -1;
a[i][3] = -1;
}else if(w != 0 && w == x && x == y){
point += w * 3;
a[i][2] = -1;
a[i][3] = -1;
a[i][4] = -1;
}
}
if(point == point_before){
printf("%d\n", point);
break;
}
//-1でないブロックを重力落下させる
for(i = 0; i < 5; i++){
int k = n-1;
for(j = n-1; j >= 0; j--){
if(a[j][i] == -1){
//-1だったら無視する
}else if(a[j][i] == 0){
//0だったら無視する
}else{
//それ以外は代入
a[k][i] = a[j][i];
k--;
}
}
while(k >= 0){//上の空白には0を入れる
a[k][i] = 0;
k--;
}
}
}
}
return 0;
}
93
問題のポイント
消える個数$k$を指定されると，少し難しくなりますね．
とはいえ，時間があれば解ける問題です，実際のコンテストでは，いかに早く解くかがポイントになりそうです．そのためにも，バグを作らない力，バグがあってもすぐに気づける力が必要でしょう．
解答
#include <stdio.h>
#include <math.h>
char str2num[] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};
int main(void){
int h, w, k;
scanf("%d%d%d", &h, &w, &k);
int i, j, m;
long long int point;
int c[30][30];
char tmp[31];
for(i = 0; i < h; i++){
scanf("%s", tmp);
for(j = 0; j < w; j++){
for(m = 0; m < 10; m++){
if(str2num[m] == tmp[j]){
c[i][j] = m;
break;
}
}
}
}
int c_tmp[30][30];
long long int ans = 0;
int ii, jj;
int tmp_list[30];
for(i = 0; i < h; i++){
for(j = 0; j < w; j++){
//c_tmpにコピー
for(ii = 0; ii < h; ii++){
for(jj = 0; jj < w; jj++){
c_tmp[ii][jj] = c[ii][jj];
}
}
long long int point = 0;
int cnt = 1;
c_tmp[i][j] = 0;
while(1){
//ブロックを重力落下させる処理
for(ii = 0; ii < w; ii++){
int kk = h-1;
for(jj = h-1; jj >= 0; jj--){
if(c_tmp[jj][ii] != 0){
c_tmp[kk][ii] = c_tmp[jj][ii];
kk--;
}
}
while(kk >= 0){
c_tmp[kk][ii] = 0;
kk--;
}
}
long long int point_tmp = 0;
//ブロックに水平に隣り合ったマスを消す
for(ii = 0; ii < h; ii++){
tmp_list[0] = 0;
for(jj = 1; jj < w; jj++){
if(c_tmp[ii][jj] == c_tmp[ii][jj-1]){
tmp_list[jj] = tmp_list[jj - 1] + 1;
}else{
tmp_list[jj] = 0;
}
}
for(int kk = 0; kk < w; kk++){
if(tmp_list[kk] >= k - 1){
for(int iii = 0; iii <= tmp_list[kk]; iii++){
point_tmp += c_tmp[ii][kk - iii];
c_tmp[ii][kk - iii] = 0;
}
}
}
}
if(point_tmp == 0){
break;
}
point += point_tmp * pow(2, cnt-1);
cnt++;
}
ans = ans > point ? ans : point;
}
}
printf("%lld\n", ans);
}
94
問題のポイント
問題文が間違えている気がします(カットする起点の記述のところ，✕北西→〇北東)
それと，意外にルールが複雑(というより誤解を招きやすい？)ので，それに気を付けて実装すれば解けます．
解答
#include <stdio.h>
#include <stdlib.h>
int max(int a, int b){return a > b ? a : b;}
int min(int a, int b){return a < b ? a : b;}
int compare_int(const void *a, const void *b){return *(int*)a - *(int*)b;}
int main(void){
//問題文間違えている？
//カットする起点の記述のところ ✕北西→〇北東
//もしくは入力例が間違っている
//北東である前提で解いていく
int n, w, d;
int p[100], s[100];
int i, j;
int cake_dw[101][2];//ケーキの奥行，幅の長さ
int sq[101];
while(1){
scanf("%d%d%d", &n, &w, &d);
if(n == 0 && w == 0 && d == 0){
break;
}
for(i = 0; i < n; i++){
scanf("%d%d", &p[i], &s[i]);
p[i]--;
}
cake_dw[0][0] = d;
cake_dw[0][1] = w;
for(i = 0; i < n; i++){//i：何回切ったか(0-origin), i+1:切った後のケーキの個数,
int d_i = cake_dw[p[i]][0];
int w_i = cake_dw[p[i]][1];
s[i] %= (w_i + d_i);
while(1){
if(s[i] < w_i){//北からor南から切る場合
for(j = p[i]; j < i; j++){
cake_dw[j][0] = cake_dw[j+1][0];
cake_dw[j][1] = cake_dw[j+1][1];
}
cake_dw[i][1] = min(s[i], w_i - s[i]);
cake_dw[i][0] = d_i;
cake_dw[i+1][1] = max(s[i], w_i - s[i]);
cake_dw[i+1][0] = d_i;
break;
}else{
s[i] -= w_i;
}
if(s[i] < d_i){//西からor東から切る場合
for(j = p[i]; j < i; j++){
cake_dw[j][0] = cake_dw[j+1][0];
cake_dw[j][1] = cake_dw[j+1][1];
}
cake_dw[i][0] = min(s[i], d_i - s[i]);
cake_dw[i][1] = w_i;
cake_dw[i+1][0] = max(s[i], d_i - s[i]);
cake_dw[i+1][1] = w_i;
break;
}else{
s[i] -= d_i;
}
}
}
for(i = 0; i < n + 1; i++){
sq[i] = cake_dw[i][0] * cake_dw[i][1];
}
qsort(sq, n+1, sizeof(int), compare_int);
for(i = 0; i < n+1; i++){
printf("%d", sq[i]);
if(i != n){
printf(" ");
}else{
printf("\n");
}
}
}
return 0;
}
95
問題のポイント
場合分けして考える
解答
#include <stdio.h>
int main(void){
long long int a, b, k;
scanf("%lld%lld%lld", &a, &b, &k);
if(a >= k){
printf("%lld %lld\n", a-k, b);
}else if(a + b >= k){
printf("%lld %lld\n", 0, b - (k - a));
}else{
printf("0 0\n");
}
return 0;
}
96
問題のポイント
いかつい問題に見えるものの，解法が分かれば短いコードで済んでしまいます．
modの和の最大値，なんて今まで考えたこともないのでとっつきにくい問題です．
解答
#include <stdio.h>
int main(void){
long long int n;
scanf("%lld", &n);
printf("%lld\n", n *(n - 1)/2);
return 0;
}
97
問題のポイント
最小公倍数を求める練習にもなりました．
解答
#include <stdio.h>
long long int gcd(long long int a, long long int b){return (a % b) ? gcd(b, a % b): b;}
long long int lcm(long long int a, long long int b){return a*b/gcd(a, b);}
int main(void){
long long int a[100000];
long long int n, m;
scanf("%lld%lld", &n, &m);
int i, j, k;
for(i = 0; i < n; i++){
scanf("%lld", &a[i]);
}
int cnt, cnt_t;
//2で割り切れる回数の計算
int t = a[0];
cnt = 0;
while(t % 2 == 0){
t /= 2;
cnt++;
}
for(i = 1; i < n; i++){
cnt_t = 0;
t = a[i];
while(t % 2 == 0){
t /= 2;
cnt_t++;
}
if(cnt != cnt_t){
printf("0\n");
return 0;
}
}
long long int tmp, x;
tmp = a[0]/2;
for(i = 1; i < n; i++){
tmp = lcm(tmp, a[i]/2);
}
x = tmp;
long long int ans = (m + x)/2/x;
printf("%lld\n", ans);
return 0;
}
98
問題のポイント
一瞬，最長増加部分列問題で解けるのかと思ったのですが，そうではなく，単純に掛け算による組み合わせ計算で解けます．
具体的に数字を当てはめて考えてなんとか解けました．
$N$の値が$10^5$という上限から，おそらく全列挙ではなく，逐次的に解ける問題であると推測できますね．
解答
#include <stdio.h>
int main(void){
int n;
int a[100000];
scanf("%d", &n);
int i, j, k;
for(i = 0; i < n; i++){
scanf("%d", &a[i]);
}
long long int ans = 1;
long long int mod = 1000000007;
int co[] = {0, 0, 0};
long long int cnt;
for(i = 0; i < n; i++){
cnt = 0;
for(j = 0; j < 3; j++){
if(co[j] == a[i]){
if(cnt == 0){
co[j]++;
}
cnt++;
}
}
ans *= cnt;
ans %= mod;
}
printf("%lld\n", ans);
return 0;
}
99
問題のポイント
数学的な問題です．なんかの大学入試とかに出てそうですよね．
プログラミング力はそれほど問われない問題です．
私は帰納法的に導出したので，なんでこうなるかは分からずにACを取れてしまったので，しっかり解説を読んで理解したいと思います．
解答
#include <stdio.h>
int main(void){
int m;
scanf("%d", &m);
long long int ans = 0;
long long int i, d, c;
long long int sum = 0;
for(i = 0; i < m; i++){
scanf("%lld%lld", &d, &c);
sum += c * d;
ans += c;
}
ans--;
ans += sum / 9;
if(sum % 9 == 0){
ans--;
}
printf("%lld\n", ans);
}
100
問題のポイント
これも具体的に数値を当てはめて帰納的に求めるのがいいでしょう．
解法によっては$N=1$のときの場合分けが必要になるので，お忘れなく．
解答
#include <stdio.h>
int a[1000][1000];
int main(void){
int n;
scanf("%d", &n);
if(n == 1){
printf("Yes\n");
printf("%d\n", 2);
printf("1 1\n");
printf("1 1\n");
return 0;
}
for(int i = 3; i < 1000; i++){
if(i*(i - 1) == 2*n){
printf("Yes\n");
printf("%d\n", i);
//a[][]の生成
int cnt = 1;
for(int ii = 0; ii < i - 1; ii++){
for(int jj = ii; jj < i - 1; jj++){
a[ii][jj] = cnt;
cnt++;
}
}
cnt = 2;
for(int ii = 0; ii < i - 1; ii++){
for(int jj = ii + 1; jj < i; jj++){
a[jj][ii] = cnt;
cnt++;
}
}
a[i-1][i-2] = 1;
for(int j = 0; j < i; j++){
printf("%d ", i - 1);
for(int k = 0; k < i - 1; k++){
printf("%d", a[j][k]);
if(k == i - 2){
printf("\n");
}else{
printf(" ");
}
}
}
return 0;
}
}
printf("No\n");
return 0;
}