2019-07-12

ICPC2019に参加しました

こんにちは。Arkです。

本日、2019年7月12日にICPC2019アジア大会国内予選が開催されました。僕はこれに参加し、結果は170位/495と惨敗でしたがいい経験になりました。

Nキチさん（@freude111）、Badlyluckyさん（@Wklqtzsyei ）には大変お世話になりました。ありがとうございました。

ICPCに参加しようと思ったきっかけ

一応ICPCの参加の経緯でも書いてみます。そもそもプログラミングというか競プロを初めたのが今年の四月の頭でした。その時点ではコードなんて全く欠けないょゎょゎ競プロerでしたが、GWに大阪で競プロ合宿が開催されたCPSCO2019に参加してなんとか戦えるくらいになりました（ひのきのぼうを装備したくらいの戦闘力ですが...）。CPSCO2019の詳しくは僕のブログの

CPSCO2019に参加しました

（https://ark11111.hatenablog.com/entry/2019/05/08/110042?_ga=2.140286451.1172777208.1562855385-101319567.1554034372）

こちらをご覧ください(⌒∇⌒)

これがきっかけで阪大の競プロerと知り合い、彼らからSlackでICPCっていう大学対抗のプログラミング大会があるし初心者でも歓迎ですといわれ、ぽよぽよしているうちにICPCに参加することになりました( ´艸｀)

ここからは日々精進で、大学の授業なんて全く聞かずにAtCorderの過去問ばかり解いていました。ICPCまでにAtCorder緑にできたらいいな～～とかふわふわ思っていたらなんか緑になってました。

ICPC本番

まあ、そんなこんなでいろいろありつつ、ICPC国内予選本番を迎えました。大会開始前はみんな緊張をまぎらわすかのようにテンションが高くて面白かったです。始まってからは僕も含め周りは真剣そのもので、たまに他のチームから手を打ち合わせる音が聞こえたり、発狂が聞こえたりして（おもにじゅぴろーくん（@jupiro_jupi ））楽しそうでした。ちなみに冷えてた僕らチームは全然楽しくなかったです。

結果を振り返ると、チームでA,Bの二完でした。アジアのボーダーはだいたい四完だったのでアジアはまだ遠いな～～と感じさせられました。

ICPC後は阪大競プロerでオードブルを注文して軽い打ち上げをしました。取り決めをしてくださったBadlyluckyさん（@Wklqtzsyei ）と監督をしてくださった猿渡先生（@saru2007 ‏）にはとてもお世話になりました。ありがとうございました。

僕はまだ大学三年生なので来年＋二年（大学院に行くので）の三回もアジアに行くチャンスがあるのですが、僕のチームメンバーは今年で卒業してしまうのでとても悲しいです。まあでも来年は僕がアジアに行くのでひっそりと見ていてくださいという感じです。来年のICPCに向けて今日から僕は精進です。

日々、精進。

2019-06-25

素数生成: エラトステネスの篩

こんにちは。Arkです。
たまに素数の生成が必要な時があるので、備忘録のために素数の生成方法について書きたいと思います。

まず、最も自然な素数の生成法を書きます。（読み飛ばしてもらっても構いません）
最も小さい素数である2を素数の欄に入れます。次に2より大きい数字を順にみていき素数の欄に入っている数字で割ってみます。素数の欄に入っている数字で割ってみて、どれで割っても余りが1以上であればその数字は素数です。よってその数を素数の欄に入れます。これを繰り返すと素数が生成されます。
しかし、これは計算量が膨大になり実行時間が莫大にかかります。そこで、偉い人が考えたのが"エラトステネスの篩"です。

エラトステネスの篩

詳しくはソースコードを読んでもらった方が分かりやすいと思うので以下をご覧ください。

bool a[1000001];
int n=1000000;
vector<int> v;

void Eratosthenes(int N){
	for(int i=0;i<N;i++)
		a[i]=true;
	for(int i=2;i<sqrt(N);i++){
		if(a[i]){
			for(int j=0;i*(j+2)<N;j++)
				a[i*(j+2)]=false;
		}
	}
	for(int i=2;i<N;i++)
		if(a[i])
			v.push_back(i);
	//for(auto z:v)cout<<z<<" ";
}

int main(){
	Eratosthenes(n);
}

軽く説明します。
まず小さい数字を全て素数と仮定します。その後に小さい数字から見ていき、その数の倍数である数を全て消去します（素数の候補から外します）。
これを繰り返すことで素数を高速で求めることが出来ます。ちなみにこのソースコードでいうvが素数の集まりで、コメント文を実行してもらえればすべての素数が列挙されます。

今回はN=1000000で行いました。実行時間はだいたい0.15秒です。非常に高速ですね！！！

2019-06-09

約数全列挙　C++

競プロ競技プログラミング精進

