AtCoder青になりました。(C++)
いや〜青になれたら競プロの強い人って感じするなぁと思って精進していたらなれました。
嬉しい(小並感)
青になるまでにしたこと
水色までは割となんか気が付いたらなっていたみたいな感じだったのですが、青は努力してなった感がとてもあります。青になるためにかなり精進しました。
もちろん競プロ強くなりたいという漠然とした思いもあったのですが、計算研究会で先輩方と一緒にICPC予選に出るため少しは貢献できるようになりたいという思いがあり頑張れました。
(実際ICPC予選での僕の貢献はC問題について少しだけ考察を投げた程度で終了してしまいましたが……)
とりあえず、精進期間には苦手だったりしてやっていなかった300点・400点をほとんど解き、より高難易度の問題、具体的には500~800点に挑戦していきました。
青色に近づくきっかけは1000点問題をACできたことなんじゃないかと思っています。
やはり、今まで解けなかった難易度帯を1問でも解けると足枷が取れる気がします。
400点までしか解けなかった時代から脱出したのも500点問題を一度ACしたのがきっかけです。
そして、1000点問題を解いてからちょっと後にあったAGC036で900点問題をコンテスト中ACすることが出来て一気にレートが1458→1584に上昇しました。その後2回のABCでレートを停滞させ、3つ後のABC137にてパフォーマンス1924を出して見事青色となりました。
(ただし、E問題を嘘解法で通していたことが発覚して萎えています。)
参考:AtCoder Scoreの画像(二段階滴定かな？)
個人的に思う青になるまでに必要な知識や能力
累積和(1,2次元)
ある程度複雑な動的計画法
二分探索(高速でミス少なくかける)
bit全探索
map
priority_queue
pair
構造体
素因数分解
ユークリッドの互除法
約数列挙
文字列の基本操作
O(logN)での累乗の計算
階乗、コンビネーションの計算
DFS
BFS
Bellman-Ford法
Warshall-Floyd法
Dijkstra法
Union-Find木
数学力
ある程度高速かつミスの少ない実装力
これから身につけたいもの
set
グラフ構成系のアルゴリズム
(Kruskal法やPrim法)
かなり複雑でヤバヤバなdp
dpを高速で書ける力
スライド最小値
行列関係
才能
その他
ICPC 2019 Asia Yokohama Regional にチーム名
「unlimited nya-n」として出ます。
皆さんよろしくお願いします。是非エンカしましょう。
水色になった競技プログラマーの衝撃の発言に涙が止まらない…
Yahooのみんなのプロコンで水色になれました。
ということで、人は色が変わるとブログを書くものらしいので書いてみました。
水色までにした事
とりあえず過去のABCを埋めていきました。水色になるまでの間に簡単なABCのA問題を全て解き、B問題も7割程度解きました。
これが実際コンテストで役に立ったかというと若干疑問ですが、きっとスピードアップに寄与していることでしょう。
そして1番大きかったのは400~800点問題への挑戦です。なかなか重たい問題ばかりでしたが、じっくり1時間2時間程度かけて考えました。その結果400点問題は割と解けるようになっていきました。
次にCからC++にしました。
これはやはり、データ構造などを考慮するとC++の方が競プロに向いてるっぽいからです。
そして三重大学の計算研究会に入りました。
競プロをしている先輩方との交流が出来て、同じ大学内で競い合うこと、わからない所を相談することが出来るようになりました。
水色になるまでに必要だと思うもの
累積和(1次元)
簡単な動的計画法
二分探索
map
素因数分解
ユークリッドの互除法
文字列の基本操作
O(logN)での累乗の計算
階乗、コンビネーションの計算
2018年大学入学から年末にかけてまとめ
化学
前期試験後からマッカーリサイモン物理化学を読んで量子化学の基礎的な部分は学べた。
有機化学に関してはあまり出来なかったが高校時代にあやふやだった知識を少しは固めることができたと思う。
あと群論で頭の中が疑問符だらけになった。
数学
とりあえず大学の講義でやった線形代数や微分積分は一応理解出来てると思う。
常微分方程式、偏微分方程式は量子化学をやる上で必要だったのでやったがまだまだ学ばなくてはならない。
フーリエ解析は関数をsinとcosの級数に出来ることに感動を覚えた。あと、パーシヴァルの等式からいろんな無限級数が出てくるのも面白いと感じた。
ラプラス変換は最初何しとんねんと思ったが、二階の微分方程式が二次方程式になるのを見てラプラス変換に感謝した。逆ラプラス変換が思った以上にシンプルじゃなかった。
解析学や群論の本も読んだが抽象度が高くてつらみがあった。
三次方程式の解の公式が導出出来るようになった。
競技プログラミング(AtCoder)
前期試験後始めた。
割とC問題くらいまではすぐに解けるようになったがDで苦戦を強いられた。
途中4ヶ月くらい進捗0だったが、夏休み後半に復帰した。
最近は500~700点問題が解けるようになってきて楽しい。
来年は水色上位から青くらいになれるよう頑張ります。
絵
まあまあ上達したと信じたい。
↑2017年の絵(受験期だしそんなにない)
↓2018年の絵
AtCoder Beginner Contest A問題の解き方(C言語)
プログラミングって敷居高いよね！
ということで敷居を少しでも下げられるように稚拙ですが記事を書きました。(最後に紹介するもののまとめ、ミスしがちな場所まとめを追加しました。)
まず第一にAtCoderのアカウントを作成しましょう。
https://atcoder.jp/?lang=ja
ここでAtCoderで覚えておくとよい超基本用語を書いておきます。
AC、Acceptedの略で正解の意味
WA、WrongAnswerの略で不正解の意味
ABC、AtCoderBeginnerContestの略で基本的に初心者はこれを受ける。
A問題B問題C問題D問題があり難易度は基本A<B<C<D
ARC、AtCoderRegularContestの略で基本的に中級者はこれを受ける。
C問題D問題E問題F問題があり難易度は基本C<D<E<F
AGC、AtCoderGrandContestの略で基本的に中級者から上級者が受ける。
A問題B問題C問題D問題E問題F問題があり難易度は基本A<B<C<D<E<F
⚠️AGCはとても難しくA問題でもABCのC問題程度の難しさです。
パフォーマンス、受けたコンテストそれぞれにつきます。
多く、早く解くとパフォーマンスは上昇します。
レート、今まで受けたコンテストの結果(パフォーマンス)によって決められる値です。
400毎に色が変わり
灰→茶→緑→水色→青→黄→橙→赤
となっていきます。
そして競技プログラマーを色を用いて
灰コーダー茶コーダー緑コーダー……などと言います。(ただし赤だけレッドコーダーと言われたりします。)
ABCではレート1200が限界でそれ以上レートをABCの結果で上げられず
ARCではレート2800が限界でそれ以上レートをARCの結果で上げられません。
AGCは無制限です。
AtCoderの情報はここまでにして、ではさっそくHello Worldを出力するプログラムを書いてみましょう。
と言われてもプログラムってどこに書けばいいの？とかプログラミング環境の準備って難しいと思う人も多いと思うのでとりあえずオンラインでプログラムをかけるpaiza.ioを紹介します。https://paiza.io/en/projects/new?language=c
これで慣れてきたらVisualStudioなどをダウンロードしてプログラムを書くことをオススメします。
#include <stdio.h> int main(){ printf("Hello World"); }
#include
stdio.hっていう道具箱の中から道具を使いますよというような意味があります。(最初のうちはstdio.hのみで良い。studio.hと書かないように気をつけましょう。)
次にint main(){}ですがこれはmain関数と言われるものでC言語ではこの関数からスタートします。
A問題ではほかの関数を使う機会はあまりないため特に気にする必要はないかと思います。
このprintf(″″);の中に入っている文が出力されるので中身を違う文にすると当然違う文が出力されます。
AtCoderのA問題ではYESとかNOとかを答える時にこのprintf(″″);を用います。
そして基本的に文末にはセミコロン(;)を用います。
説明時には省くこともありますがプログラム例ではちゃんとセミコロンを書くのでそれを見て慣れていってください。
これだけではまだA問題は解けません。
次は変数についてです。
変数というのはよく箱に例えられるもので数値、文字や文字列を入れることが出来ます。
しかし、数値を入れておける変数と文字や文字列を入れておける変数は違うので使い方には気をつけないといけません。
ではプログラム例を載せます。
#include <stdio.h> int main(){ char str; char str2[256] = "Hello World"; int a; str='z'; a=57577; printf("%c\n",str); printf("%s\n",str2); printf("%d\n",a); }
出力
z
Hello World
57577
となります。
このプログラムをとりあえずひとつひとつ解説していきます。
まずchar str、これはchar型(文字や文字列を扱う型)の変数str(strは変数の名前で自分で勝手に決められる)を用意するという意味で、変数の宣言と言われるものです。
ただしこのstrにはたった1文字しか入れることは出来ません。
じゃあ文字列を入れるにはどうすればいいのかそれが次に紹介するものです。
char str2[256]、これはstr2[0]からstr[255]までの256個の変数を用意するという意味です。
すると、先程紹介した1文字しか入れられなかった変数を256個用意する訳ですから256文字まで入れられる……という訳では無いのです。
実は文字列には文字列の終わりを表す文字(ヌル文字)が必要でその文字を入れるために1つ使える変数が減ります。そのため255文字までしか入れることができません。
これはバグの温床なので気をつけましょう。
さらに言うとこの宣言の際[]の中に変数入れないようにしましょう。
また、これの横に=″Hello World″;とありますが、これは実際にstr2にHello Worldを代入するという意味があります。(これだけ後で代入するのがやや面倒臭いので先に代入しています。)
int a、これは整数を入れられる変数(int型)aを用意するという意味です。
str=′z′;、これは変数strにzを代入するという意味です。(1文字は基本的に″じゃなくて′を用いましょう)←先程のchar str2[256] = "Hello World";がchar str2[256] = "H";と1文字だったとしてみよう。
この時は1文字とは言え文字列なので″を用いることとなります。
a=57577;、これは変数aに57577を代入するという意味です。
これは整数を代入するため′や″は必要ありません。
printf("%c\n",str);、これは最初に説明しました。
しかし、中に先程とは違うものが入っているのでそれを説明します。
まず変数strにはzが代入されていますが、printf("str");
と入れると出力はstrとなってしまいます。
printf("str");はただただstrという文字を出力するだけで人間の気持ちを汲んでzを出力してはくれません。
そこでちゃんとzを出力するためにprintf("%c\n",str);を用います。イメージで言うと%cは1文字を入れられる欄を作ってくれて,の後のstrをその欄に入れると言った感じです。
最後に\nは改行を意味します。
AtCoder初期のA問題には出力の最後に改行を入れないと間違いと判定されるようになっている場合がありますので気をつけてください。
次の2行もほとんど同じなのですが、%dは整数(int型)%sは文字列の時に用いるものです。
似たようなプログラムを載せておきます。
#include <stdio.h> int main(){ char str[256]="Hello"; char str2[256] = "World"; printf("%s %s\n",str,str2); str[1]='a'; str2[1]='e'; str2[2]='e'; str2[3]='n'; str2[4]=' '; printf("%s%s",str,str2); }
出力
となります。
これはstrにHello、str2にWorldを代入し
後でstrの2文字目(str[1])str2の2,3,4,5文字目に違う文字を代入しています。(プログラムでは0から数字がスタートすることに注意しましょう)
次に演算です。
#include <stdio.h> int main(){ int a,b,c,d,e,f,g; a=33; b=4; c=a+b; d=a-b; e=a*b; f=a/b; g=a%b; printf("aの値は%dでbの値は%d。\nその和は%d\nその差は%d\nその積は%d\nその商は%d\na÷bのあまりは%d\n",a,b,c,d,e,f,g); }
出力
aの値は33でbの値は4。
その和は37
その差は29
その積は132
その商は8
a÷bのあまりは1
となります。
このプログラムではまず整数を入れられる変数a~gを用意しています。
そして今回はa=33、b=4として計算しています。
それぞれのc~gまでの演算は出力を見ていただけるとわかると思いますが、気をつけないといけない演算があります。
まず掛け算、これは×ではなく*を使います。
次に割り算、これは÷ではなく/を使います。また整数どうしの割り算では小数点以下が無視されます。
最後に余り、これは%で表現できます。
これ以外にも出来る演算はあり
例えば
#include <stdio.h> int main(){ int a; a=0; printf("%d\n",a); a++; printf("%d\n",a); ++a; printf("%d\n",a); a--; printf("%d\n",a); --a; printf("%d\n",a); a+=5; printf("%d\n",a); a=a+5; printf("%d\n",a); a-=5; printf("%d\n",a); a=a-3; printf("%d\n",a); a*=10; printf("%d\n",a); a=a*10; printf("%d\n",a); a/=2; printf("%d\n",a); a=a/2; printf("%d\n",a); a%=13; printf("%d\n",a); a=a%5; printf("%d\n",a); }
出力
0
1
2
1
0
5
10
5
2
20
200
100
50
11
1
となる。
このプログラムでは最初変数aの値は0で
a++によって+1されて1になる。
次に++aによって+1されて2になる。
次にa--によって-1されて1になる。
次に--aによって-1されて0になる。
次にa+=5によって+5されて5になる。
次にa=a+5によって+5されて10になる。
次にa-=5によって-5されて5になる。
次にa=a-3によって-3されて2になる。
次にa*=10によって×10されて20になる。
次にa=a×10によって×10されて200になる。
次にa/=2によって÷2されて100になる。
次にa=a/2によって÷2されて50になる。
次にa%=13によって÷13した時の余りの11になる。
最後にa=a%5によって÷5した時の余りの1になる。
そろそろA問題が解けるんじゃないか？と思うかもしれませんがまだ解けません。
なぜなら入力を受けとることが出来ないからです。
ということで次は入力の受け取り方を解説します。
プログラム例です。
#include <stdio.h> int main(){ int a; char str; char str2[256]; scanf("%d",&a); scanf(" %c",&str); scanf("%s",str2); printf("%d ",a); printf("%c ",str); printf("%s ",str2); }
入力
10 x AtCoder
出力
10 x AtCoder
となります。
このプログラムではscanfと言われるものが用いられています。
そしてscanfの内部の書き方はほとんどprintfと同じです。
しかし違うところもあります。
まず1つ目謎の&、これは文字列以外を読み込むときは入れてください。(逆に文字列の場合は入れないでください。)
この&は今のところは知らなくても大丈夫ですがアドレスというもののせいで入れなくてはいけません。
次2つ目%cの前の謎の空白、これは空白や改行は無視するという意味があります。
というのも文字を読み込む際空白も読み込んでしまい望み通りの入力処理ができない場合があるからです。
これはとてもバグの温床になるので気をつけましょう。
ここまで来たら解けるA問題が出てきます。
例えばhttps://beta.atcoder.jp/contests/abc012/tasks/abc012_1です。
下に答えは載せますが一度見ずに書いてみましょう。
提出もしてみてACが出たらOKです。
これの解答例は
#include<stdio.h> int main() { int A,B; scanf("%d%d",&A,&B); printf("%d %d\n",B,A); }
解説
この問題では入力された整数の順をひっくり返して出力すればよいです。
そのためscanfによってAとBの入力を受け取り、printfによってB→Aの順で出力します。
今回上手くいかなかった場合チェックすべきこと
- 綴りはあっているか
- scanfで&を忘れていないか
- 最後に改行をちゃんと入れているか
- printfの順は合っているか
- セミコロン(;)を忘れていないか
次に解説するのはif文です。これが使えると多くのA問題を解くことが出来ます。
ではプログラム例です。
#include <stdio.h> int main(){ int a; scanf("%d",&a); if(a==30) { printf("=30"); }else if(a<30) { printf("<30"); }else { printf(">30"); } }
入力→出力
30→=30
20→<30
40→>30
このプログラムでは条件分岐if(){}を用いています。
()の中に条件を書き、それがtrue(正しい)であれば
{}の中の操作に移り、false(正しくない)であれば{}
の中は無視され次に移ります。
また複数の分岐の場合else if(){}を用いて繋げていきます。
elseではそれまでの条件を満たさなかった場合{}内の操作に進むという意味です。
では()の中に入れる主なものを説明していきます。
- a>bまたはb<a、aがbより大きい(a=bは含まない)
- a>=bまたはb<=a、aがb以上(a=bも含む)
- a==b、aとbが等しい(a=bはaにbを代入という意味なので間違わないように気をつけましょう。)
- a!=b、aとbが等しくない
- &&、二つの条件式を繋いでかつという意味を表す。例：if(a>=5&&a<=10){printf(″YES″);}aが5以上かつ10以下の時YESと出力
- | |、二つの条件式を繋いでまたはという意味を表す。例：if(a<=5||a>=10){printf(″NO″);}aが5以下または10以下の時にNOと出力
先程のプログラム例で言うと変数aの値が30だったらif文の中の{}に進みそれ以降のelse ifやelseは無視されます。
次にaの値が30より小さい値だったらif文の条件は満たさないのでifの{}内は無視されてelse ifに進みます。
else ifの条件はこの場合満たしているのでelse if文の中の{}に進みそれ以降のelseは無視されます。
最後にaの値が30より大きい値だったらif文の条件は満たさないのでifの{}内は無視されてelse ifに進みます。
更にelse if文の条件も満たしていないのでelse ifの{}内も無視されます。
そしてifとelse ifの条件を満たさなかったため最後のelseの{}内に進みます。
では、もう1つプログラム例を挙げることにします。今度は文字の比較です。
#include <stdio.h> #include <string.h> int main(){ char str[11],str2[11]; scanf("%s%s",str,str2); if(str[strlen(str)-1]==str2[0]) { printf("しりとり成立"); }else { printf("しりとり不成立"); } }
入力→出力
apple enter→しりとり成立
atcoder banana →しりとり不成立
このプログラムでは2つの文字列についてしりとりが成立しているかを判定できます。
ここで新しく登場したのが
string.hとstrlen()です。
ではまずstring.hについて、これはstrlen()を用いるために必要な工具箱のようなものです。(他にもstring.hをインクルード(用意)することで出来ることはありますがまずはstrlen()だけ覚えておけばよいです。)
次にstrlen()について、これはその文字列の長さ(何文字か)を取得する関数です。
今回の場合しりとりなので、当然1つめの文字列の最後の文字の情報が必要です。
プログラムで表現するとstr[文字列の長さ-1]の情報が必要なので文字列の長さを求めるstrlen()が必要となってくるわけです。(文字列の長さ-1の-1がなぜあるかと言うとプログラムの数字は0から数え始めるからです。具体的にappleの場合を言うとstr[0]にa、str[1]にp、str[2]にp、str[3]にl、str[4]にeが入れられます。この時最後の文字を取り出そうとするとappleという文字列の長さ5を用いてstr[5-1]と書けます。)
ここまでくるとかなりのA問題が解けると思います。
ではまずABC020 A問題
https://beta.atcoder.jp/contests/abc020/tasks/abc020_a
を解いてみましょう。
#include<stdio.h> #include<string.h> int main() { int n; scanf("%d",&n); if (n==1) { printf("ABC\n"); } if (n == 2) { printf("chokudai\n"); } }
解説
解説はつけるまでもないと思いますが、とりあえず入力をscanf()で受け取ってそれが1ならABC、2ならchokudaiを出力します。
この問題はA問題の中でもかなり簡単な問題だと思うのでこの問題はパパッと解けるようになって欲しいです。
もしWA(不正解)が出たら最後の改行を忘れている可能性があります。
次はABC028のA問題
https://beta.atcoder.jp/contests/abc028/tasks/abc028_a
を解いてみましょう。
#include<stdio.h> #include<string.h> int main() { int n; scanf("%d",&n); if (n <= 59) { printf("Bad\n"); } else if (n <= 89) { printf("Good\n"); } else if (n <= 99) { printf("Great\n"); } else { printf("Perfect\n"); } }
解説
テストは0点から100点までであって、その点数をscanfによって取得します。
その後if文によって59点以下かどうか判定し60点以上ならば次のelse ifに進みます。
else if文によって89点以下かどうか判定し90点以上ならば次のelse ifに進みます。
else if文によって99点以下かどうか判定し100点ならelseに進みます。
このような仕組みから60点以上、90点以上という条件をelse if文の中にわざわざ入れなくても良いことがわかります。(入れても大丈夫です。)
ではこの問題の誤答も載せておきます。
int main() { int n; scanf("%d",&n); if (n <= 59) { printf("Bad\n"); } if (n <= 89) { printf("Good\n"); } if (n <= 99) { printf("Great\n"); } if (n ==100) { printf("Perfect\n"); } }
この誤答ではelse ifを用いずifのみで解こうとしています。
しかし、このプログラムではテストの点数が50点の場合出力が
Bad
Good
Great
と3つ出てしまいます。
このミスはif文がその前のif文の影響を受けないなため起こります。
つまり先程の正しいプログラムではif文の条件がfalse(間違い)の時だけ次のelse ifに進んでいましたがこの誤ったプログラムではif文の条件がfalseでもtrue(正しい)でも次のif文に進んでしまうということが原因です。
if文のみで正解するには2つめのif文に60以上という条件、3つめのif文に90以上という条件をつけるか、最後以外のif文の{}内の最後にreturn 0;(値を返すという操作で関数をそこで終わらせることが出来ます。main以外の関数を使わない場合値を返すこと自体の意味は気にしなくても良い)を付ける必要があります。
3問目はABC038のA問題
https://beta.atcoder.jp/contests/abc038/tasks/abc038_a
#include <stdio.h> #include <string.h> int main(){ char str[120]; scanf("%s",str); if(str[strlen(str)-1]=='T') { printf("YES"); }else{ printf("NO"); } }
解説
まず文字列を取得します。
そして、しりとりの例でやったように最後の文字
str[strlen(str)-1]を見てそれがTと等しい時YESと出力し等しくない時NOを出力します。
ここまでの解説でほとんどのA問題は解くことが出来ると思います。
では、最終問題としてちょっと頭をひねらないと解けないA問題を載せておきます。
https://atcoder.jp/contests/abc025/tasks/abc025_a
#include<stdio.h> int main() { int n; char str[30]; scanf("%s%d",str,&n); n--; printf("%c%c\n",str[n/5],str[n%5]); }
解説
Sがabcdeだった場合
str[0]がa、str[1]がb、str[2]がc、str[3]がd、str[4]がeとなり
25個の文字列を辞書順に並べると
aa, ab, ac, ad, ae,
ba, bb, bc, bd, be,
ca, cb, cc, cd, ce,
da, db, dc, dd, de,
ea, eb, ec, ed, ee
となります。
ここで気がついてほしいのが1つめの文字が5個飛ばしで変わっているということです。
するとまた、2つめの文字が5で割ったあまりで表現出来ることが分かります。
これをプログラムで行うそれが
printf("%c%c\n",str[n/5],str[n%5]);なわけです。
しかし8番目で実験してみると答えはbcなのですが
str[8/5]=str[1]つまりb(整数の割り算では小数切り捨て)str[8%5]=str[3]つまりdとなりbdとなってしまいます。
これを直すのがprintfの前のn--;というわけです。
nが1小さくなるとズレが解消するのが分かると思います。(このズレは日常生活では1から数えるのに対しプログラムでは0から数えるため生じます。最初のうちは慣れないと思いますが、0から数えた方が便利なこともありいつかは自然と慣れるはずです。)
具体的にはstr[7%5]=str[2]となりcが出てきてくれます。
これでAtCoderBeginnerContest A問題の解き方解説を終わります。
オマケ
全てのおさらい(変数名は適当にa,b,cとします)
#include<>
最初に書く。道具箱の準備のようなもので、基本的には
int main(){}
main関数、プログラムはこの関数からはじまり基本的にこの{}内にプログラムを記述する。
printf(″″);
中に文字を入れて出力できる。
変数を出力する時はprintf(″%d%c%s″,a,b,c);のように書く。この場合aは整数(%d)、bは文字(%c)、cは文字列(%s)″″の中に\nを入れると改行できる。
int a;
int型(整数を入れる変数)の宣言
char a;
char型(1文字を入れる変数)の宣言
char a
char型(文字列を入れる配列)の宣言の中に必要な文字数+1以上を入れる(NULL文字に注意)n文字目はa[n-1]にしまわれる。
scanf();
入力を読み取ります。
scanf (″%d %c%s″,&a,&b,c);
aは整数、bは文字、cは文字列
空白や改行を読み込まないように%cの前は空白を入れましょう。
また文字列のみ&はいれない。
aにbを代入a=b
足し算a+b
引き算a-b
掛け算a*b
割り算a/b(少数以下切り捨て)
あまりa/b
↑
c=a演算子bのように代入と合わせて使いましょう
1足すa++や++a
1引くa--や--a
b足すa+=b
b引くa-=b
bかけるa*=b
bで割るa/=b
bで割ったあまりa%=b
↑
基本的に代入と合わせて使わない。
a++ならa=a+1
a+=bならa=a+bという意味が既にあるため。
if(){}
条件分岐できる。()内に条件{}内に条件満たした時に行う動作を入れる。
多数の分岐の場合else if(){}と繋げる。
if文にelse if文を繋げた場合どれか条件を満たした時点でそれ以降のelse if文は無視される。
else{}を繋げた場合、それまでのif文else if文の条件が満たされなかった時のみ{}内に進む。
条件
- a>bまたはb<a、aがbより大きい(a=bは含まない)
- a>=bまたはb<=a、aがb以上(a=bも含む)
- a==b、aとbが等しい(a=bはaにbを代入という意味なので間違わないように気をつけましょう。)
- a!=b、aとbが等しくない
- &&、二つの条件式を繋いでかつという意味を表す。例：if(a>=5&&a<=10){printf(″YES″);}aが5以上かつ10以下の時YESと出力
- | |、二つの条件式を繋いでまたはという意味を表す。例：if(a<=5||a>=10){printf(″NO″);}aが5以下または10以下の時にNOと出力
strlen(a)
#include
これによって文字列aの長さが分かる。
ACが出なかった時に確かめるべきこと
- 問題を読み間違ってないか
- 綴りはあっているか
- scanfで&を忘れていないか
- printfで&を入れてないか
- 最後に改行をちゃんと入れているか
- セミコロン(;)を忘れていないか
- 空白や改行を読み込んでないか(%cの前に空白を開けると解消します。)
- if文の()の中に等号成立のつもりで代入の=を使ってないか
- 括弧はちゃんと閉じているか
- char str[100];などの時1から数えてないか
- NULL文字のことを忘れてないか(100文字入れる時にchar str[100]にしていないか)
Union-Find木使ってみた。 ARC097-D(C言語)
厳密な話は色々なサイトに書いてあるので
ゆるーい雰囲気で書きます。
まずUnion-Find木ってどこで使えるの？
AtCoderの問題だと↓がそうです。(最後に解答を載せておきます。)
D: Equals - AtCoder Regular Contest 097 | AtCoder
とにかくグループ分けしたい時に使えます。
Union-Find木の作り方
・配列を用意
全体の要素数をこえる大きさの配列を用意しましょう。
・木の根を求める(グループがどこか求める)関数を用意
再帰(ある関数の中でもう一度その関数を呼び出す)を用いて木をさかのぼって行きます。
木が伸びていくと再帰に時間がかかってしまうので再帰の時に木が短くなる時に形を変形しておきましょう。(最後にのせたコードの16行目にこの変形が書かれています。)
1→2→3→4→5(5から1にいくまで4回かかる)
1→(2,3,4,5)(5から1に1回で行ける)
・2つの要素が同じグループか判定する関数を用意
先程の関数を2つの要素について呼び出して比較します。
・グループをくっつける関数を用意
これも先程の関数を2つの要素について呼び出して等しかったら何もせず、等しくなければ片方のグループ番号をもう片方に写します。
ではARC097-Dの解答例です。
#include<stdio.h> #include<stdbool.h> //union find木(グループわけができる) int par[100005]; int unifind(int n) { for (int i = 1; i <= n; i++) { par[i] = i; } } //木の根を求める int unifind_root(int x) { if (par[x] == x) { return x; } else { return par[x] = unifind_root(par[x]); } } //同じグループか判定 bool unifind_same(int x, int y) { return unifind_root(x) == unifind_root(y); } //グループ併合 int unifind_unite(int x, int y) { x = unifind_root(x); y = unifind_root(y); if (x == y) { return 0; } par[x] = y; } int main() { int p[100005] = {}; int q[100005] = {}; int result = 0; int xy[100005][2] = {}; int m; int n; scanf("%d%d", &n,&m); unifind(n); for (int i = 1; i <= n; i++) { scanf("%d", &p[i]); q[p[i]] = i; //qはその値が左から何番目にあるかを示す配列 } for (int i = 1; i <= m; i++) { scanf("%d%d", &xy[i][0], &xy[i][1]); unifind_unite(xy[i][0] , xy[i][1]); } for (int i = 1; i <= n; i++) { //左からi番目の数が所属するグループと数字iが所属するグループが等しければ良い if (unifind_same(i, q[i])) { result++; } } printf("%d", result); }
AtCoder 緑になりました。(C言語)
とりあえず色が変わるとブログを書くみたいなので書いてみることにしました。
使用している言語はCです。
内容は
AtCoderを何故始めたか
AtCoder緑になるまで
を書こうと思います。
AtCoderを何故始めたか
(1)C言語を使うようになったきっかけ
元々プログラミングに興味はそこまで無く
高校1年の授業でやったHTMLやJavaScriptくらいしか知りませんでした。しかし高二のある時ゲーム作りたいなぁという思いが生まれてとりあえず聞いたことのあるJavaScriptの本を買ってみました。結局ポインタ辺りでよくわからなくなって投げてしまいましたけど、少しのきっかけにはなっていたのかもしれません。その後友達が苦しんで覚えるC言語を読み始めて僕自身もCに興味をもつようになりました。(他に後輩につられてUnityのC#をちょっとやってたりもしました。)
(2)AtCoderを知るきっかけ
(ⅰ)科学の甲子園
高2の時科学の甲子園とかいう科学の大会に三重県代表の一人として参加しました。ここで多くの科学系ついったらーとFF内になりました。
この人たちがのちのちAtCoderを始めたり勧めてきたりします。
(ⅱ)化学グランプリ本選
高3の夏に化学グランプリというイベントに参加しました。ここの人達も科学の甲子園同様後でAtCoder始めたりしてます。
(ⅲ)灘高校文化祭オフ会
灘高校の文化祭に科学の甲子園等で知り合った方々と行きました。その帰りにAtCoderやってる人から基礎的な競プロの話を聞くことが出来てちょっと興味が湧きました。
(ⅳ)謎の構文
Twitterを見ていると時々「はいプロ、○○界のtourist」とかが流れてきて元ネタはなんだろうと調べたところ競プロだったというのがありました。
(3)AtCoderをやるきっかけ
(ⅰ)受験の終わり
受験が終わり終わりました。
終わりましたが自由の身なので何かやろうと思い競プロをしようと思いました。
(ⅱ)日本語で出来る
英語全然読めないので競プロやるならAtCoderかなというお気持ちになりました。
(ⅲ)周りのついったらーが元からやってたり大学決まってからやり始めた
これがきっかけとしてかなり大きい。科学の甲子園とか化学グランプリで知り合った方々が一気にやり始めまたため「俺もちょっとやってみるか」となりました。
緑になるまで
まずAtCoderのアカウントを作りました。
この時2018年3月4日(土曜)だったと思います。
既にABCが終わっていて来週頑張ろうとか思ってました。
次に過去問です。
今までのABCのA問題B問題あたりを解いていきました。基本的なC言語の知識は苦しんで覚えるC言語を読んだため多少あり、A,Bは比較的容易く解けるようになりました。しかしC問題から急によくわからなくなったのを覚えています。ただ、C問題もある程度問題に触れてたら自然と解けるようになりました。C問題もある程度解けるようになったので次はD問題だと思い見たら次元が違うと感じました。B→Cに比べてC→Dの難易度の差はとても大きく何をしていいか全くと言ってよいほど分かりませんでした。解けたと思っても一部のケースがTLEしたりしてAC出来たD問題は1問でした。
初めてのABCで大勝利
初めて参加したABCでまさかの全完を達成してしまいました。
これ自体は喜ぶべきことなのですが、次のABC91ではA,B、ABC92はレジったものの参加出来ず、AGC23は0完でした。これで萎えました。それで4ヶ月AtCoderを放置しました。
復帰！大学の夏休み！
大学の夏休みは長くてやることがなくなってきます。そのためもう1回AtCoderやってみるかと思いABC109に参加しました。一応A,B,Cは解けてちょっとレートが上がりました。
茶コーダーになった
AGC27でA問題を解いたらレートが100くらい上がり茶色コーダーになれました。
そろそろ勉強
何となくで茶色コーダーになりましたがこれ以降はアルゴリズムとかやらないといけないなと思い累積和や尺取り法とかを学びました。当然DPも勉強しましたがよく分からなかったです。
嘘解法
ABC110のC問題を嘘解法で通してしまった。しかし問題の不備でunratedになったので許してって感じでした。(後でこのABCのD問題もAC出来た。)
悲劇はもう一度
ABC111はC問題まで解けました。この時点で個人的にはC問題までは余裕だと思い込んでいました。しかしABC112のC問題で大量のWAを出し結局AC出来ませんでした。ただ今回は前と違ってAtCoderやめようとはなりませんでした。
AGCはA問題
AGC28では何とか2回のWAを出したもののA問題(300点)をAC出来ました。嬉しかったですしパフォーマンスも1000をこえました。
Tenka 1 Programmer Beginner Contest
この大会で400点問題(C問題)まで解いたところパフォーマンス1600を達成し一気にレートが173上がり緑色になれました！やった！
とりとめのないようなことしか書けませんでしたがとりあえず私のAtCoderらいふはこんな感じです。プログラミングやアルゴリズムのこととかほとんど書いてないけど……。
にゃーん(おわり)
