Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

Beta Round #15 (参加記録) (この記事を編集する[管理者用])

2010年05月30日00時から2時間15分,5問.
[ Link ]
全体的にサーバの調子が悪く繋がりにくかった.(ので2時間の予定が15分延びた)

A. Cottage Village

1次元の世界で,中心x[i],幅w[i]に家が建っている.家の数は1000個以下.
自分は幅wの家を建てたいのだけど,少なくても1個の家に接するように建てたい.
オーバーラップしてはいけない.
家の建て方は何通りあるか調べる問題.

各家の占める場所はx[i]-w[i]/2からx[i]+w[i]/2まで.
小数やだ,2倍する!
後は,両端の2通りと,家の間がwより大きければどちらに寄せるか2通り,ちょうどwだったらすっぽり入れる1通り足していく.
ログインしようとしたらサーバにつながらない.
つながれーつながれー.
繋がった.サブミット.
繋がらなくなった….
繋がれー繋がれー.
問題はBとCは開けたけど,DとEは読み込み中で止まってる.
まぁ,次の問題見よう.

B. Laser

n*mのチョコレート板の2点(x1, y1), (x2, y2)にレーザーが当てられている.
2つのレーザーは最初チョコレート板があった範囲の外にでないように,両方共,同じように移動できる.
レーザーでチョコレート板を溶かしきったとき,残ってるチョコレート板の面積を求める問題.

問題文わっかりにっくいなぁ….
うーん,ああ,そういうことか.
最初の2点のx座標の差とy座標の差のみ重要…なんだよね?
左上端と右下端に(x座標の差)*(y座標の差)だけ残る.
書く.書いた.long longにしないとダメなあたりに気をつけよう.
サブミットできんので,一旦Cに行く.

C. Industrial Nim

nを10000以下として,10^16以下の整数x1, t1, ..., xn, tnが与えられる.
石の山が
 x1, x1+1, x1+2, ..., x1+t1-1
 x2, x2+1, x2+2, ..., x2+t2-1
 …
 xn, xn+1, xn+2, ..., xn+tn-1
のNimが先手必勝か後手必勝かを判定する問題.

要するに,1~nまでのXORを高速に求めてくださいという問題.
それはbitごとにみると,周期性があるのでそれを利用すればOK!
ってことで書く.
書いたところで,サーバーが一瞬復活.AはAcceptだった.
BとCを送る.
サーバー落ちた.
結果見れないけどStandingのみ見れた.
Cは通ってる.Bは-1とか書いてる.あ,間違えてる気がする.

B. Laser (再)

残った破片が普通に繋がっていることもある….
切り取られるのは,左下隅,左上隅,で両方に切り取られている部分は包除原理により足してあげよう.
これでいいんじゃ?
サブミット…できない.
できた.Accept.

E. Triangles

図のような三角形のうち,上の頂点から始まって元に戻ってくるパスの数をmod 1000000007で求める問題.
ただし,パスは自分と接してはいけないし,パスで囲まれる部分にグレーの部分を含んでいてはいけない.

グレーを含んでいてはいけないという文を読み飛ばした.
とりあえず,無理ゲー.
規則を探す?
普通にDFSして小さいとき求めてみた.
あれ,74ってn=3の時の答えだぞ….
数列検索してもよく分からない,Dに行こう.

D. Map

1000*1000の場所の高さが与えられる.
a*bのビルを建てたい.
建てるときは建てる場所のうち,標高が最も低い場所にあわせて,余分な部分を削る.
次のような操作を繰り返す.
 建てれる場所が残っているなら,最小削りで建てれる場所のうち,最も左上に建てる
結果をシミュレーションする問題.

とりあえず,a*bの部分の和と,a*bの部分の最小値を全部計算しないといけない.
えーっと,和はO(1000^2)でできるけど….最小値は…できる…の?
最悪でもO(500^3)なのでちょっと愚直に書いてみようか.
ローカルで1秒ちょっと,間に合う…か,間に合わない…か,微妙な感じ.
とりあえず,暫定的にこれで行く.
あとはどうする?
GCJ 2010 Round 1CのC問題に似てる.
ヒープ作って…,なんてしたらオーバーフローする….
いや,ヒープいらん.
各マス更新すると作れなくなるだけなので,最初にソートして,立地条件のいい場所から建てていく.
前建てたのと重なって建てればいフラグが建っているなら飛ばすだけでいい.
書いた.
送信.WA.
あれ….
ソート間違えてる….ていうかwhileと書くべきをifと書いてる.なんていう初歩的ミス.
送信.WA.
あれ….
ソートまだ間違えてる.余分な+1がある.
送信.もっと早い段階でWA.
%lldにしてた….
送信.Accept.

E. Triangles

あー,グレーは囲んではいけないことを理解.
なんか,普通にDPっぽく計算出来そうな気がする.
間違えて,ページ再読込したら,繋がらなくなった.
ちょっと,図が見えない!
つながれー,つながれー,つながれー,つながれー.
なかなか繋がらない….
でも,時間的にこれ解くの苦しいかなぁ….
諦めよう,うん.

Result

レート更新されるのかされないのか分からないけど,悪くない順位.サーバ不調で諦めた人が多いのかも.
UVaとかで鯖落ち耐性はある程度あるのが良かった…のか?
コンテスト開いてくださってる側も頑張ってるのだと思うし,こういう時は,イライラせずに,結果はどうあれ問題を楽しみましょう,というの感じで.

University of Aizu Programming Contest 2010 (参加記録) (この記事を編集する[管理者用])

2010年05月29日13時から5時間,11問.UAPC 2010.
[ Link ]

問題文がネタ満載.
結果はKを諦めて10問通した.
以下時系列順.