お久しぶりです。Arkです。

最近はAtCorderの400点問題を主に解いており、その過程で必要になった知識を書いていこうと思います。今回の内容は約数全列挙です。

僕が解いた問題はこちら

https://atcoder.jp/contests/abc112/tasks/abc112_d

一応僕のソースコードも張っておきます。
https://atcoder.jp/contests/abc112/submissions/5828856

一目見て約数が必要だな～～～とわかる問題になっています。Mの制約が10^9と大きいので少し工夫が必要です。まぁ、少し考えてもいい解法が思い浮かばなかったのでネットで検索しました。

するとO(√M)解法がヒットしました。以下にソースコード張ります！

//nの約数を列挙
vector<long long> divisor(long long n)
{
	vector<long long> num;
	for(long long i=1;i*i<=n;++i){
		if(n%i==0){
			num.push_back(i);
			if(i*i!=n)
				num.push_back(n/i);
		}
	}
	return num;
}

これは何をしているかというと、例えばn=100としたとき、for文でiを1~10まで回します。
100をi (1~10)で割り切ることができるかを判定して（一つ目のif文の判定) 、割り切ることができたら n/iも約数であるのでこの二つを列挙します。しかし、i*i==nになってしまうと、今回の場合10を二回列挙してしまうことになるので例外処理 (二つ目のif文) をします。
約数列挙の部分が重複して記載することになりますが、例の挙げたn=100を列挙するソースコードは以下のようになります。

#include "bits/stdc++.h"
using namespace std;

//nの約数を列挙
vector<int> divisor(int n)
{
	vector<int> num;
	for(int i=1;i*i<=n;++i){
		if(n%i==0){
			num.push_back(i);
			if(i*i!=n)
				num.push_back(n/i);
		}
	}
	return num;
}

int main(){
	vector<int> v=divisor(100);
	for(int i=0;i<v.size();i++)cout<<v[i]<<",";
	return 0;
}

以上となります。求める約数の数によっては、intの部分をlong longなどに変更してお使いください。

次は素数の生成方法の記事を書きたいなと思っているのでもしよければ覗いてあげてください。僕がとても喜びます(^▽^)/

2019-05-18

幅優先探索法 :BFS

競プロ競技プログラミング精進

こんにちは。Arkです。

今日は初めてBFSに触れたので記事にしました。

今回解いた問題は

ABC088-D Grid Repainting

https://atcoder.jp/contests/abc088/tasks/abc088_d

です。幅優先探索というものの存在を知ってはいましたが、全く実装方法が分からなかったので蟻本(通称: プログラミングコンテストチャレンジブック)を参考にしながら書きました。ちなみに今日買いました。高かったです(´;ω;｀)

以下が僕のコードです。コメント盛りだくさんです。伝わってくれると嬉しいです。

https://atcoder.jp/contests/abc088/submissions/5437847

加えて、28行目のwhile文以下の説明を僕なりに考察しながら書きます。間違ってたらコメントをください！！

まず、p=que.front() で、queに入っている一番最初のものを参照します。次に、参照したものは que.pop() で捨てます。この操作がないと一度探索したことのある座標をもう一度参照することになってしまい、無限ループになってしまいます。

次に、指定した座標の前後左右 (next_x, next_y) を見ます。その時、最初に与えられている迷路をはみ出して探索することがないように、(1<=next_x<=W) かつ (1<=next_y<=H) の条件を付けます。また、この問題では ' . ' のマスのみ移動可能なのでこのあたりも条件に付けます。加えて、次に進む点が未訪か既訪かを示すフラグ (未訪ならINF) を見て、未訪なら更新し、次のループでその点を起点とできるようにque.push()します。そして、一マス動いたのでdistanceを+1します。

最後にdist[W][H]を出力するんですが、スタートからゴールまで行くことができれば最短距離が格納されていますし、ゴールできない場合は最初に入力したINFが入っています。

こんな感じで読み解きながら実装しました。結構自己満な記事ですが、自分が振り返ることができるし、説明するにあたって自分の穴をなくすことができるのでこれからも書いていきたいと思います。暇があれば、たまに目を通してくれると嬉しいです。

精進頑張ります！！！

2019-05-13

ワーシャルフロイド法

競プロ競技プログラミング精進

こんにちは。Arkです。

最近はC問題が解けるようになってきたので、D問題に挑戦してみようと適当にとってきた問題がこちらです。

AtCorder Beginner Contest 073 / D - joisino's travel

https://atcoder.jp/contests/abc073/tasks/abc073_d

まず一目見て、なんだこれっ！！ってなりました。図形問題でやったことあるのDFSだけだし、かといってDFSも自分で実装できないしな～～って感じだったので少し考えてすぐに解説を見ました。（天才が考えたことを僕は勉強するだけです...）

