サークルのOBであるdyumaさんがGWにサークル内でのISUCONを企画してくれた。 運営は、dyumaさんとbgpatさんにやって頂いた、ありがとうございます！ 最近は、数学しかやっていなくて1ヶ月位コードを書いていなかったのでリハビリという目的と、世間は"Go"lde…

解説 まず、ある数字が持つ最小の素因数を持つ配列を作成します。 つまり、となっています。 このような配列は、最初に昇順に数字を入れておいた配列に対して、インデックスと、その要素が等しいところからエラトステネスの篩の要領でループを回すことで作成…

はじめに ICPCなどの大会ではファイルを提出する必要があります。 この記事は、とりあえずファイルの入出力をやりたい人に対して書かれています。 なので、細かい説明はしません。 mac/linux の場合 一行で出来てしまいます。 $ ./a.out < input.txt > outpu…

基本 以上以下の整数の和は、で求められる。 本題 上の公式で求めた後に、累積和の要領で差を取れば良いです、小さいほうの区間の右端が開いていることに注意します。 , とすると、 のように差を取れば良く、となります(再三ですが、Aの右端が開いている事に…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2826&lang=jp 問題 種類のモンスターが昇順に与えられる。 主人公はレベル1からスタートし、自分のレベル+未満の敵を倒すことが出来る。 敵を倒すとだけレベルが上昇する。 このゲームでは、番目…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2748&lang=jp 問題 各頂点が確率を重みとして持つような頂点からなる有向グラフが与えられる。 また、各頂点は確率で状態Aとなる。状態Aとなった頂点は、隣接する頂点の状態をAに変えることが出来…

次のサイトを参考にさせていただきました。 一応自分で使いやすい感じにカスタマイズさせていただきました。 強連結成分分解(Strongly-Connected-Components) | Luzhiled’s memo 解説 トポロジカルソートの要領で各頂点からdfsして、帰りがけに頂点を追加し…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1196&lang=ja 問題 頂点辺からなるグラフ(つまり木)が与えられる。 最初、好きな島に居るとして繰り返し以下のいずれかの操作が可能。 今いる頂点の隣の頂点に移動する。 今いる頂点に生えている…

Educational Codeforces Round 96 (Rated for Div. 2) https://codeforces.com/contest/1430/problem/D 問題 0と1で構成された文字列が与えられる。 に対して2stepからなる操作を何回か適用することを考える。 ]を選んで削除する。ただしである。 が0で無い…

Codeforces Round #656 (Div. 3) https://codeforces.com/contest/1385/problem/E 問題 頂点辺のグラフが与えられる。 ここで、与えられる辺は、有向辺または無向辺のどちらかである。 無向辺に向きを付けることで、DAGを構成できるかどうか判定せよ。 判定…

Codeforces Round #656 (Div. 3) https://codeforces.com/contest/1385/problem/D 問題 長さの文字列が与えられるので、番目の文字を任意の文字に置き換える操作を何度か行うことでa-goodな文字列にできる最小の操作回数を求める。 ここで、c-goodであるとは…

Codeforces Round #661 (Div. 3) https://codeforces.com/contest/1399/problem/E1 問題 頂点1を根とする頂点からなる木が与えられる。 また、各辺には重みが付けられている。 操作を1度行うたび、任意の重みをに更新することが出来る。 根から葉へのパスの…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2885&lang=jp 問題 色A, B, C で与えられたグラフを次の条件を満たすように彩色する問題を考える。 AとBで彩色された頂点は、辺で直接繋がっていない。 同じ色で彩色された頂点は、辺で直接繋がっ…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2825 問題 参加者人、問題数問のクイズ大会を考える。また、問目の問題の得点はである。 このクイズ大会では、問目に正解する可能性がある参加者が人おり、それぞれであることがわかっている。 こ…