・K: Seventh Color
今日も逆から読んでみる.
幾何,面倒だけど,別にそんなに難しくないんじゃないの?
点が円に含まれてるかどうか全部の円に対して求めて,塗る辺の適当に求めれば.
コード書いてみよう.
…,いや,そんなに単純じゃなかった.
飛ばす.
・J: No Story
素因数分解して,どっちに振り分けるか.
書くだけ.書いた.答えあわねぇ.
aとbには大小関係が付いてた!
等しくなる場合は両方ともLのときだけだから,1足して2で割れば良い?
良さそう.サブミット.Accept.
・I: Mysterious Onslaught
2^25の状態がある.メモリ足りねぇ.探索か?
取り敢えず飛ばす.
みょんみょん.
・H: Winter Bells
取り敢えずワーシャルフロイドしておく.
ノード0からノードkに向かう最短路の数,ノードkからノードn-1に向かう最短路の数を適当に求めてやればいいよね.
DPする…がダイクストラっぽく順序付けてやればいいはずだけど,面倒なので収束するまで回す.
doubleで持ってるから収束したかどうかどうやって判定するの….
十分に大きい回数だけ回すことにするw
(なんか書いてたらちょうどBGMがこれになった…,でぃんどんだんどん)
インデックスミスったりして2WA.その後Accept.
・G: Rolling Dice
サイコロころころなダイクストラ.面倒.飛ばす.
・F: Ben Toh
普通にDPするとO(n^2)でTLE.
だけど,連続して50回以上弁当買える確率なんて無に等しいので,無視して,n*50の計算量にしてしまう.
(実際doubleで計算して50回連続で買える確率は0になった)
Accept.
・E: Huge Family
最小全域木の数.(微妙に読み間違えてる)
わからん,次.
・D: Distorted Love
少しだけめんどうなシミュレーションっぽい.次.
・C: Accelerated Railgun
問題文の意味がわからない.
原点中心にバリアはったら,原点に届かないじゃないか….(制約やサンプルをちゃんと見てない)
無視.次.
・B: Old Bridges
どうみてもgreedy.ソートして順番に行く.
Accept.
・A: Citation Format
書くだけ.Accept.
逆順に見てきたので,今度はAから順番に戻っていく.
・C: Accelerated Railgun
問題の意味理解.最初から円の中にいるのね.
うーん,跳ね返すのシミュレーションするのかな?めんどうじゃない?
というか誤差怖い.
跳ね返る時どうなるかって式は…,ってこらこら.
中心通るなら 入射角 = 反射角 = 0 じゃないとだめだよね.
ってことは,最初から中心に向かっているか,中心と反対方向を向いている場合しかない.
簡単だ.書く.
WA, WA, WA.
直線上にあるかどうかの判定が
 符号付き面積 < EPS
と書いてたり(絶対値をとってない),原点を向いてるかどうかを,1秒後に最初より原点に近づいているかどうかとか書いてたり.
これは,いくらなんでもちょっとばかじゃないの….
Accept.
・D: Distorted Love
書くだけ.だけど文字列書かなきゃいけないのでこれだけC++で書いた.
Accept.
・G: Rolling Dice
ダイクストラ書くのが面倒だったので,ベルマンフォードでお茶を濁した.問題なかった.Accept.
・E: Huge Family
うーん,どうやるんだ….
って,ちょっとまって,枝の数n本しかなくないか?
ないじゃん.
ループになってる中で,最もコストが大きいのを1本だけ抜けば良い.
その抜き方の数.
サンプルの図を描いてみよう….
あれ,連結じゃない場合もあるの?
ある.問題文ちゃんと読め.
面倒だな….
連結成分ごとに分けて考えて,次数が1のノードを取り除いて,取り除いても良い枝の集合を求めて,その中で一番大きなのは何個あるかを掛けていく.
書こうか….
入力書いてる途中に,ふと,次数1のノードなんてないことに気づく.
面倒じゃなかった.
Accept.
・K: Seventh Color
とりあえず書いてみる.
ごにょごにょー.
交わってるところでぶった切って,円弧に分けて,その円弧の中心から敵に向かって線を引いて,他の円に交わらないなら,その長さを足していく.
O(n^3).
サブミット.TLE…だと.しかも10秒内に終わってないTLE.(AOJはTLEでも10秒までは走って,それ以内に処理が終わったらかかった時間を出力してくれる)
これで,TLEとかいわれたらちょっと…どうするのよ….
・I: Mysterious Onslaught
普通にDFSで探索してみよう.
とりあえず,バグ怖いので,愚直に書く.
あれ,テストケース一瞬で終わるぞ.
いけるんじゃない?サブミット.TLE.
うーん,なんか幾つかテスト作っても結構一瞬で終わるし,答えが5より大きいケースがほとんどない気がする.
最大の答えを決め打ちして送ってみる.WA.結構大きいケースも作れるらしい.
あ,ちょっと遅いケース見つけた.0.3秒かかる.
ビット使ってちょっと高速化してみる.0.1秒になった.サブミット.相変わらずTLE.
n=5のケースの後半だけメモ化してみるか….
残り3行だけメモ化する,2^15の場合の数.
あんまり速くならない….
4行メモ化する,2^20の場合の数. 最初に2秒ぐらい前計算が必要だけど,結構一瞬で答え出るようになった.
サブミット.Accept.
・K: Seventh Color
なんか,ジャッジデータ訂正したよ,とか書いてある.試しに送ってみる.
0.00秒でWA.やった.
ちゃんと考える….
考えれば考えるほど,これ難しいぞ….
かきかき,こんな場合はどうする?[ jpg ]
(円が接することはないっていう条件が加わる前なので接してますが,本質的には変わらない)
ぇー.
ぐるりと回れば良い…かも.
まわる方向は?
敵を含んでる円は時計回り,そうじゃない円は反時計回りに円周上をまわる.
いけるんじゃない?
WA.
でも,良く考えたら,円が連結とは限らない.
特に,円の中に他の円がすっぽり収まってる場合もあるし.
円の塊を回り込んで移動したら,向こうの円に触れれる場合もある.(特にこれが困った)
ちょっと,どうするのよ….
諦めた.

SRM471 DIV2 HARD - Thirteen (この記事を編集する[管理者用])

Source

TopCoder SRM471 DIV2 HARD (1000pt)
(サーバー不調でノーゲームとなった回,問題文はArenaから見れます, ホームページには無い)

問題概要

ノード数50以下の有向グラフが与えられるので,ノード0からn-1に行く以下の制約を満たす最小距離を求める問題.
ただし,自分自身に枝をはってるかもしれない.
制約は,移動距離がT1, T2, T3という枝を通ったのであれば,
 T1, T1+T2, T1+T2+T3
のどれも13の倍数ではない.

解法

今までの距離の和%13の値を付与して,各ノードを13倍に拡張してダイクストラする.

C++によるスパゲッティなソースコード

続きを読む

SRM471 DIV2 MEDIUM - EllysPlaylists (この記事を編集する[管理者用])

Source

TopCoder SRM471 DIV2 MEDIUM (500pt)
(サーバー不調でノーゲームとなった回,問題文はArenaから見れます, ホームページには無い)

問題概要

