実装リンク集 https://qiita.com/drken/items/6edb1c0542d4c3b7179c
問題一覧 https://abs.contest.atcoder.jp/assignments
大学でC言語しか勉強したことがないが競技プログラミングをやってみたい人はいると思います。しかし資料はC++が大半であり、C言語に対応した資料は少ないです。この解答集が最初の一歩の助けになれば幸いです。
この狙いのため、全解答とも、C/C++のいずれでもコンパイル可能となっています。
また、記事の終わりに、C++の【使い方】について説明しています(基礎ではありません、ここ大事。慣れるまではbetter Cでいいのです)。
余談：全解答C89準拠です(1行目を除く)。また、遊びですが、(6/7/9問目を除き)picocというインタプリタでも動作するようになっています。
解答
例題 PracticeA
scanfのフォーマット文字列中に空白を入れている例が散見されますが、まったく必要ではありません。また、空白と改行の差を無視して入力することができます。
ちなみに、//usr/bin/env picoc $0 - $@;exitはShebangのようなものです。cf: https://qiita.com/cielavenir/items/b83552a761419be57285
//usr/bin/env picoc $0 - $@;exit
#include <stdio.h>
int main(){
int a,b,c;
char s[999];
scanf("%d%d%d%s",&a,&b,&c,s);
printf("%d %s\n",a+b+c,s);
return 0;
}
第１問 ABC086A Product
//usr/bin/env picoc $0 - $@;exit
#include <stdio.h>
int main(){
int a,b;
scanf("%d%d",&a,&b);
puts(a*b%2 ? "Odd" : "Even");
return 0;
}
第２問 ABC081A Placing Marbles
C(++)では、boolを直接intとして扱うことができます。
//usr/bin/env picoc $0 - $@;exit
#include <stdio.h>
int main(){
char s[9];
int c=0,i=0;
scanf("%s",s);
for(;i<3;i++)c+=s[i]=='1';
printf("%d\n",c);
return 0;
}
第３問 ABC081B Shift only
arrの各要素に対し2で割ることが出来た回数の最小値です。
INF値として1<<29が使われていますが、2倍してオーバーフローしない中で簡潔に書ける数として競技プログラミングではよく使われます。
//usr/bin/env picoc $0 - $@;exit
#include <stdio.h>
int main(){
int n,x,r=1<<29;
for(scanf("%d",&n);n--;){
int r0=0;
scanf("%d",&x);
for(;x%2<1;x/=2)r0++;
if(r>r0)r=r0;
}
printf("%d\n",r);
return 0;
}
第４問 ABC087B Coins
500円玉と100円玉の枚数を全探索します。
//usr/bin/env picoc $0 - $@;exit
#include <stdio.h>
int main(){
int a,b,c,x,i,j,k,r=0;
scanf("%d%d%d%d",&a,&b,&c,&x);
for(i=0;i<=x/500;i++)for(j=0;j<=(x-500*i)/100;j++){
k=x-500*i-100*j;
r+=k%50==0&&c>=k/50&&a>=i&&b>=j;
}
printf("%d\n",r);
return 0;
}
第５問 ABC083B Some Sums
変数sは各i(j)を10で割れるだけ割って、その間に出た余りの和です。
//usr/bin/env picoc $0 - $@;exit
#include <stdio.h>
int main(){
int n,a,b,r=0,i,j;
scanf("%d%d%d",&n,&a,&b);
for(i=1;i<=n;i++){
int s=0;
j=i;
for(;j;j/=10)s+=j%10;
if(a<=s&&s<=b)r+=i;
}
printf("%d\n",r);
return 0;
}
第６問 ABC088B Card Game for Two
qsortを使うには関数ポインタを使います。説明は本記事では割愛します。余談ですがpicocではqsortは使えないようです。
#include <stdio.h>
#include <stdlib.h>
int compare(const void *a,const void *b){
return *(int*)b-*(int*)a;
}
int main(){
int n,i,r=0,t=1;
int arr[999];
scanf("%d",&n);
for(i=0;i<n;i++)scanf("%d",&arr[i]);
qsort(arr,n,4,compare);
for(i=0;i<n;i++){
r+=t*arr[i];
t=-t;
}
printf("%d\n",r);
return 0;
}
第７問 ABC085B Kagami Mochi
ソートしたら、直前の数値と同じかどうか見ていきます。(C++のuniqueと同様のアルゴリズム)
#include <stdio.h>
#include <stdlib.h>
int compare(const void *a,const void *b){
return *(int*)a-*(int*)b;
}
int main(){
int n,i,r=1,t;
int arr[999];
scanf("%d",&n);
for(i=0;i<n;i++)scanf("%d",arr+i);
qsort(arr,n,4,compare);
t=arr[0];
for(i=1;i<n;i++){
if(t!=arr[i]){
t=arr[i];
r++;
}
}
printf("%d\n",r);
return 0;
}
第８問 ABC085C Otoshidama
1000円札と5000円札の枚数を全探索します。
//usr/bin/env picoc $0 - $@;exit
#include <stdio.h>
int main(){
int n,y,i,j,k;
scanf("%d%d",&n,&y);
for(i=0;i<=n;i++)for(j=0;j<=n-i;j++){
k=n-i-j;
if(i*1000+j*5000+k*10000==y){
printf("%d %d %d\n",k,j,i);
return 0;
}
}
puts("-1 -1 -1");
return 0;
}
第９問 ABC049C Daydream
文字列を逆にして比較していきます。
char T[4][8]と書いていますが、char *T[4]は不可です。実行時に配置されるメモリ領域が書込可能な領域でないといけないからです。
#include <stdio.h>
#include <string.h>
void rev(char *s){
int l=strlen(s),i;
for(i=0;i<l/2;i++){
char t=s[i];
s[i]=s[l-1-i];
s[l-1-i]=t;
}
}
char T[4][8]={"dream","dreamer","erase","eraser"};
int main(){
int i=0,c,l;
char s[100001];
for(i=0;i<4;i++)rev(T[i]);
scanf("%s",s);
l=strlen(s);
rev(s);
for(;c<l;){
int k=-1;
for(i=0;i<4;i++){
if(!strncmp(s+c,T[i],strlen(T[i]))){
k=strlen(T[i]);
break;
}
}
if(k<0){
puts("NO");
return 0;
}
c+=k;
}
puts("YES");
return 0;
}
第10問 ABC086C Traveling
dx+dyがdt以下かつdtとの偶奇が一致。
//usr/bin/env picoc $0 - $@;exit
#include <stdio.h>
int main(){
int n,t=0,x=0,y=0;
for(scanf("%d",&n);n--;){
int t0,x0,y0;
scanf("%d%d%d",&t0,&x0,&y0);
{
int dt=t0-t,dx=x0-x,dy=y0-y;
if(dx+dy>dt || (dt-dx-dy)%2){
puts("No");
return 0;
}
}
t=t0;x=x0;y=y0;
}
puts("Yes");
return 0;
}
発展：第６問/第７問をC++で
C言語で問題を解いていると、どうしても回りくどくなってしまう部分があります。配列長を多めに取ったりとか。ソート用関数書くのめんどくさいとか。そういう場合に部分的にC++を使うと簡単に解決できる場合があります。
第６問
std::vector<int>arr(n)とすると、配列長nの配列が手に入ります。<>の中身が要素の型になります。
また、std::sort(arr.begin(),arr.end());とするだけでソートできます(ただし昇順なのでreverseもしている)。
#include <vector>
#include <algorithm> //sort,reverse
#include <stdio.h>
int main(){
int n,i,r=0,t=1;
scanf("%d",&n);
std::vector<int>arr(n); //int arr[999];
for(i=0;i<n;i++)scanf("%d",&arr[i]);
std::sort(arr.begin(),arr.end()); //qsort(arr,n,4,compare);
std::reverse(arr.begin(),arr.end());
for(i=0;i<n;i++){
r+=t*arr[i];
t=-t;
}
printf("%d\n",r);
return 0;
}
第７問
いちいちソートして隣同士を数えるのはくどい、重複を無視した集合を用意すれば解決できる。と思った方、正解です。
重複を無視した集合はsetと呼ばれています。
.insert(x)でxを集合に追加、.size()で集合の大きさを得ることができます。
#include <set>
#include <stdio.h>
int main(){
int n,i,x;//,r=1;
std::set<int>se; //int arr[999];
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%d",&x);
se.insert(x);
}
printf("%d\n",se.size());
/*
for(i=0;i<n;i++)scanf("%d",&arr[i]);
qsort(arr,n,4,compare);
int t=arr[0];
for(i=1;i<n;i++){
if(t!=arr[i]){
t=arr[i];
r++;
}
}
printf("%d\n",r);
*/
return 0;
}
終わりに
構造体はst.elemという形式でアクセスできますが、これに括弧が付くとなんらかの操作ができます。カプセル化やら継承やらが出てくるから混乱するのであって、慣れるまではこういうおまじないであると思っておけばいいのです。C++、better Cから始めてみませんか。