まず、解説の最初の文にワーシャルフロイド法という名前が出てくるも、初耳すぎて頭の中が　?(・ω・)?　という感じでした。そこで調べて自分で実装してみました。

https://atcoder.jp/contests/abc073/submissions/5387051

僕なりにまとめるとこんな感じ。(カッコ内は僕のコードにおける行番号を示す)

①頂点間の移動距離を0で初期化（16）

②自己連結の場合はそのまま0にし、他の頂点とつなげる場合はINF(=∞)にする（19）

③入力で得られた頂点間にパスがつながっている場合、そこのINFを上書きする（22）

④頂点i から頂点j に行く移動距離と、頂点i から頂点k を経由して頂点j に行く移動距離を比べ、小さい方を頂点i~頂点j の移動距離として上書きする(29)←この操作がワーシャルフロイド法におけるもっとも重要な部分！！！

⑤next_permutationを使うためにソートし、最短経路を出力する(34~41)

以上こんな感じです。最後のnext_permutationは数学のコンビネーション(nCr)のようなものです。これはまた記事にしたいなと思っています。にしてもD問題ってこんな方法を知らないと解けない問題とかが多そうなので、これからも精進あるのみだと感じました。

競プロを初めて今日で5週間がたちましたが、最初はB問題でさえ解けなかったのがよくここまで来たなという感じです。精進みを感じることが出来て僕は結構満足しています。しかし、上には上がいるので日々精進を忘れることなく頑張ります！！！！！

(2019/5/17追記)

AtCorder Beginner Contest 079-Dでも似たような問題があり、一発ACをすることが出来てうれしいので追記しておきます。

問題

https://atcoder.jp/contests/abc079/tasks/abc079_d

解答

https://atcoder.jp/contests/abc079/submissions/5425934

いや、自分天才では？？？

完

2019-05-10

ICPC国内予選2014-Chain Disappearance Puzzle

ICPC 競プロ競技プログラミング精進

どうも、Arkです。

この前のICPCミーティングで関数を使えるようになるといいと教わったので、おすすめされた問題を解いてみました。

ICPC国内予選2014-Chain Disappearance Puzzle

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1193

もう、僕レベルでは一苦労の問題でした。疲れました。実際五時間くらいかかりました。最後の最後で一つのコーナーケースに気づかず結局はツイッターに投稿し、教えて貰った上でのACでした。結構ぐちゃぐちゃしたコードですが、下に載せます。

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3557250#1

精魂尽き果てました。おわり。

ICPCの国内予選までにはこのレベルの問題までは普通に解けるようにすることが僕の目標です。日々精進あるのみ。

2019-05-09

<bits/stdc++.h>でC++の標準ライブラリを全部インクルードする方法

精進競プロ競技プログラミング

プログラミング初心者なのでインプットに励みたいと思いつつ、脱初心者をしたときに振り替える場が欲しいと思ったので毎日の精進をざっくりブログにしようと思います。

まぁ、ほぼほぼ自己満足なブログになると思うので暇なときに見てくれると嬉しいです！！

今日参加したICPCのミーティングで、Visual Studioでは<bits/stdc++.h>をインクルードできないため、使えるようにしましょうと言われたので自分で調べながら実装した流れを書こうと思います。いろいろなサイトを参考にしたのですが、僕の読解力不足によりよくわかりませんでした。しかし、以下のサイトをそのまま行うと成功しました。

---------------------

Visual Studio Community 2015で#include <bits/stdc++.h>を使う

http://blog.livedoor.jp/dgd17/archives/11663659.html

---------------------

（※一応C++用に書きましたが、Cの人は以下の④の操作でコピーする部分を00033~00061にすればいいだけだと思います。）

①まず、Visual Studioを起動し、競プロ用に使うプロジェクトを作成する。僕の場合はcontestというものを作成しました。

②ファイルから先ほど作成したプロジェクトがあるディレクトリに移動する。僕の場合はC:\Users\###(ユーザー名)\source\repos\contest\contestにありました。

③そのディレクトリに新しいファイルを作成し、名前をbitsにする。

④https://gcc.gnu.org/onlinedocs/gcc-4.6.2/libstdc++/api/a01040_source.html

このサイトに飛び、00064以下をコピーしてメモ帳に張り付ける。この時、＃ifdef,#endifは削除する。保存するときは.txtではなくすべてのファイルにする。

⑤コピーして作ったファイルの名前をstdc++.hにして、bitsフォルダの中に移動する。

⑥最後にcontestプロジェクトで.cppファイルを作成し,#include "bits/stdc++.h"を入力し完成！！！！！

f:id:Ark11111:20190509224239p:plain — include完了

いかがでしょうか。全く知識のない僕ができた方法ですので参考になれば幸いです(⌒∇⌒)