50個以下の曲名が与えられる.
ちょうどK曲からなるプレイリストを作る.
同じ曲が何回あっても良いが,Aという曲の次の曲がBならば,Aの曲名の最後3文字と,Bの曲名の最初3文字が一致していなければいけない.
作り方のパターンの数 mod 1000000007を求める問題.
Kは1000以下.

解法

DPする.dp[i][j] = i曲目終了時,最後の曲がjの場合のパターンの数 としてみた.

C++によるスパゲッティなソースコード

続きを読む

SRM471 DIV2 EASY - PrimeContainers (この記事を編集する[管理者用])

Source

TopCoder SRM471 DIV2 EASY (250pt)
(サーバー不調でノーゲームとなった回,問題文はArenaから見れます, ホームページには無い)

問題概要

1000000以下の正整数Nが与えられるので,
 N/2^k (k=0,1,2,...)
に何個素数があるか求める問題.

解法

素数判定を書く.

C++によるスパゲッティなソースコード

続きを読む

SRM471 DIV1 HARD - ConstructPolyline (この記事を編集する[管理者用])

Source

TopCoder SRM471 DIV1 HARD (1000pt)
(サーバー不調でノーゲームとなった回,問題文はArenaから見れます, ホームページには無い)
SRM 471 自分の参加記録

問題概要

3次元上の有向線分が50個以下与えられる.
平行移動して,1本の自分と交わらない線分にしたとき,始点と終点の距離の最大値を求める問題.

解法

結局,3次元ベクトルを足したり引いたりして2ノルムを最大化する問題.
リスタート+ランダマイズ局所探索でシステムテストは通った.
想定解放はまだ理解していない.

C++によるスパゲッティなソースコード

続きを読む

SRM471 DIV1 MEDIUM - ThirteenHard (この記事を編集する[管理者用])

Source

TopCoder SRM471 DIV1 MEDIUM (500pt)
(サーバー不調でノーゲームとなった回,問題文はArenaから見れます, ホームページには無い)
SRM 471 自分の参加記録

問題概要

ノード数25以下の有向グラフが与えられるので,ノード0からn-1に行く以下の制約を満たす最小距離を求める問題.
ただし,自分自身に枝をはってるかもしれない.
制約は,移動距離がT1, T2, T3という枝を通ったのであれば,
 T1, T2, T3, T1+T2, T2+T3, T1+T2+T3
のどれも13の倍数ではない.

解法

今までの距離の部分和%13の値をどれだけ取っているか,各ノードを2^13倍に拡張してDPする.
ループがあると勘違いしてダイクストラしたけど大丈夫だった.以下のコードはダイクストラ.

C++によるスパゲッティなソースコード

続きを読む

SRM471 DIV1 EASY - PrimeSequences (この記事を編集する[管理者用])

Source

TopCoder SRM471 DIV1 EASY (250pt)
(サーバー不調でノーゲームとなった回,問題文はArenaから見れます, ホームページには無い)
SRM 471 自分の参加記録

問題概要

 p/2^0, p/2^1, ..., p/2^k
が全部素数のとき,自然数pにスコアkをつける.
D以上のスコアを持つ,N以下で最も大きい自然数を求める問題.
存在しないなら,-1を返す.
Nは10^7以下,Dは10以下.

解法

エラトステネスで素数求めて,DPで全部のスコアを計算する.

C++によるスパゲッティなソースコード

続きを読む

2010 Round 1C C問題 - Making Chess Boards (この記事を編集する[管理者用])

Source

Google code jam 2010 Round 1C C問題
Problem Statement
SPOJ 6706 [CT101CC] (2010/05/28 23:45追加)

問題概要

各セルが黒か白かのM*Nのグリッドが与えられる.
チェス盤を切り取っていく.チェス盤は白と黒とが交互になっている市松模様の正方形の盤面.
切り取っていく順番は,できるだけ大きいのから,複数あるなら,左上のから切り取る.
最終的に,どのサイズのチェス盤が,どのぐらい切り取られたかを求める問題.
small: M, Nは32以下
large: M, Nは512以下

解法

全てのマスに対して,そのマスを左上角になるようなチェス盤のうち,最大サイズをDPで求める.これはO(MN)で可能.
後は,実際に大きいものから切り出していって,切り出されたことによって,DPの値を修正していく.
このときに,サイズごとになぞっていくとO(MN*MIN(M,N))ぐらいになる.
ヒープを使うと,O(MN log(MN))ぐらいで解ける.

Cによるスパゲッティなソースコード

続きを読む

2010 Round 1C B問題 - Load Testing (この記事を編集する[管理者用])

Source

Google code jam 2010 Round 1C B問題
Problem Statement
SPOJ 6678 [GCJ101C]

問題概要

あるサーバはL人の負荷には耐えれて,P人の負荷には耐えれないということが分かっている.
Cは2以上10以下の与えられた定数として,a人の負荷に耐えれて,a*C人の負荷に耐えられないというaを1つ見つけたい.
負荷テストを1回行うと,好きなXに対して,X人の負荷に耐えれるかどうかがわかる.
最小負荷テスト回数を求める問題.
small: L, Pは10^3以下
large: L, Pは10^9以下

解法

再帰的に考えると,Lを固定したとき,n回の負荷テストでaを見つけることのできる最大のPはP=L*C^(2^n)であることがわかる.

Cによるスパゲッティなソースコード

続きを読む

2010 Round 1C A問題 - Rope Intranet (この記事を編集する[管理者用])

Source

Google code jam 2010 Round 1C A問題
Problem Statement

問題概要

それぞれ要素数Nの相異なる数字からなる数列A[i]とB[i]が与えられる.
N本の線分の端点をそれぞれ(0,A[i])-(1,B[i])としたとき,交点の数を求める問題.
ただし,3本以上の線分が同じ点で交わることはないとする.
small: Nは2以下.
large: Nは1000以下

解法

全部の線分の組み合わせに対して,交わってるかどうか判定する.

Cによるスパゲッティなソースコード

続きを読む

2010 Round 1B C問題 - Your Rank is Pure (この記事を編集する[管理者用])

Source

Google code jam 2010 Round 1B C問題
Problem Statement

問題概要

与えられた2以上の自然数Nに対して,
 {2, 3, ..., N}
の部分集合SでNがPureなものの数をmod 100003で求める問題.
F(N)を集合Sの中にあるN以下のものの数として
 「NがPure」 とは 「F(N)=1 か F(N)がPure のどちらかが成り立つ」
で定義する.
small: Nは25以下.
large: Nは500以下

解法

