topcoderはエントリーを開始時間５分前までにする必要がある。topcoderはエントリーを開始時間５分前までにする必要がある。topcoderはエントリーを開始時間５分前までにする必要がある。よし。もう忘れない。 ということで参加はしていない。後日取り組んで…

3050 Hopscotch概要 ５×５のマスに整数が書いてある。 適当なマスからスタートして４方好きな方向に５回移動する。 そのとき到達した６個のマスを順に並べてできる数は 何個あるか答える。 例えば、1→1→1→1→2→1と移動したら111121が得られる。方針 (4^5)*5*5…

2323 PERMS 概要 1からn、n個の数からなる順列を考えたとき、ある２つの数を見たとき 大きい数が小さい数より前（左側）にあるときinversionであるという。 例えばは3>1と3>2より2 inversionsである。 nとkが与えられたとき、n個の数からなる全ての順列の内…

2485 Highways n個の町を高速道路で繋ぐ計画。 どの町にも高速を使ってアクセスできるようにするとき、町間の高速道路の長さの最大値が 最小になるような計画を立てて、最大値を答える問題。最少全域木問題だから、貪欲法で解ける。 初めてunion findを使っ…

1019 Number Sequence S1S2...Sk...という数の集合の列をnumber sequenceという。 Skは12...kという数列である。 入力iが与えられたときi番目の数を答える問題。!!! 注意 !!! S10は12345678910であり、11個の数から構成される。 S10の10番目の要素は1であり…

3255 Roadblocks1からNまでのパスの内、２番目に短いものを探す。後で調べてわかったけどこれはk-th shortest pathという問題らしい。そういえばアルゴリズムの講義でやった気もしないでもないけど、とりあえずchokudaiくんの教えにしたがって、アルゴリズム…

3268 Silver Cow Party牛パーティー。N個の農場があって、２農場間を繋ぐパスがM個ある。 各農場に1からNというナンバリングをしたとき、X (1 ティーが催される。 各農場から代表牛が参加する時、行き帰りの距離が最大になる牛の移動距離を求める問題。（た…

2247 Humble Numbers2, 3, 5, 7しか素因数をもたない数をhumble numberと呼ぶ。ただし1はhumble numberである。 入力n (1 …のはずが！この問題を解くにあたって参考にしたサイト → 英語の数字の読み方・書き方 基数・序数編なぜか？それは後ほど。この問題。…

2603 Brave balloonists 気球に乗って旅する１０人の数学者が赤道を越えて喚起乱舞してシャンパンを開けたらコルクが気球を突き破って落ちて死ぬお話。気球が落下する前に誰かが犠牲になる（海にダイブする）ことで他の９人を助けることができる。誰が犠牲に…

3061 Subsequence N個の数字から成る数列の部分数列で、その和がS以上であるものの内、最小の長さを求める問題。英文は簡単に読める割にAC率が30％強という問題。単純に（何も考えずに）やろうとすると、sum[i][j]をi番目の数字を先頭とする長さjの部分数列…

牛がボーリングするらしいよ…問題文は謎だったけど、要するに２分木の根から葉までのスコアの最大値を求めるものらしい。以前の俺ならすべてのパス（2^N個）のスコアを計算しようという愚行をしでかしていただろう。だがッッ！！今の俺にはDPがいるッッッ！…

1080 Human Gene Functions ２つの遺伝子がどれだけ似ているか(similarity)を計算する。 これまたPKUに興味を持つきっかけになった1159 Palindrome（halwhiteがLCSを教えてくれて解けた）に似ているなぁと思ってDPの練習としてやってみた。 dp[i][j]をseq1の…

1579 Function Run Fun たらいまわし関数。 友人が卒論でベンチマークとして竹内関数を使っていたとき初めて知ったたらいまわし関数。普通に実装しちゃったら何時間もかかるよって問題文に書いてあるたらいまわし関数。これは昔3036 Honeycomb Walkでやった…

古代の暗号を暴け！ 以下の２種類の暗号化方式がある。 Substitution cipher あるアルファベットを他のアルファベットに置き換える Permutation cipher 文字列の順番を入れ替える １つの暗号化方式だけだと弱いので、組み合わせて使う。問題は２つの文字列が…

2141 Message Decowding 問題は超簡単。 26文字の新しいアルファベットを定義して、それに基づいて入力された文字列を デコードするというもの。 ただちょっと詰まったところがあったので備忘録。 詰まったコード。 #include<cstdio> #include<ctype.h> using namespace std; </ctype.h></cstdio>…

2591 Set Definition 1338 Ugly Numbersやったらhalwhiteが紹介してくれた類問。1338は1500番目までのUgly Numbersを求めればよかったから、 Uglys[1500]に格納すれば良かったけど、今度は10,000,000までの Sを求めなければならないから配列確保できるのか？…

3085 Quick Change 25, 10, 5, 1セント硬貨があって、お釣りを最少の枚数の硬貨で 返す方法を考える問題。 例えば、お釣りが194セントなら、25セント7枚、10セント1枚、 5セント1枚、1セント1枚を返す。 単純に大きい額の硬貨から選んでいけばよい。 (以前or…

2533 Longest Ordered Subsequence 与えられた数列から昇順の部分数列を取り出したとき、 要素数最大のものの大きさを答える問題。 PKUに興味を持つきっかけになった1159 Palindromeに似てるなぁ、 と思ってDPでやるのだろうと思ったけど挫折。 思考錯誤した…