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 ある２つの数について、各桁の数の順列が一致する（leading zeroは無視）とき Neibouring Numberであるという。 例えば、40020と204はそれぞれの順列00042と042で一致するのでNeighbouring Numberである。 いくつかの数がvectorで与えられ…

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 …のはずが！この問題を解くにあたって参考にしたサイト → 英語の数字の読み方・書き方 基数・序数編なぜか？それは後ほど。この問題。…

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

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の…