コンビネーションを使いながら計算するO(N^3)のDP.
 dp[i][j] = {2, 3, ..., i}の部分集合でiがPureで要素数がjの集合の数

Cによるスパゲッティなソースコード

続きを読む

2010 Round 1B B問題 - Picking Up Chicks (この記事を編集する[管理者用])

Source

Google code jam 2010 Round 1B B問題
Problem Statement
SPOJ 6691 [GCJ101BB]

問題概要

N匹のひよこが1次元上を移動できる.
各ひよこの初期位置,最大スピードが与えられる.
最初,各ひよこは目的地の左にいる.
K匹以上が目的地に辿り着くために,最小のひよこの追い越し回数を求める問題.
不可能ならそれを指摘する.
small: Nは10以下.Kは3以下
large: N, Kは50以下

解法

目的地に辿り着けるひよこを追い抜かす必要はない,後ろからついていけば良い.
なので,目的地に辿りつけるひよこは,自分より前にいる,目的地に辿り着けないひよこの数だけ追い抜けば目的地にたどり着ける.
つまり,初期位置で前からK匹の目的地に辿り着けるひよこが,目的地に辿り着くまでに追い抜くひよこの数の和を求める.

Cによるスパゲッティなソースコード

続きを読む

2010 Round 1B A問題 - File Fix-it (この記事を編集する[管理者用])

Source

Google code jam 2010 Round 1B A問題
Problem Statement

問題概要

すでに作られているフォルダのパスがN個与えられる.
新しく作りたいフォルダのパスがM個与えられるので,mkdirコマンドを叩かないといけない数を求める問題.
small: N, Mは10以下
large: N, Mは100以下

解法

文字列+実装問題.
すでに作られているフォルダパスを全部ハッシュに入れていった.

Cによるスパゲッティなソースコード

続きを読む

SRM471 DIV1 参加記録 (この記事を編集する[管理者用])

2010年05月27日00時02分から.
サーバ不調のため途中からコンパイルできなくなり,ノーコンテスト.

Assignment

久しぶりに,青~黄色下位が多い気がする部屋.
それよりTomyam先生のデビュー戦.

EASY

 p/2^0, p/2^1, ..., p/2^k
が全部素数のとき,自然数pにスコアkをつける.
D以上のスコアを持つ,N以下で最も大きい自然数を求める問題.
存在しないなら,-1を返す.
Nは10^7以下,Dは10以下.

前回(ニコ生Open 第2回)の反省を踏まえて,じっくりゆっくりやる.
エラトステネスで素数求めて,DPで全部のスコアを計算する.
エラトステネスの配列をcharで,DPをintで持てば50MBなのでメモリは大丈夫.
書いた.0.5秒とかかかるのか,ローカルだと一瞬なんだけどな,でもそれが最悪ケースだから問題ない.サブミット.
(なんか,サーバーの実行時間も不安定だった模様)
dが7以上で-1なのか…,まぁ,そんなもんかも.

MEDIUM

ノード数25以下の有向グラフが与えられるので,ノード0からn-1に行く以下の制約を満たす最小距離を求める問題.
ただし,自分自身に枝をはってるかもしれない.
制約は,移動距離がT1, T2, T3という枝を通ったのであれば,
 T1, T2, T3, T1+T2, T2+T3, T1+T2+T3
のどれも13の倍数ではない.

問題文読む.
問題文中の例が意味分からん,13は13の倍数じゃないのか??
サンプル見ると,最初のサンプルで13は駄目だよって書いてあるぞ,どういうことぞ???
つうか,最初のサンプルおかしくね?
なんで最小パス13なんだ?距離27以上の枝しかねぇぞ??
なんだこれ???
小文字と大文字の距離が逆なの?
逆っぽい.
なんか,こんなくだらないことで悩んでないで,取り敢えず書こう.
ていうか,問題読解にだいぶ時間かかってるんだけど,これ自分のせいじゃないよな….
方針は簡単.
今までの距離の部分和%13をどれだけ取っているか2^13倍にノードを拡張してダイクストラでしょ.
細かいことは考えてないけど,書けばわかるよ.がりがり….
あー,これ条件から,ビット立てて行く時,新しく絶対ビット立てれないと13の倍数になって駄目で,1のビットは1つずつ増えていく.
ループないよー,ダイクストラじゃなくてDPでいいじゃん.
そういうのが見えてないのが頭弱い.無駄に実装量増やしているだけ.
まぁ,書き始めたからこのままいく,そっちの方が速い.
サンプル通った.提出.

HARD

3次元上の有向線分が50個以下与えられる.
平行移動して,1本の自分と交わらない線分にしたとき,始点と終点の距離の最大値を求める問題.

どゆこと?
不可能な場合とか書いてないけど,絶対に作れるのか?
うーん.
てか,これ,2次元版の問題PKUかどっかになかったっけ…,なんか結構感動した解法だった気がするが…,憶えてないんじゃ意味ねぇな….
うーん.
不可能な場合はない,作れる.
というか,多分,x[i], y[i], z[i]をマイナス1倍しても良い,2^50通り試して,その中で最も
 xの和^2 + yの和^2 + zの和^2
が大きくなるのを求める問題と同値.
ちょっと自信ないけどたぶんそう.
さて,どうするんだ….
幾何的に考えるのか,それとも,単純に数字として扱った方が楽なのか….
800点台とかで提出してるな,なんだと,簡単なのか?
わからん.
でも,2^50通りしか考えれないし,リスタート+ランダム局所探索で通っちゃったりするんじゃない?
そう思ったら通る気がしてきたぞ?
いまから,一瞬で局所探索書いて,サブミットして通したら上位狙える.
いいや,やっちゃえ.
コンパイルできないんですけど….
でも,チャットみても,皆,コンパイルできねーとか言ってないな…,リログするか.
リログした,チャットが全く進んでない件.
twitter見ると皆同じ症状.
ノーゲームかなぁ.
てか,せっかくのTomyam先生のデビュー戦なのに….

Challenge

そんなものはなかった.

System tests

後でプラクティスでシステムテスト試すとEasy, Medium, Hard全部通った.
あー,惜しかったなぁ….
偉い人の「500はダイクストラだとTLE疑惑」で戦々恐々としてたけど,最悪ケースで7msだった.
てか,Hard,やっぱりランダムで通るんかい.まぁ,想定解法ではないはずなのでのちのち勉強.

TopCoderニコ生オープン 第2回 (参加記録) (この記事を編集する[管理者用])

2010年05月25日22時20分から.
(TopCoder Open 2010 Algorithm Qual. 3は2010年05月25月10時02分から)

