出典 Aizu Programming Contest, University of Aizu, Aizu-Wakamatsu, 7-8 June, 2003 問題概要 各要素が-100以上100以下の整数の集合（最大五つ）と、それを含む集合演算の式が与えられる。集合演算の結果を要素をスペースで区切って出力せよ。 演算結果が…

半月前に立てた目標の「今月中にPKU300問」何とか達成できた。 2608 Soundex 文字列を規則にしたがって変換する問題。 2853 Sequence Sum Possibilities 与えられた整数n（n＜2^31）が、何通りの連続する自然数の和で表すことが出来るか求める問題。項数をi…

今日通した問題メモ。 2389解いてて思ったけど、TopCoderのMarathon MatchとかでC++使ってる人はみんなどうやって巨大整数実装してるんだろう。乗算とかはやっぱりカラツバ法とかFFTとか使って高速化してるのだろうか。その昔妖精現実というサイトにJavaScri…

id:iwiwiさんがこんなのを公開して下さったようです。 DPと木のデータ構造って僕が今一番苦戦してるとこじゃないか！なんという神。 JOI 春合宿での講義資料(http://d.hatena.ne.jp/iwiwi/20100328) 多分おとといのCodeforces Round#6のEはちょうどこのデー…

三月中に300問行くって目標立てたのに昨日サボリすぎた…… 今日も全然集中できないなあ。とりあえず最低10問はやろう、うん。 3025 Rings n個の円が与えられる。直接または間接的に接触してるリングをグループと見るとき円の個数が最大になるグループの、最大…

緑なので参加。 今回も5問セット。そろそろ問題数が収束しつつあるのだろうか。 前回のDiv2 onlyのRoundは問題が易しめだったので、始まる前に今度は沢山解いてやろうと漠然と思っていた。 A Triangle 4本の棒が与えられる。そのうち3本を使って三角形を作る…

1617 Crypto Columns 平文の順序を変えた暗号文を復号する問題。そのまま実装すればいい。 1799 Yeehaa! 半径Rの大きい円のにn個の半径rの小さい円が輪になって内接している。Rとnが与えられたときの小さい円の半径rを求める問題。方程式を立てて解く。昔な…

なんだか久しぶりな気のするSRM. 今回こそは1問目を早く解くぞと意気込んで臨んだ。ダメだったけど。 Easy 200-600-900セットらしい。一完ゲーの予感がしつつ問題文を読む。 塔をn個の格子点の候補の中から2つを選んで、それぞれの塔の中心がその格子点にな…

今日はTopCoderのSRM! 明日はCodeforcesのRound #6もある。 テンション上がる！ 1106 Transmitters 半円の範囲をカバーするアンテナ一つと、いくつかの点がある。アンテナを回転させたときカバー範囲に入れられる点の最大値を求める問題。それぞれの点が半円…

夏に苦労したPKU1011 Sticksを彷彿とさせる探索問題。今回は2回目でACしたけど。 問題概要 それぞれの長さの与えられたn本の棒（n≦20）を使って正方形を作ることができるか判定せよ。 この問題、使わない棒があってもいいともダメとも書いてないしサンプルか…

さて今日も易しめなの適当に解こう。 2002 Squares 与えられた点の集合の中から正方形の数を数える。二点とって残りの二点を二分探索で探すO(n^2log n)の解法で間に合う。（上位は1桁速いのでもっと高速なアルゴリズムあるのかな？） 2042 Lagrange's Four-S…

解説必要な問題はなし（ｷﾘｯだとブログの意味がないので一応今日解いた問題とその方針だけメモ…… 1111 Image Perimeters How many islands?系の問題。地形の周長を求める。周囲4マスに'X'がない→周長に1プラス。周囲8マスの'X'について再帰。 1132 Border 壁…

ひたすらハイエナ作戦。 （ランキングから他の人の解いてる問題が見られるので、その中で解きやすそうな問題を解くという作戦ｗ） Problem Statusによる問題の難易度推測ができるようになってきた。 Submission5000以下くらいのものについてはAC数を見ること…

旅行先からネットブックで参加。我ながら必死すぎる。 今回は5問セット。 4問セットなら2完を目標にと思っていたけど難易度的にはどうなっているんだろう。 A Aから順番に読んでいく。 チャットシステムを作るにあたってトラフィックをシミュレートせよ。 シ…

東京大学プログラミングコンテスト2009(Problem F) いつの間にかUTPC2009の問題が追加されていたようだ。 問題概要 音の出るn段の階段を、長さmの決められた旋律を演奏しながら降りることはできるか。（n,m≦50000） 階段の降り方は以下の３通り。 1段降りる…

簡単なのばっかりでアレだけど、とりあえず数字上は目標達成。 やっぱり雑魚問でも数を多く解くと疲れる…… 中程度の問題をすらすら解けるようになりたいなあ。 解説するような問題は特になかった。 午後はのんびり休んで夜のSRM(TopCoder)に備えよう。 今日…

参加。 250-550-1000のセット。 Easy 各桁が0-9からなるある文字列が「カラフルである」とは、 その文字列のどんな連続する各桁の積も、全て異なることである。 このときn桁のカラフルな文字列のうちk番目に小さなものを求めよ。 あれ、250だけどパッと方針…

気分転換にPKUの簡単な問題を10問強やった。 三月中に（累計）正解数150問を目標にしよう。 そういえばPKU Judge Onlineの問題を1000問解くと赤コーダーになれるという噂があったような。 頑張って1000問解いて噂の真偽を確かめたいと思うｗ 面白かった問題…

参加してきた。 今回も４問セット。 A ある数n（≦100）が2つの偶数の和で表せるならYES、そうでないならNOを出力せよ。 偶数+偶数=偶数だから偶数なら表せるのかな？あ、でもn=2の時だけは例外。 一応n=100だし全探索のほうが間違いがないから全探索で書こう…

前回飛ばした17,19,23,29は飛ばしっぱなし。 一通り最後まで問題見ていって、２周目に解くことにしよう。 31〜50 31〜50解いた。 飛ばしたの:40,47 47番は問題の意味がよくわからない。 例の644と646って素因数2が共通してるんじゃないのか。 3ページ目から…

小手調べに1〜30まで飛ばし飛ばしに。 飛ばしたの：17,19,23,28,29 要するにまともな数学的考察が必要ないやつだけ（ｒｙ BigIntegerが必要な13,16,20,25はJavaを使ったのだけど、 慣れてない所為でものすごい手間取った。何でこんなにBigInteger使いにくい…

オイラー計画 （今頃）存在を知ったので登録してみた。 http://projecteuler.net/計算機の力を借りて解く数学の問題集のサイト。 解答数のランキング等もある。TopCoderとかで見かける名前がちらほら…… Japanese Translation http://odz.sakura.ne.jp/projec…

Bではまって残り時間10分になってしまったCのPractice. Bより簡単じゃないかorz 問題概要 3x3の盤で行われる先手が×の「○×ゲーム」（ルールは通常と同じ）において、盤面の状態が次のうちどれであるか判定せよ。 先手勝ち 後手勝ち 先手番 後手番 引き分け …

ICPC 2009 東京予選 Problem J 問題概要 n×n（n≦5）セルのライフゲームのセル全て死滅させるのにかかる最小ターン数を求める。ライフゲームのルールは通常と同じである。すなわち、 ターン開始時に、生物のセルについて、周囲8セルのうち、2つまたは3つが生…

A : Shortest path of the king 今回は４問セットなのか。 8x8チェス盤のマスAからマスBまでキングが移動する時の最小手数を求める。 障害物などはない。 ただの実装だけれど、移動方向が8方向あるので場合分けが少し面倒。 20分かかった。赤い人たちはみん…

minx≦x≦maxx，miny≦y≦maxy，minz≦z≦maxzを満たす整数の組 (x,y,z)の個数を求めよ。 ただし1≦minx,miny,minz,maxx,maxy,maxz≦1,000,000,000である。 数字が10億と大きいのでナイーブにループを回して数え上げる方法は取れない。 なんとか√10億（≒3万）くらい…

与えられた数の組number[n]を、ランダムに並べてつなげ、１つの巨大な数にした時にそれがKで割り切れる確率を求めよ。 ただしK≦100、n≦15であり、number[i]のそれぞれは50桁以下であるとする。 全列挙は15!（約1兆）なのでなんらかの計算量削減が必要になる…

という訳で昨日の全探索パターンを書いてみた。 そう、状態数は2500しかないんだよね。 カードのs枚目からt枚目までの最適解をmemo[s][t]とすると、 memo[s][t]=min{memo[s+1][t-1]+opt(Cs,Ct), min{opt(memo[s][i],memo[i+1][t])|s≦i＜t} } ただしopt(a,b)…

EASY 小さい順に掛け算すればいいとSubmit →あれ途中で積が負になったりする？とか不安になってチェックとか入れてResubmit 送ってすぐにいやいや、良く考えたらソートしてるんだからそんなの要らないじゃんと気づく。 Medium 30点くらいEasyで損したことに…

n個のそれぞれ重さw[k]、価値c[k]の宝物(0≦k＜n)、 m個のそれぞれ重さw[k]、価値c[k]の宝物(0≦k＜m)がある。これを重さの合計W以下で価値の和が最大になるよう梱包したい。 ただし最初のn個の宝物は分けることが出来ないが、m個の宝は好きな（実数の）重さに…