Programming Contest

こんにちはtatsyです。 今回は先日行われたKUPCをチラ裏的に解説したいと思います。僕はAからFまでしかできてないので、できているとこまでです。 たぶん、そのうち公式の解説がでるので、完全に自己満です。許してください。 A. 東京都 問題 アルファベットの小文字だけから成る文章が与えられるので、それを適当に切り分けて、tokyoあるいはkyotoが入っている断片を作る。作れる断片の最大数はいくつかを答えよ。 ...

こんにちは、お久しぶりのtatsyです。 本日はGCJ 2015のRound2に参加しました。 去年から1年、今日という日に賭けてきたにもかかわらず、今年は1217位という悲しい結果に終わってしまいました。 CのEasyが微妙に計算時間を短縮できなかったのが敗因です。そこらへんも含めて、 A Small / Large B Small C small を解説していきたいと思います。 A. Pegman (Small 5pt, Large 10pt) 問題 R×Cの大きさのグリッドが与えられている。グリッドの各セル ...

こんにちはtatsyです。本日はTCO2015ラウンド1Aの解説です。 Easy (250点) 問題 ある2つの数A,Bが与えられた時、この二つの数の類似度sim(A,B)は0から9の数字の中で、2つの数両方に含まれる数の個数を表す。AとBが取りうる値の下限Lと上限Rが与えられたとき、互いにことなるAとBでsim(A,B)の最大値はいくつか？ 解法 単純に考えるとLとRの間の全ての数のペアについてsimがいくつにな ...

こんにちはtatsyです。本日もSRMの解説いきます。 Easy (250点) 問題 太郎はAとBからなる長さNの文字列を作ろうとしている。この文字列を作るときにposition[i]にはvalue[i]が来ることが分かっている。このとき、余っている部分にAとBを埋めて、2文字AあるいはBが続いている箇所数が最小になるようにしたい。この最小の文字列は何種類作れるか？1,000,000,007で割った余りを求めよ ...

こんにちはtatsyです。本日もSRMの解説いきます。 Easy (250点) 問題 ある長さNの文字列が与えられる。このSnukeさんはこの文字列のうちK個を取り除いてあなたに見せる。この際、あなたはSnukeさんが何番目の文字を消したのかを言い当てたい。確実に言い当てられる場合には”Certain”を、そうでない場合には”Uncertain”と答えよ。 解法 確実に言い当てられない場合というのは、結果が同じにな ...

こんにちはtatsyです。本日もSRMの解説いきます。 Easy (250点) 問題 長さがNでAとBの2種類の文字からなる文字列Sがあるとする。このときある2つのインデックスi, j (i < j)に注目した時、S[i] = A, S[j] = Bとなるような組がK個あるような文字列をどれでも良いので出力せよ。ただし、そのような文字列がない場合には空の文字列を返せ。 解法 この問題の条件を言い換えると、文字列に含まれる各Aについてその右側に ...

こんにちはtatsyです。本日もSRMの解説いきます。 Easy (250点) 問題 整数からなる数列が与えられる。この数列から適当にk個を選んで、好きなように並べ替えることができる。このとき各々の数を変化させて、数が1ずつ上がる、あるいは1ずつ下がるようにしたい。変化させるべき数の絶対値の合計の最小値はいくつか？ 解法 この問題は個人的に少し英語が分かりづらかったなぁと思います。 要するに好きに数をk個選んで並び替 ...

こんにちはtatsyです。いつものようにSRMの解説をします。 Easy (250点) 問題 数字N(最大10^18)が与えられるので、これを素因数分解し、その素因数を小さい順に重複を含めて配列として返したい。このときヒントとして、答えの配列の偶数版目の要素(配列番号は0から始まる)が与えられる。 解法 まず、いつも通り単純に考えると、普通にエラトステネスのふるいみたいなことをして、素因数を列挙することが出来そうで ...

今回もSRM 642の解説行きます。今回からソースコードのヘッダ部分は切ります(一応マクロは残します)。 今回の問題は Easy: メモ化 / 確率 Medium: 最小費用流 となっております。 Easy (250点) 問題 ある町にはバスがN本あり、それぞれのバスは駅を出発してtime[i]分で駅に戻ってくる。一度に運行できるバスは1本だけであるため、ひとたびバスが出発するとtime[i]分はバスがでない。出発するバスはそれぞれprob[i] % ...

SRM641の解説です。 Easy (250点) 問題 2次元座標上に最大2500個の点が与えられる。これらの点のいずれの3点も同一直線状にないことが保証されており、また原点は含まれない。この点の中から3点を選んで三角形を作った時に原点が内部に含まれるようなものの個数を求めよ。 解法 普通に考えるとO(N^3)になってしまうので、工夫する方法がないかを考えます。 定数の2500という条件からO(N^2)か、O(N^2 ...