TopCoderニコ生オープンとは

red.cliff.jpの診断人さん主催の大会です.
今回はTopCoder Open 2010 Algorithm Qual. 3に出れない人たちが,終了後に皆でQual. 3を本番形式で解こうという大会です.
TopCoderニコ生オープンのコミュニティはco329335
自分も放送しながら参加しました.自分の放送は→.[ 1枠目 ] [ 2枠目 ] [ 3枠目 ]

Easy

n*mのグリッドの数字を書く.1行目と1列目の数字は与えられている.
小さい2*2のグリッドを見たとき,左上の数字は,その他の数字の和になっている.
右下の数字を求める問題.
一意に定まらないなら,それを指摘する.

どうみても一意に定まります.罠乙.
左上の方から順番に求めていくだけ.書いた.提出.

Medium

6本の弦のあるギターがある.
それぞれの弦を抑えずにそのまま引くと鳴る音が問題文中で与えられている.
実際に押さえた場所が与えられて,6本の弦に対して,それぞれ,何も押さない時と比べて,i_k×半音だけ高い音が出る.
鳴らさない弦もあるかもしれない.
MajorとMinorしか考えないとして,コードを求める問題.
コードは,3つの音色からなる集合.

CとかD#とかそういうのと整数を対応させるライブラリ前書いたよな….
あった.
適当に実装.
和音を含んでいるかどうか24通り調べて,一意に定まるか調べる.
あれ,ニコ生配信止まってないか?
止まってる.
リロード.
配信開始,ぽちっとな.
何も反応がない….
もう1回リロード,ぽちっとな,ブラウザ強制終了…,ぇ.
取り敢えず提出.
なんか,どうしようもないので,枠閉じて,次枠取ろう.
次枠開始してからでHard開こう.
…あれ,配信開始できないから,配信終了もできない…,なんという罠.
30分経って自然消滅するのを待つ.

Hard

1000*1000以下のガラスがある.
ダイヤモンドのカッターの初期位置と,それをどのように動かしたか,UDLRの文字列で与えられるので,ガラスが何個の破片に別れたかを求める問題.

ニコ生,1100人待ち…だと!?
まー,のんびり待ちましょう…,順番きた.
配信画面なかなかでないなー,なんか重いなー,と思ってたら,1分ぐらいしてサーバがエラーを返しましたとか言ってきた.
リロード!
あれ,なんか,順番待ち中とか言われて,配信画面に入れないぞ.
どうなってるの?
5分ぐらいたってから入れた.
さっきは10秒以上遅延してたけど,今度は遅延は少ない.
てか,もう30分も時間残ってないじゃないか,Hard開こう.
草刈るのにダイヤって何だ…,って草じゃねぇw (お約束だったみたい)
で,問題は,座標を拡大して,塗りつぶすだけ.
縦横2倍したら十分だけど,考えにくいので縦横3倍する.時間的には多分大丈夫だろう.
メモリは…? 大丈夫!
でも,これ,塗りつぶすの再帰するとスタック足りないよね.
まぁ,頑張って書くだけだ.
動かん….
0からHまであるので,H+1個取りうる値があるよね…,1足さなきゃ.
まだまだ動かん….
UとD逆だ….
ほか変数間違えてたりいろいろ.
通った.サブミット.
チャレンジに備えて,枠を早めに閉じる.
枠取ろうとしたら,まだ放送中になってるよ,早く終わって.

Challenge

枠間に合わなかった….
まぁ,取り敢えず狙いどころは,Hardのスタックオーバーぐらいか?
眺める.うーん,流石に再帰で書いてる人なんていないなぁ….
てか,Mediumって,音の数が3個じゃないと即座に該当なしを返してるな…,え?
いやいや,4つでも,和音含んでることあるだろ…,え??
ちょっとまって,問題文勘違いしてるの自分じゃないの?
問題文読み直す…,え,どっちかわからん.
でも,常識的に考えて,変な音混ざってたら和音って言わないだろ…,たぶん自分が間違ってる.
拗ねた.
拗ね枠始まった.
500落ちるので,同じような点数の人いないだろうし,どうでもいいやという感じでチャレンジ2失敗.

System tests

250と1000は通って,500は落ちる.予想通り.
放送見直してみると,今回の僕はどう見ても焦りすぎ.ニコ生のトラブルが多少有ったのを差し引いても.
定期的に,こういう失敗をしないと,慎重に戻れないので,いい時に痛い目を見て良かったと思う.
忘れたら思い出せ: TopCoderは解ける問題を,慎重に確実に解くだけで,自然に高得点になる.

Mediumの読み間違えは
> The above chord contains three distinct notes: C, E, and G. This chord is called the "C Major" chord.
を見て,C, E, Gを含んでいれば何でもC Majorと捉えてしまった.
もうちょっと常識と照らし合わせて何かおかしいなと疑問に思え,良く考えろ.

2010 Round 1A C問題 - Number Game (この記事を編集する[管理者用])

Source

Google code jam 2010 Round 1A C問題
Problem Statement
2010 Round 1A 自分の参加記録
SPOJ 7260 [NUMGAME] (2010-09-20 10:40追加)

問題概要

2人でゲームをする.
最初正整数AとBが与えられている.
二人交互に任意の正整数kを選んで以下のどちらかを行う
 A を kB だけ減らす.ただし結果はAは正整数でなければいけない.
 B を kA だけ減らす.ただし結果はBは正整数でなければいけない.
打つ手がなくなったら負け.
A1, A2, B1, B2が与えられるので,
 A ∈ [A1, A2]
 B ∈ [B1, B2]
なる先手必勝パターンの数を求める問題.
small: A1, A2, B1, B2は1000000以下,A2-A1, B2-B1は30以下
large: A1, A2, B1, B2は1000000以下

解法

まず,A, Bが与えられたときに,それが先手必勝かどうかを考える.それは  大きい方が小さい方の2倍以上なら,kを何を選ぶかの選択権があるので,必勝
 そうでなければ,減らし方は1通りしかないのでシミュレーションする
でO(log(min(A,B)))で求めることができる.(smallはこれでOK)
それで,実際に先手必敗パターンを書き出してみると,規則が見える.
具体的には,BはA以上として,Aを固定したとき,先手必敗になるのはBがfloor((A-1)*(1+sqrt(5))/2)+1以下のときのみ.
それを実装すればO(min(A,B))で求まる.
(規則を見つけるコードとその実行結果も以下に貼りつけておきます)

Cによるスパゲッティなソースコード

