2010-01-01から1年間の記事一覧
えくすぱいあiPhone実機上で自作アプリケーションを動作させるためのProvisioning Profileは3ヶ月で失効するので、更新しなければならない。とりあえず、iOS Dev CenterのProvisioning Portalから新しいProvisioning Profileをダウンロードしてダブルクリッ…
久々のTopCoder最近疎遠になっていたTopCoder。約2ヶ月ぶり。 心機一転のため、気まぐれアカウントkxkから、いつもの keitanxkeitanに移行した。 そんな節目のTopCoder SRM 472。 レーティングは1000からスタート!ColorfulTilesEasy DIV1の簡易版。 R,G,B,…
一生使うパソコンだから…そんなことはない…なんて悲しいことは言いたくないけど、 初めて自分で買った大切なMacだから、ごちゃごちゃさせずに整理整頓、 きれいに使おうと思う。ということで、適当にダウンロードしてきて適当なところにおいて、 その時だけ…
Google Code Jamとは? 世界のGoogleが主催するプログラミングコンテストです。 詳しいことはわかりません。 友達のid:ororogくんに勧められて以前登録だけしていました。ルールGCJのルールは楽しいです。 予選は3問あって、特に難易度順に並んでいるように…
あ…ありのまま(ryPEARのインストールをしようとネット上を東奔西走してたら PEARのインストールは終わってた!ゆとりだからXAMPP使ってPHPやらApacheやら使ってるんだけど、まさかPEARまでインストールされるとは…「XAMPP PEAR インストール」でググって…
topcoderはエントリーを開始時間5分前までにする必要がある。topcoderはエントリーを開始時間5分前までにする必要がある。topcoderはエントリーを開始時間5分前までにする必要がある。よし。もう忘れない。 ということで参加はしていない。後日取り組んで…
3050 Hopscotch概要 5×5のマスに整数が書いてある。 適当なマスからスタートして4方好きな方向に5回移動する。 そのとき到達した6個のマスを順に並べてできる数は 何個あるか答える。 例えば、1→1→1→1→2→1と移動したら111121が得られる。方針 (4^5)*5*5…
stringstreamの勉強としてid:ororogに教えてもらった問題をやった。ToolsBox 概要 vector needのi番目の要素はi番目の家具を作るのに必要な工具を表す。 need[i]の各工具はスペース" "で区切られている。 全ての家具を作るのに必要な工具の数を答えよ。ruby…
TurretPlacement class TurretPlacement { public: long long count(vector <int> x, vector <int> y) { long long result = 0; int n = x.size(); for (int i = 0; i < n; ++i) { for (int j = i+1; j < n; ++j) { double d = sqrt((x[i]-x[j]) * (x[i]-x[j]) + (y[i]</int></int>…
NumberNeighbours ある2つの数について、各桁の数の順列が一致する(leading zeroは無視)とき Neibouring Numberであるという。 例えば、40020と204はそれぞれの順列00042と042で一致するのでNeighbouring Numberである。 いくつかの数がvectorで与えられ…
2323 PERMS 概要 1からn、n個の数からなる順列を考えたとき、ある2つの数を見たとき 大きい数が小さい数より前(左側)にあるとき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までのパスの内、2番目に短いものを探す。後で調べてわかったけどこれはk-th shortest pathという問題らしい。そういえばアルゴリズムの講義でやった気もしないでもないけど、とりあえずchokudaiくんの教えにしたがって、アルゴリズム…
3268 Silver Cow Party牛パーティー。N個の農場があって、2農場間を繋ぐパスがM個ある。 各農場に1からNというナンバリングをしたとき、X (1 ティーが催される。 各農場から代表牛が参加する時、行き帰りの距離が最大になる牛の移動距離を求める問題。(た…
2247 Humble Numbers2, 3, 5, 7しか素因数をもたない数をhumble numberと呼ぶ。ただし1はhumble numberである。 入力n (1 …のはずが!この問題を解くにあたって参考にしたサイト → 英語の数字の読み方・書き方 基数・序数編なぜか?それは後ほど。この問題。…
MAYAH.JPさんのブログで 500をDFSで書いている素晴らしいコードを見つけたので拝借して。。。自分の書いたダメなコードと比較すると、明らかにcolorfulではない数をチェックしているかしていないか、という違いだけなように思う。 その証拠にfor (int i = 0;…
撃墜された500を清書してみた。 ちょっと書き換えてみたけど結局システムテストで落とされた\(^O^)/[方針] n桁の全ての数に対してcolorfulかどうかのチェックをして、 colorfulだった場合カウンターをインクリメントしていって k番目のcolorfulstringを…
久々に挑戦![250 ColorfulBoxesAndBalls] numRed個の赤箱と赤ボール、numBlue個の青箱と青ボールがある。 赤箱に赤ボール、青箱に青ボールを入れるとそれぞれonlyRedポイント、onlyBlueポイントが得られる。 赤箱に青ボール、青箱に赤ボールを入れるとbothC…
2603 Brave balloonists 気球に乗って旅する10人の数学者が赤道を越えて喚起乱舞してシャンパンを開けたらコルクが気球を突き破って落ちて死ぬお話。気球が落下する前に誰かが犠牲になる(海にダイブする)ことで他の9人を助けることができる。誰が犠牲に…
3061 Subsequence N個の数字から成る数列の部分数列で、その和がS以上であるものの内、最小の長さを求める問題。英文は簡単に読める割にAC率が30%強という問題。単純に(何も考えずに)やろうとすると、sum[i][j]をi番目の数字を先頭とする長さjの部分数列…
牛がボーリングするらしいよ…問題文は謎だったけど、要するに2分木の根から葉までのスコアの最大値を求めるものらしい。以前の俺ならすべてのパス(2^N個)のスコアを計算しようという愚行をしでかしていただろう。だがッッ!!今の俺にはDPがいるッッッ!…
1080 Human Gene Functions 2つの遺伝子がどれだけ似ているか(similarity)を計算する。 これまたPKUに興味を持つきっかけになった1159 Palindrome(halwhiteがLCSを教えてくれて解けた)に似ているなぁと思ってDPの練習としてやってみた。 dp[i][j]をseq1の…
1579 Function Run Fun たらいまわし関数。 友人が卒論でベンチマークとして竹内関数を使っていたとき初めて知ったたらいまわし関数。普通に実装しちゃったら何時間もかかるよって問題文に書いてあるたらいまわし関数。これは昔3036 Honeycomb Walkでやった…
古代の暗号を暴け! 以下の2種類の暗号化方式がある。 Substitution cipher あるアルファベットを他のアルファベットに置き換える Permutation cipher 文字列の順番を入れ替える 1つの暗号化方式だけだと弱いので、組み合わせて使う。問題は2つの文字列が…
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でやるのだろうと思ったけど挫折。 思考錯誤した…
keitanxkeitanです。友人がやってるのでやるという単純思考で開設。最近友人の勧められて(いや、勝手にまねして・・・) PKU Judge Onlineやってます。 世界中のプログラミング大会の過去問を集めてるサイトで、 かの北京大学が運営してるとか(北京ってBei…