続きを読む

2010 Round 1A B問題 - Make it Smooth (この記事を編集する[管理者用])

Source

Google code jam 2010 Round 1A B問題
Problem Statement
2010 Round 1A 自分の参加記録
SPOJ 6700 [GCJ101AB] (2010/05/28 05:20追記)

問題概要

0以上255以下を要素に持つ長さNの整数列が与えられる.
それの隣り合う項の差をM以下にするために必要なコストを求める問題.
できる操作は以下の3種類.
 コストDで1要素を消す
 コストIで好きな場所に好きな要素を挿入する
 コスト1である要素の数字を1だけ増やすか減らす
small: Nは3以下
large: Nは100以下

解法

 dp[今見てる場所(この場所の前までは条件を満たしている)][一つ前の数字]
でDPしようとしたら,ループしたので,ベルマンフォードっぽく書いた.
2010/05/28 05:20追記 ループのない形のちゃんとしたDPも書いた.以下のコードを追加しておきます.

Cによるスパゲッティなソースコード

続きを読む

2010 Round 1A A問題 - Rotate (この記事を編集する[管理者用])

Source

Google code jam 2010 Round 1A A問題
Problem Statement
2010 Round 1A 自分の参加記録

問題概要

N*NのグリッドにRかBの文字が書いてある.重力によって,文字は下に落ちている.
90度時計回りに回転させる.文字は重力によって下に落ちる.
縦横斜め,一直線上にRとBがそれぞれK個以上繋がっている場所があるかどうかを,それぞれ判定する問題.
small: Nは7以下
large: Nは50以下

解法

実装するだけ.サイズは小さいので愚直な方法で大丈夫.
(実際に回転させなくても,右に寄せるでもOK)

Cによるスパゲッティなソースコード

続きを読む

2010 Round 1A (参加記録) (この記事を編集する[管理者用])

2010年05月22日10時から2時間30分,3問.
[ Link ]

開始前

3回あるなかのどれかで勝ち抜けられれば良いので,まだ気楽なラウンド.
2時間半なので4問か(もしくは5問?)と思ってたら3問しかなかった.

A. Rotate

N*NのグリッドにRかBの文字が書いてある.重力によって,文字は下に落ちている.
90度時計回りに回転させる.文字は重力によって下に落ちる.
縦横斜め,一直線上にRとBがそれぞれK個以上繋がっている場所があるかどうかを,それぞれ判定する問題.
small: Nは7以下
large: Nは50以下

なんか予選より問題わかりやすいなぁ,英語読解力的な意味で.
そして,やるだけ問題.largeでもサイズ小さい.
書いた.WAった.あれ?
左下の斜めのライン考えてないじゃんorz
直した.small correct.largeもついでにサブミット.

B. Make it Smooth

0以上255以下を要素に持つ長さNの整数列が与えられる.
それの隣り合う項の差をM以下にするために必要なコストを求める問題.
できる操作は以下の3種類.
 コストDで1要素を消す
 コストIで好きな場所に好きな要素を挿入する
 コスト1である要素の数字を1だけ増やすか減らす
small: Nは3以下
large: Nは100以下

DPですよねっ.
うーん,dp[残り要素の数][一つ前の要素の数字]でいいかぁ….
ま,サイズ小さいし,最も愚直に書いても実行時間大丈夫だろう.
書く.
あれ?これループしないか?
dp[a][b]から数字cを付け加えたらdp[a][c]が必要になる…,ループする.
まぁ,数字付け加えるのは,次の値に近くなるように付け加えるんじゃなければ無意味なので,そういう時だけ考えよう.
これならループしないよね!
書いた.WAった….またかい.
うーん?
次の要素を変えて,目的を満たす場合もあるよね…,なんでそれ考えてないんだ….
直した.自分で作ったサンプルが合わない.くだらないミスを潰す.自分で作ったサンプルは合った.
small correct.largeもサブミット.

C. Number Game

2人でゲームをする.
最初正整数AとBが与えられている.
二人交互に任意の正整数kを選んで以下のどちらかを行う
 A を kB だけ減らす.ただし結果はAは正整数でなければいけない.
 B を kA だけ減らす.ただし結果はBは正整数でなければいけない.
打つ手がなくなったら負け.
A1, A2, B1, B2が与えられるので,
 A ∈ [A1, A2]
 B ∈ [B1, B2]
なる先手必勝パターンの数を求める問題.
small: A1, A2, B1, B2は1000000以下,A2-A1, B2-B1は30以下
large: A1, A2, B1, B2は1000000以下

えーっと…,規則を見つけるゲーム?
とりあえず,小さい場合の答えを列挙しよう.規則わからなければそれでsmallだけサブミットしてもいいし.
A, Bが与えられたとき,先手必勝か後手必勝かを判定するには…
 大きい方が小さい方の2倍以上なら,kを何を選ぶかの選択権があるので,必勝
 そうでなければ,減らし方は1通りしかないのでシミュレーションする
さて,規則は見えるかな….
あからさまに,見えるなぁw
Aを固定したとき,必勝パターンでないのはBがある区間に入っているとき.
この区間の最大値の値って,たぶん(1+sqrt(5))/2ずつ増えてるんだよね…? 確かめる.うん,たぶんそう.
よし,書こう.
書いた.small correct.largeサブミット.

Result

あれ,B落ちた….
> まぁ,数字付け加えるのは,次の値に近くなるように付け加えるんじゃなければ無意味なので
これ嘘じゃない? (これつけててもLarge通ったのでよくわからないけど)
てか,前回使った数字も書き換え直してるし,そんなことやっちゃ駄目じゃん.
もうめちゃくちゃ….

SRM470 DIV1 参加記録 (この記事を編集する[管理者用])

2010年05月21日00時02分から.

Assignment

普通っぽい部屋.

EASY

2人でゲームをする.
一列に連なった部屋の間に鍵のかかったドアがある.
最初,それぞれのプレイヤーは両端にいて,ある部屋を目指す.
鍵は16種類以下で,順番にどの種類の鍵を解除するかを指定していく.指定された鍵のドアは全部開く.
勝てるなら最小ターンで,負けるなら最大ターンで負けるようにする.
勝敗とターン数を求める問題.

え,どうみてもビットDP….
EASYだよね,重くないか?
自分だけが開けないといけない鍵の種類,相手だけが開けないといけない鍵の種類,両方が開けないといけない鍵の種類数から場合分けすれば求まりそう?
いや,なんか場合分け面倒そうだし,TopCoderで場合分けしたときはシステムで落ちるのが怖い.
それにDPならサクっと書けばそっちの方が早いに違いない!
DP書く.
はまった.
答えが合わない.
何がおかしいのか…?
最適の比較(勝敗と最小ターン数)って比較間違ってないか?
合ってる…?合ってない?あれ,なんかよくわからなくなってきた….
合ってない!
あー,結構比較面倒,比較用の関数作っちゃえ.
あわない,無限大が返ってくる….
最悪の場合は1ターンで負ける場合だよ,無限大ターンで負ける場合じゃない,初期値間違ってた.
ようやくサンプル合った….
サブミット.
…,40分かかってる.
おわた….
(Hard放棄~Intermission中に考えれば,場合分けしても全然面倒じゃない)
(てか,思ったよりコーナーケースみたいなのがない)
(明らかに方針間違えたなぁ)

MEDIUM

上辺と下辺にn個の点をとり,それぞれ左から1~nの番号をつける.
最終的に,n本の線を書く.
すでに,50本以下,点を結ぶ線を書いている.
あとは,ランダムに書くとき,交わる線の組の数の期待値を求める問題.
nは10000以下.

EASYに40分費やしたのに,部屋の誰もMediumサブミットしてない.
これは,解けない問題の予感.
問題読む.
確率!
期待値なんだから線形性バンザイ問題っぽい.
既に交わってるの(A),もう引いてるのと交わるの(B),新しく引くの同士で交わるの(C),別々に考える.
 A → 調べるだけ
 B → 新しく1本付け加えたときに,交わるパターン数 / 全部のパターン数 * 付け加える本数…だよね?
 C → それぞれの線分同士が交わる確率は1/2
てか,簡単じゃね?
がりがり.
書いた.合った.サブミット.10分.

HARD

50*50のマップのところどころに岩がある.
岩のあるますは道路が引けない.
それぞれの岩を壊すコストは異なる.
ある場所からある場所へ道路を引きたいというのが最大で4つ与えられる.
すべての道路を引けるようにするために壊す岩のコストの最小値を求める問題.

最小費用流…?
いや,違うか?
1個目の流れにはコストがかかるけど,2個目以降はコストがかからない.
どうするんだろう…?
てか,これも簡単そうな気もするけど,思いつかんなー.
と思ったら,誰もサブミットしてないな,簡単じゃないのかな?
てか,時間ねぇ…,EASYに40分とか使ってるからだよ.
諦めよう.

Challenge

のんびりまったり,いつも通りコード眺めてるだけ.

System tests

250と500は通る.
250が致命的に駄目だったけど,500が早く解けてちょっと救われた感じ.
(でも,若い強い人のスコア見てると,これでも早くなさそうだ…)
Hardは結局誰も解けなかったみたい.やっぱり難しいのか….

Marathon Match 60 - PolymerPacking (参加記録) (この記事を編集する[管理者用])

2010年05月06日02時から,2週間.

Source

Problem Statement
standings

問題概要

長さL (100以上500以下)の折れ線が与えられる.
折れ線は自分と交差せずに,曲がるときは整数座標上で90度だけ曲がる.
ある点を軸に,そこから先を反転させるという操作をL/8回以下やることができる.
その操作の途中で,折れ線が自分と重なってはいけない.
最終的な,折れ線を囲むバウンディングボックス(ただしx座標y座標に並行な長方形)の面積を最小化する問題.

自分の解法

・制限時間のうち最初の2/3ぐらいは以下を繰り返す
ランダムに反転作業L/8回をやる.
ただし,反転させれる場所を全部反転させて,暫定的な答えが良いものを採用しやすくしておく.

・制限時間のうち最後の1/3ぐらいは以下を繰り返す 今まで見つかった良さそうな解から,2箇所選んで反転作業をやってよくなるならそれを採用する局所探索.

その他の工夫は,その反転がvalidか,バウンディングボックスの面積はいくらか,というのは,O(L)で計算できるようにしておく.
また,一度計算したものはhashに突っ込んでおいて,それを利用する.(効果があるか微妙)

自分の提出コードは記事の最後に載せています.

最後のExample submissionの結果

Example scores:
0) 0.6754385964912281
1) 0.5416666666666666
2) 0.5234375
3) 0.5959079283887468
4) 0.5404411764705882
5) 0.36583184257602863
6) 0.6306818181818182
7) 0.3472340425531915
8) 0.5769230769230769
9) 0.5573333333333333
参加記録

以下,時系列順のログです.

続きを読む

VIII Programming Olympiads in Murcia (この記事を編集する[管理者用])

2010年05月15日16時30分から5時間,8問.
[ Link ]

良く寝たはずなのに,なんかずっと参加中眠かった.
最初4時間のコンテストだったと思うんだけど,気づいたら5時間に延長されてた.
Fが通らない.なんでだろう….
F以外の7問解いた.

取り敢えずAから.
左右の最も高い座標を覚えておけば,自分の場所がどの位,水が溜まるかわかるよね.
Accept.
Bはやるだけ.Accept.
Eは重み付きLISみたいなの.
入力サイズ書いてないのが怪しいけどO(n^2)のDPしかないだろうし,それで通るよね?
n^2だから,入力は1000ぐらいまでだろう.
Wrong Answer.
うーん?誰もこの問題WAなんて食らってないのに,何をやらかしたんだ?
配列のサイズ1000から10000にして,取り敢えずもう1回送ってみよう.
Accept….うーん.入力サイズぐらい書いておいてよー.
Gはやるだけ実装問題.
重要な駅のみのノード数100のグラフに落として,ワーシャルフロイド.
Accept.
Cは幾何.
めんどい.てか,問題の意味が少しわからない.
ボールの半径って,ゴールの枠に当たったら入らないため?
違うな,長方形のエリアをボールの中心が通れば良い,みたいな事書いてる.
まぁ,地面から半径だけ浮いてるので,ゴールの高さをマイナス半径しておくだけか?
それでサンプル合うな.サブミット.Wrong Answer.
色々解釈変えたり,EPS追加してサブミットしてもWrong Answer.
Dはめんどい探索とポーカーの役判定.
書くだけ.書いた.
探索の順番を間違えてて1回WA.(全く同じ強さの手なら先に見つかったのを返すという制約)
てか,サンプル親切じゃん,サンプル通ってないじゃん.送るなよ.
直した.Accept.
Fは500^3で頑張ってみた.Wrong Answer.
BBS見たら,CのClarきてた.
入力は0 0 0で終わりますだと!
それだけ直したらAccept.
あれ,なんかコンテスト時間が1時間延びてる?
F通らないので,Hやる.
枝刈り探索かなーと思ってたけど,状態数って良く考えればΣ[k=0,1,2,3,4,5] C(25,5k)だよね,そんなに多くないのでは?
で,連結条件もあるから,結構いけるのでは?
DPで書いてみた.
n=5の最悪ケースで,1ケース当たり1秒ぐらいかかる….
てか,サンプル合わないんですが?
でも,これ,どう見ても,サンプル間違ってないか?問題の解釈間違ってるの?
これは…,まぁ,取り敢えず送ってみる.TLE.ですよねー.
うーん….
n=4だと一瞬何だよなあ.
てか,連結条件などから状態数は少なくなるはずなので,最初にDAGを作っておこう.
めんどいので,n=5のときだけ…,n=4以下のときは今までのルーチンを使う.
お,最初に1秒だけ前計算いるけど,n=5もほとんど一瞬で終わるじゃん.
てか,n=5でノード数17000ぐらいのグラフになった,意外と連結条件が厳しいんだ.状態数20000もないじゃないか.
Accept.
やっぱりサンプルは間違ってるらしい.(3つ目の答えは1じゃなくて-1)
残り1時間あるけど,F通らないし放棄ー.
コンテスト時間,1時間延ばしてくれなくて良かったのにw
しかし,Fは難しいと思えないし,全員WAで通らないって,…,って疑うのは良くないよね….

ぼやき (この記事を編集する[管理者用])

TopCoderニコ生Open 第1回のタイムシフト見たけど,やっぱり診断人先生とchokudai先生はエンターティナーだなぁと思った.

chokudai先生の連載の動的計画法・メモ化再帰チェックシートの1問目と3問目は実際プログラミングコンテストで出題されると,

1000兆円以下の金額が与えられる。日本の硬貨/紙幣で支払いをする時、支払う合計枚数の最小値を出力しなさい
コインを100万枚投げたとき、表になっている枚数が49.8万枚以下である確率を求めなさい

とかになったりするんだろうなぁ,とか思ってしまった.

LiveArchive 4741 - Kind of a Blur (この記事を編集する[管理者用])

Source

ACM/ICPC Africa and the Middle East - Africa and Arab (Alexandria, Egypt) - 2009/2010
LiveArchive 4741
SPOJ 7776 [ANARC09I] (2010-11-09 03:57追加)

問題概要

グレイスケールの画像があって,それをぼかした画像が与えられる.
ぼかすとは,各ピクセルの要素を,
 自分とマンハッタン距離d以下のピクセルの画素値の平均値
に変更する処理.
元の画像を復元する問題.答えは一意に求まることは保証されている.
画像サイズは10*10以下.

解法

連立一次方程式を解くのみ.
どっちか縦で横か,サンプルが正方形しか無いときはちゃんとチェックしましょう….(To: 自分)

LiveArchive 4740 - Land Division (この記事を編集する[管理者用])

Source

ACM/ICPC Africa and the Middle East - Africa and Arab (Alexandria, Egypt) - 2009/2010
LiveArchive 4740
SPOJ 7778 [ANARC09H] (2010-11-09 03:59追加)

問題概要

2次元平面上にN個の点がある.
真横にK-1回切るか,縦にK-1回切るかして,K個の領域に分ける.
 ∑ |それぞれの領域の点の数 - N/K|
の最小値を求める問題.
Nは100000以下,Kは10以下.

解法

縦に切るか横に切るか両方試して良い方を採用すれば良い.
切り方は,左から見て行って,その領域に含まれる点がN/Kを超える場所の前後の2パターンのみ試せば良いので,2^Kぐらいしか切り方を試さなくて良い.

LiveArchive 4739 - Stock Chase (この記事を編集する[管理者用])

Source

ACM/ICPC Africa and the Middle East - Africa and Arab (Alexandria, Egypt) - 2009/2010
LiveArchive 4739
SPOJ 7779 [ANARC09G] (2010-11-09 04:02追加)

問題概要

頂点数N (Nは234未満)の有向グラフを考える.最初は枝はない.
T回だけ以下の操作を繰り返す.(Tは100000以下)
 枝A→Bを加えて,ループができないならその枝を加える.
枝を付け加えられなかった回数を求める問題.

解法

DFS使って,B→Aに辿り着けないなら加えるってのを繰り返す.

LiveArchive 4737 - Hop --- Don't Walk! (この記事を編集する[管理者用])

Source

ACM/ICPC Africa and the Middle East - Africa and Arab (Alexandria, Egypt) - 2009/2010
LiveArchive 4737
SPOJ 5452 [ANARC09D] (問題名: Hop Do not Walk)

問題概要

WBFからなる100文字以下の文字列が与えられる.Fは厳密に1回のみ現れる.
1ターンでできる行動は,
 Fとその隣の文字を入れ替える
 Fとその左右2マス目にある文字を入れ替えて,Fじゃない方の文字をWB反転させる
さて,どのWもBの間にない状態にするのに必要な最小手数を求める問題.
WWBFWWBBも後ろ2つのWWがBに囲まれているので駄目.
10手以下で達成できないなら,それを指摘する.

解法

DFSしてみた.
戻る行動は考えなくて良いので,だいたい計算量はO(3^10).

LiveArchive 4736 - Probability One (この記事を編集する[管理者用])

Source

ACM/ICPC Africa and the Middle East - Africa and Arab (Alexandria, Egypt) - 2009/2010
LiveArchive 4736

問題概要

正整数nが与えられたときに,ある手順によって計算して,n1, n2, n3, n4を作る.
n1が偶数ならn=n4*2,n1が奇数ならn=n4*2+1が成り立つ.
さて,nが与えられたときに,n1の偶奇とn4の値を求める問題.

解法

やるだけ.

LiveArchive 4735 - Not So Flat After All (この記事を編集する[管理者用])

Source

ACM/ICPC Africa and the Middle East - Africa and Arab (Alexandria, Egypt) - 2009/2010
LiveArchive 4735
SPOJ 5451 [ANARC09C]

問題概要

1000000以下の正整数AとBが与えられる.
Aは(p2,p3,p5,p7,...)にプロットする.ここでpkはAが持っている素因数kの数.A=2^p2*3^p3*….
Bも同様.ただし,座標軸はAもBも持っていない素数の軸は省略することにする.
AとBのマンハッタン距離と,軸の数を求める問題.

解法

素因数分解するだけ.

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。