Entries

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

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

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

2010年10月26日00時から2時間,5問.codeforces format.
[ Link ]

A. Towers

1~1000までの数字が1000個以下与えられる.
何種類の数字が与えられたか,最も多く与えられた数字は何個与えられたかを求める問題.

問題文が読みにくい.
理解.
書くだけ.
サブミット.pretest passed.

C. Old Berland Language

要素数N(1000以下)の整数列len[i]が与えられる.len[i]は1以上1000以下.
01からなるlen[k]文字の文字列(k=0,1,...,N-1)を1つ求める問題.
ただし,文字列の組を取ってきたとき,片方が片方のprefixになっていてはいけない.
不可能ならそれを指摘する.

Bの問題文がわからないので先にこっち.
適当にtrieみたいなtreeを作って,dfsでまだ使ってない長さlen[i]のノードにたどり着いたらそれを使うだけ.greedy.
…,でいいんだよな?
ちょっと試す.
良さそう.
書く.
サンプル通る.色々テストする.Runtime Error.
あ,1箇所チェック抜けてた.求めたい文字列の長さにかかわらず,どんどん木の深くに迷いこんでいく….
修正.
大丈夫そうかな?
サブミット.pretest passed.

B. Computer Game

敵を倒す最小ターンとそれを達成する巻物の使用方法を求める問題.倒せないならそれを指摘する.
敵の最大HPと,毎ターン回復する敵のHPと巻物の情報が与えられる.
各巻物は,敵がどのぐらい弱ってないと使えないか(敵のHPがpow%以下で使える),使うと毎ターンいくつのダメージを与え続けれるかが与えられる.
各,巻物は1回使うとなくなり,1ターンに1個までしか使えない.
ターンの行動は以下のとおり (問題文は間違っているので注意)
 過去使った巻物で敵にダメージが入る
 敵が回復する (最大HPを超えない)
 敵の死亡判定
 使う巻物を選ぶ (使わなくても良い)
巻物は敵が死んだ後に使ってはいけない.

Dの問題文もわからなかったので,頑張ってBを読む.
わかった.やるだけっぽい.使える巻物の中で最もダメージの大きいものから使えばよい.
書く.
書いた.
時間が1だけずれる….
死亡判定って,回復した後か!一時的にHPがマイナスになっても回復してプラスになると生きてる.
死亡判定をターンの最後にしよう.
サブミット.WA.
あれ.
アウトプットに巻物1は最初のターンに使えるようにpowが100だよって書いてある.
もしかして,最初のターンは巻物1を使わなければならないのでは?
WA.
わからん….
試しに,死亡判定を巻物選ぶ前にしてみる.
pretest passed.え….

D. Lesson Timetable

2つの数列XとYが与えられる.要素数は同じで要素数は100以下.
Y[i]はX[i]以上で,Y[i]は100以下.X[i]は非負.
sum = ΣX[k]として,sum個の数字のペア{a[k],b[k]} (b[k]はa[k]以上, k=0,1,...,sum-1)のうち,以下を満たすものの個数をmod 1000000007で求める問題.
 n=a[k]となる個数はちょうどX[n]個
 n=b[k]となる個数はY[n]個以下
sumは1000以下.

問題文読むのに手こずる.
単なるDPな気がする.
書く.
あれ…,これ計算量大丈夫か?結構怪しい気がする.(sumは1000以下を読み飛ばしている)
まぁ,これ以外に解法ないだろうし,とりあえず書いてみる.
うまく書けばオーダー落とせるのかもしれないけど,検算用になるし.
書いた.
最大ケースで3秒.
うーん,コンビネーションを階乗から計算するんじゃなくて覚えておこう.よく考えればメモリ足りてるし.
最大ケースで1秒ちょっと.
向こうのサーバーでは怪しい.
枝刈ると,オーダーは変わらないけど,理論上2倍ぐらいは早くなりそうな気がする.
最悪ケースがよくわからなくなるから時間試せないけど,きっと間に合う.
枝刈って.サブミット.

E. Trial for Chief

50*50以下の白黒ビットマップ画像が与えられる.
ペイントの塗りつぶしツールを何回使えば真っ白な画像にできるか,最小値を求める問題.

とりあえずDやる前に問題読んだけど,わからないのでDやって,それが終わったら時間なかったので考えてない.
でも同じような問題見たことあるような….PKUか何かで…?

Hack

Bがループたりてなかったり,敵のHP削れないとすぐ抜け出している人がいて,敵のHPが100%の時に使える巻物が複数ある場合を叩き込む.
3成功2失敗.

Result

提出したのは全部通った.

Anupam Bhattacharjee Memorial Contest (この記事を編集する[管理者用])

2010年10月24日23時から5時間,9問.
[ Link ]

ケアレスミスが多かった気がする.8問解いた.
以下問題別.

・問題B
構文解析・文字列処理.実装あるのみ.
・問題C
同じグループはunion findで固めて,違うグループに枝を張って,2色彩色できるかどうか調べた.
・問題D
有名問題?ライブラリコピー.
・問題E
単なるビットDP.最初全ての場所に行けるように動くってのを見落としてた.
・問題F
頑張って計算する.
1箇所対称性とか使っても角度がわからない場所があって,そこは
 sin A - cos A = ほげほげ
みたいな方程式をたてて解いた.
・問題G
ベルマンフォードで負閉路検出.
・問題H
真ん中出すだけ.
・問題I
最初に数列作ってしまって,各クエリごとに2分探索して範囲を求めた.

ACM ICPC Latin America Regional Contest (この記事を編集する[管理者用])

2010年10月24日04時から5時間,11問.
[ Link ]

よくある系の問題が幾つか見られたけど,まずまずバランスの良いセットだと思う.
10問解いた.
以下問題別.

・問題A
問題の入力形式から,深い方を浅く移動して,一致したところで終了してください,って書いてあるような気がしたのでそうした.
・問題B
やるだけ.全部の差を調べる.
・問題C
思いのほか梃子摺った.
内接する四角形の向かい合う角の和は180度なのを利用して,2つの点を選んで,残りの点の角度をそれぞれ求めて,同じ物の数が最も多くなるようにする.
最初はO(n^4)で愚直にやってTLEもらってた.(定数が小さいので行けるかと思ったけど全然無理でした)
・問題D
よくある系の問題.
桁ごとに調べる.
・問題F
やるだけ.
・問題G
Rolling hash使って,自分より短い文字列に対して含んでいるか判定してTLEをもらった.
Aho-Corasick使ってAC.
・問題H
1回前と2回前を記録するDP.
・問題I
1回で移動できるか,2つの差の2倍だけ移動できるので,そのGCD倍にゴールがあるかどうか判定.
・問題J
すべてのカード全部一応調べた.そして勝てるかどうかもnext_permutationで全部調べてみた.
本当は,それぞれのカードより1だけ大きいものだけ,勝てるかどうかもgreedyでいいのだろうけど.
・問題K
連結成分に分けて次数を調べる.全部ではなく,サイクルが存在したり,次数が3以上のものが存在したりするとダメとか,Adhocに判定.

JAPLJ Contest (この記事を編集する[管理者用])

2010年10月24日13時から3時間,6問.(夜の部は22時から3時間)
[ Link ] [ 夜の部 ]

全然できなかった.難しい.3問解いた.
以下問題別.

・問題A
最初は問題の意味がわからなかった.
意味をなんとなく理解してから適当に書く.
図が2倍2倍にとんがっていくのはすぐわかった.てか見たことある関数.
ってことで書く.
q=0ってどうなるんだ….適当にn=1,t=100とかにしとけばいいか.
いや,nの最小値って1でいいのか?問題文の定義の仕方だとn=0は定義されてないから1で良い気がする.
送る.Accept.
後で気づいたけど,入力が2^n+1の時って答え間違える(-1を返す)んだけど,まぁ,通ってるので触らないことにしておく.
・問題B
どうみても,根から高さを求めるだけ.
トポロジカルソートみたいに書く.
トポロジカルソート知らないとか情報系失格とか聞いたけど,普通にそんなの知ったのごく最近ですよ….
まぁ,これは普通にAccept.
・問題C
うーん,サイズ的にDPだと間に合わない.
紙に書いて適当にやると普通にgreedyで良さそう.
これって答えないことあるのか?なさそうなんだけど….うん,多分ない.
スタックに使われてないのを積んで,スタックに入ってるのと違う色と出くわしたら結ぶ.そうでなければ積む.
Accept.
・問題D
縦横mod dで分けて考えると,毎回,ある区間だけ同じ数字を減らしていくことになる.
2d Fenwick Treeでも使えばできるのかなーと思ったけど結局分からず.
・問題Eと問題F
ほとんど考えてない.

SPOJ 7567 - Divisor Summation Powered [IITD4] (この記事を編集する[管理者用])

Source

IIT Delhi ACM ICPC provinical contest 2010
SPOJ 7567 [IITD4]

問題概要

F(n,k)をnの約数のk乗の和,G(a,b,k)をF(a,k)+F(a+1,k)+…F(b,k)とする.
G(a,b,k) mod 1000000007を求める問題.
a, b, kは100000以下.

解法

G(a,b,k) = Σ[p=1..b] a~bまでのうちでpを約数に持つ物の数 * p^k
a~bまでのうちでpを約数に持つ物の数が0だとp^kを計算しない,としなければTLEだった.

SPOJ 7566 - Expected Cycle Sums [IITD5] (この記事を編集する[管理者用])

Source

IIT Delhi ACM ICPC provinical contest 2010
SPOJ 7566 [IITD5]

問題概要

1~Nの置換Pが与えられたとき,ノードiからノードP[i]に枝をはることでいくつかの閉路ができる.
ノードkが含まれる閉路に含まれるノードxに対してS[x]の和をsum[k]とする.
互いに異なる非負整数S[x]が与えられたとき,sum[k]の平均値の最小値を達成するkでのsum[k]の平均値を求める問題.
全ての置換は同じ確率で選ばれる.
Nは5000以下.

解法

サイズ3や4の置換を紙に書いて確かめてみると,
 kは必ず含まれる
 それ以外は確率1/2で含まれる
ということがわかるので,(S[k]最小値 + ΣS[k])の半分が答えになる.

SPOJ 7565 - Another Sorting Algorithm [IITD1] (この記事を編集する[管理者用])

Source

IIT Delhi ACM ICPC provinical contest 2010
SPOJ 7565 [IITD1]

問題概要

与えられた4000要素以下の整数列を,問題文に書かれているアルゴリズムでソートしたとき,swapが呼ばれる回数を求める問題.

解法

reverseがO(1)でできれば合計でO(N^2)時間となり間に合う.
双方向リストを使えばreverseはO(1)でできる.
双方向リストは,reverseしたら前後がどっちかどっちかわからなくなるので,前の要素と違う方に進んでいく形.
後半のjのループは,最終的な形は規則性が見えるので,それを利用して,わざわざreverseしないなどの定数倍高速化が必要な感じ.(タイムリミットが結構厳しい)

SPOJ 7425 - Hackers [HACKERS] (この記事を編集する[管理者用])

Source

FCEyN UBA ICPC Selection 2010
SPOJ 7425 [HACKERS]

問題概要

ノード数3000以下,枝数100000以下の無向グラフが与えられる.
クエリが100000個以下与えられるので,そのクエリに答える問題.
各クエリに対して,あるノードからあるノードに移動するのに通る,最大の枝の重みの最小値を求める.

解法

クラスカルのようにunion findを使って解く.
全てのクエリを同時にやるため,全ての節点対に対して答えを求める.
新しく繋げるとき,その時繋がるペアを全部考えれば良い.
アッカーマン逆関数を無視すると計算時間量はO(枝 log 枝 + ノード^2 + クエリ).

SPOJ 7424 - Girls and Boys [GIRLSNBS] (この記事を編集する[管理者用])

Source

FCEyN UBA ICPC Selection 2010
SPOJ 7424 [GIRLSNBS]

問題概要

男がB人,女がG人いる.
1列に並んだとき,連続して男が出現する数,連続して女が出現する数の最大値の最小値を求める問題.
BとGは1000以下.

解法

例えばGが小さいとして,BをG+1個に分割したとき,最大のサイズのBが答え.割り算で求まる.

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

Source

TopCoder SRM485 DIV2 EASY (250pt)
Problem Statement
SRM485 DIV1 自分の参加記録

問題概要

a以上b以下の整数で末尾に9ができるだけ長く続く数字を求める問題.
同じだけ続くなら,その中で最も大きい物を求める問題.
aとbは1以上1000000以下.

解法

やるだけ.
ただし,DIV2 EASYにしてはサンプルが弱く,例えば9の個数を全部数えてしまうプログラムでもサンプルが通るので注意.
(普段はDIV2 EASYは想定される間違いはサンプルで全部落ちるようになってる気がする)

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

続きを読む

SRM485 DIV1 MEDIUM RectangleAvoidingColoring / DIV2 HARD - RectangleAvoidingColoringEasy (この記事を編集する[管理者用])

Source

TopCoder SRM485 DIV1 MEDIUM (500pt)
TopCoder SRM485 DIV2 HARD (1000pt)
Problem Statement (DIV1)
Problem Statement (DIV2)
SRM485 DIV1 自分の参加記録

問題概要

r*cのグリッドを白か黒に色を塗る.
すでに塗られているマスと塗られていないマスが与えられたとき,validの塗り方が何通りあるか求める問題.
validな塗り方は,a != b, c != dで
 board[a][c], board[a][d], board[b][c], board[b][d]
が全部同じ色ではないこと.
DIV1ではrとcは50以下.
DIV2ではrとcは10以下.

解法

取り敢えず,DIV1用の解法を記す.
rとcがある程度大きいと解が存在しないことがわかる.
具体的に試してみると,rがc以下とすると
 r=3~4の場合は,cが7以上から解なし
 r=5以上の場合は解なし
であることがわかる.
ただし,rが2以下の場合はたくさん解がある.
rが1の場合は,2^?の数 が答えになり,rが2の場合は,WWとBBがたかだか1回使え,それ以外はWBかBWになれば良いからWWとBBを使う列を全パターン試して数え上げる.
rが3以上で解がある場合は,全探索してもすぐに終わる.
rが2以下も場合分けせず,rが4以下であることに着目して,DPする方法もある.
DPは白,黒,ともに考えてる列より前に,使ったパターンをビットに押し込んで記録しておく.(使ったパターンは2つ組のみに落としこんで考えれば良い)
DIV2では,多分最初から全探索しても間に合いそう.

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

続きを読む

SRM485 DIV1 EASY/DIV2 MEDIUM - AfraidOfEven (この記事を編集する[管理者用])

Source

TopCoder SRM485 DIV1 EASY (250pt)
TopCoder SRM485 DIV2 MEDIUM (500pt)
Problem Statement
SRM485 DIV1 自分の参加記録

問題概要

1以上1000以下の奇数の正整数からなる数列が与えられる.要素の数は4以上50以下.
好きな要素に好きなだけ2をかけていいから,等差数列にしてくださいという問題.
複数答えがあるなら,辞書順最小のものを求める.

解法

解法は主に2つ.
解法1は,1個目の要素と2つ目の要素にそれぞれ適当な2の冪を掛けて全探索する.
3つ目の要素以降は,差が等しいことから一意に定まり,後はそれがvalidかどうか判定する.
解法2は,答えは全部偶数の数列にはならないことに着目する.なぜなら全部偶数なら2でわることで辞書順でもっと早いものが存在するから.
なので,1つ目と3つ目,または,2つ目か4つ目は元の数列に等しいはずで,それを利用して復元し,validかどうか判定する.
validかどうか判定するときに,偶数である限り2で割るとして,0を割り続けて無限ループにならないように注意する.
以下のコードは解法1.

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

続きを読む

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

2010年10月21日20時02分から.

Assignment

マラソンの覇者とSPOJの覇者と同じ部屋.
250-500-1000の標準セット.

EASY

1以上1000以下の奇数の正整数からなる数列が与えられる.要素の数は4以上50以下.
好きな要素に好きなだけ2をかけていいから,等差数列にしてくださいという問題.
複数答えがあるなら,辞書順最小のものを求める.

問題文長い!
と思ったらそんな感じでもなく,すんなり意味が理解できる.
1つ目の要素と2つ目の要素を全探索するだけで良いよね.
それぞれ適当に2^40まで掛けてみて,残りは等差数列ということから一意に定まるからvalidかどうか判定するのみ.
がりがり.
コンパイルー.
コンパイルできねー,反応返ってこねー.
もう1回.
できた.サブミット.

MEDIUM

50*50以下のグリッドを白か黒に色を塗る.
すでに塗られているマスと塗られていないマスが与えられたとき,validの塗り方が何通りあるか求める問題.
validな塗り方は,a != b, c != dで
 board[a][c], board[a][d], board[b][c], board[b][d]
が全部同じ色ではないこと.

50*50だと!?
長方形の中全部同じ色だと駄目なんだから,2*2の長方形だけ考えれば良いよね.(問題読み間違えてる)
うーん,わからん.
包除原理…できないなぁ.
うーん,うーん.
実は高さか幅の小さいほうが8以上だと答え0なんじゃないの?
だったらbit DPでいける.
証明は…できない.
問題をもう1回読んで考えよう.
あれ,これ条件違うんじゃない?
違うよ,問題読み間違えてるよ,制約もっと厳しいよ!
じゃ,尚更答えなさそうじゃん.
幅と高さの小さいほうが10より大きいと0を返して,後はbit DPする!
で,10*10の?を突っ込んで答えが0なら提出だ!
かきかき.
答え合わねー.
いや,違うじゃん,問題読み間違えてたんだよ,制約違うよ.
あれ…,bit DPできないじゃないか….
紙の上でいろいろ例を考える.
これ,高さと幅の小さいほうが3以上だとあんまり作れないんじゃ….
とりあえず,高さが1の時のコードと,高さが2の時のコードを書く.
1は自明.2の時は?
うーん….
幅が大きいと,WWをたかだか1回使えて,BBをたかだか1回使えて,残りはWBかBW.
WWを使う行,BBを使う行を全探索して足し合わせれば良さそう.
かきかき.
幅3以上は….
全探索のコードをとりあえず書く!
書いた,サンプルは全部通る.
さて,大きいのを突っ込んだら0になるかな?
なる!
高さ3だと幅7以上で0かな,高さ4でもだ.
高さ5だと,幅5以上で0.
高さの方が低いと最初に転置する.
てか,全探索すぐ終わるなー.
ちょっと余裕もっと大きめにしておこう.
サブミット.
いろいろテストする.
1x50の?…OK.
50x1の?…seg falut.え?
!!
1の時の処理が,転置したやつじゃなくて,引数をそのまま見てる!
何やってるんだ…,修正,リサブミット.
うげー,これでだいぶ順位下がったなぁ….

HARD

2つの凸多角形がある.1つはもう片方の内部に含まれている.
外側の多角形の辺上を1つランダムに選び,そこから直線距離で最も遠い外側の多角形の点に向かって線を引く.
最も遠い点が複数あるなら,ランダムに選ぶ.
その線が,中にある多角形と1点でも重なっている確率を求める問題.

残り10分でまさかの幾何.
あれ…,これ普通に解けそうじゃないか….
どうせ一番遠い点って頂点のどれかな気がするし….
でも,10分で実装は不可能….
諦めて,250, 500の見直しすべし.

Challenge

勘違いして2失敗.もう500提出組の中では底辺に近かったからあんまり気にしない.と思ったけどやっぱり痛い.

System tests

Systestは通る.でも完全敗北.
部屋内では,順当に,マラソン覇者とSPOJ覇者がワンツーフィニッシュ.

番外編: DIV2 EASY (診断人師匠のニコ生中)

末尾に9が続く数字は安く見えて魅力的な数字である.
a以上b以下の整数で末尾に9ができるだけ長く続く数字を求める問題.
同じだけ続くなら,その中で最も大きい物を求める問題.
aとbは1以上1000000以下.

サンプル見て意味理解.
書く.
脊髄反射で9が含まれる数全部数える.
提出.249.25点.システムテスト落ちた.
DIV2最下位からやり直したほうが良い….

SPOJ 7600 - Milk Trading [MLK] (この記事を編集する[管理者用])

Source

Egyptian Olympiad in Informatics (EOI) 2009, August 14 - 21, Cairo
SPOJ 7600 [MLK]

問題概要

1000000要素以下の-1000以上1000以下の数列が与えられる.
隣り合う2つのセルを選んで,片方を-1して片方を+1することができる.
全ての要素を0にするのにかかる必要最小手数を求める問題.
数列の和は0.
テストケースの数は24で,正解したテストケースの割合でスコアリングされる.

解法

a[i]を1引いて,a[i+1]を1足す回数は,a[0] + a[1] + … a[i]が負なら0回,正ならその回数だけ.
同様に,逆向きに移動する場合も求める.
答えは32bitに収まらないことと,入力がscanfだと微妙に間に合わないことに注意する.

Beta Round #36 D問題 - New Game with a Chess Piece (この記事を編集する[管理者用])

Source

Codeforces Beta Round #36 D問題
Problem description
Beta Round #36の自分の参加記録
SPOJ 7602 [CF36D] (2010-10-21 01:25追加)

問題概要

n*mのチェス盤の左上にコマがある.
2人でゲームを行う.順番にコマを動かしていき,行える行動がなくなったら負け.
出来る行動は,右に1マス動かすか,下に1マス動かすか,右下ななめにkマスだけ動かす.
先手必勝か後手必勝か判定する問題.
n,m,kは1以上10億以下.

解法

小さい時に全探索すると規則が見える.
ただし,k=1のときのみ例外的な形をしている.
規則が見えると,それが先手必勝になることの証明はできなくもないはず.

C言語のスパゲッティなコード

続きを読む

Beta Round #36 C問題 - Bowls (この記事を編集する[管理者用])

Source

Codeforces Beta Round #36 C問題
Problem description
Beta Round #36の自分の参加記録

問題概要

上辺が下辺より広い台形を積み重ねていく.
上辺は実態がなくて,下辺はある.
順番にn個 (3000以下) 積み重ねたときの高さを求める問題.

解法

下から順番に,どの高さにその図形が置かれるか計算していく.
それは,自分より下のものの上に直接おいた時の高さを全部求めて最大値を取ればいい.O(n^2).
下の図形と何処でつっかえるかで場合分けして求める.

C言語のスパゲッティなコード

続きを読む

Beta Round #36 B問題 - Fractal (この記事を編集する[管理者用])

Source

Codeforces Beta Round #36 B問題
Problem description
Beta Round #36の自分の参加記録

問題概要

問題文に与えられた規則通りに,与えられた図形を元に,1ステップで縦横n倍の図形をフラクタルっぽく作っていく問題.

解法

やるだけ.

C言語のスパゲッティなコード

続きを読む

Beta Round #36 A問題 - Extra-terrestrial Intelligence (この記事を編集する[管理者用])

Source

Codeforces Beta Round #36 A問題
Problem description
Beta Round #36の自分の参加記録

問題概要

100文字以下の0と1からなる文字列が与えられる.
1の文字が全部等間隔に並んでいるかどうかを判定する問題.

解法

やるだけ.

C言語のスパゲッティなコード

続きを読む

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

2010年10月19日19時から2時間,5問.codeforces format.
[ Link ]

A. Extra-terrestrial Intelligence

100文字以下の0と1からなる文字列が与えられる.
1の文字が全部等間隔に並んでいるかどうかを判定する問題.

まあ,やるだけ.
書く.今回は入力がファイルからなので気をつける.
提出.Presentation Error.えーーー.
どういうことだ….
入力ファイルがinput.txtなのにinputにしてた,出力も.txtがなかった….
これでPEになるのか.
提出.pretest passed.

C. Bowls

上辺が下辺より広い台形を積み重ねていく.
上辺は実態がなくて,下辺はある.
順番にn個 (3000以下) 積み重ねたときの高さを求める問題.

B問題が問題文表示されないので先にこっちをやる.
この図はZOJだったかどこかで見たことあるぞ….
下からどの高さになるか決めていって,下に積んであるのに重ねたとき,どの高さになるかってのの最大値を取ればいい.
O(n^2)…,nは3000だけど,間に合うか…,多分大丈夫だろう.
書く.
すっぽり入っちゃう場合や,入らず上に乗る場合とかをテストする.
大丈夫そう.
n=3000を突っ込む.0.2秒.いけそう.
サブミット.pretest passed.

B. Fractal

与えられた図形を元に,1ステップで縦横n倍の図形をフラクタルっぽく作っていく問題.

問題見れるようになってた.
どうみてもやるだけ.
簡単.
pretest passed.

D. New Game with a Chess Piece

n*mのチェス盤の左上にコマがある.
2人でゲームを行う.順番にコマを動かしていき,行える行動がなくなったら負け.
出来る行動は,右に1マス動かすか,下に1マス動かすか,右下ななめにkマスだけ動かす.
n,m,kは1以上10億以下.

わからん.簡単な規則でもあるのではないか?
k=2とk=3の答えをn,mが50以下の部分を出力してみる.
規則が見える.
書く.
提出.pretest passed.

E. Two paths

ノード数10000以下の無向グラフで,枝が10000個以下与えられる.
空でない2つのパスの組で,枝をちょうど1度ずつ使うものを求める問題.

うーん.
次数が奇数のものが4つ以下ならできそう.
いや,全部が連結じゃなくて,2つにわかれている場合は,それぞれで1つのパスを作らなきゃ.
うーん,どうやってパスを復元するのだろう….
これって,連結の時の方が難しい!
下手に復元すると,もう片方がパス作れなくなる.
結構,これ難しいのでは….
諦めた.

Hack

Cで,底辺を突き抜ける人を2つ落として2つ失敗.
Aで問題読み間違えてる人を2つ落とす….てか,こんなのでpretest通るんかい….

Result

CとDが落ちた.
Dはhos先生がDしかRockしてないのに,Hackで点数稼いでいる時点で怪しいと思うべきだった.k=1がコーナーケース.
Cは普通に場合分けを1つ忘れていた.すっぽりと中に入ってるのだけど,つっかえてる場合.

Aizu 0225 - Kobutanukitsuneko (この記事を編集する[管理者用])

Source

PC Koshien 2010予選 (パソコン甲子園2010予選)
Aizu 0225

問題概要

10000個以下アルファベット小文字からなる文字列が与えられる.
全部の単語を使ってしりとりして,最初の単語の先頭の文字が,最後の単語の最後の文字にできるかどうかを判定する問題.

解法

アルファベット26種類のノードをもつグラフに落として,次数(入次数-出次数)が0であること,枝があるノードは全部連結であることを調べればよい.

Aizu 0224 - Bicycle Diet (この記事を編集する[管理者用])

Source

PC Koshien 2010予選 (パソコン甲子園2010予選)
Aizu 0224

問題概要

ノード数108以下ぐらいで,枝数256以下の無向グラフが与えられる.枝には通ると消費されるカロリーが与えられる.
ケーキ屋さんが6個以下あり,ケーキ屋さんを通過すると,カロリーが増え,同じケーキ屋さんは2回以上通れないとする.
出発地点から目的地まで移動する最小消費カロリーを求める問題.

解法

それぞれのケーキ屋さんに訪れているかどうか,それぞれのノードを2^6個に分裂させてダイクストラする.

Aizu 0223 - Stray Twins (この記事を編集する[管理者用])

Source

PC Koshien 2010予選 (パソコン甲子園2010予選)
Aizu 0223

問題概要

50*50以下のグリッド上に2人いる.
片方が,右左上下に移動すると,もう片方は,左上下上に移動する.
ただし,片方だけがグリッドの外に出る場合と,壁にぶつかって移動できない場合は,片方のみその場に留まる.
2人が同じセルに移動するまでの最小時間を求める問題.
ただし,時間100以上かかる場合は,NAを出力する.

解法

2人の位置を状態にBFSする.

Aizu 0222 - Prime Quadruplet (この記事を編集する[管理者用])

Source

PC Koshien 2010予選 (パソコン甲子園2010予選)
Aizu 0222

問題概要

(a-8, a-6, a-2, a)が全部素数の時,四つ子素数といい,aを四つ子素数の大きさという.
13以上10000000以下の整数nが与えられるのでn以下で最大の四つ子素数の大きさを求める問題.

解法

最初に四つ子素数の大きさを全部求めてしまい,2分探索する.(四つ子素数は少ないので線形探索でも十分な気がする)

Aizu 0221 - FizzBuzz (この記事を編集する[管理者用])

Source

PC Koshien 2010予選 (パソコン甲子園2010予選)
Aizu 0221

問題概要

1から順番に数字を言っていくが,3の倍数ならFizz,5の倍数ならBuzz,両方の倍数ならFizzBuzzと言わなければいけないゲームを行う.
間違えた人から脱落していく.
参加人数と発言ログが与えられるので,最後まで残っている人の番号を求める問題.
また,最後の1人になったら,その後の発言には関わらず,その人は生き残る.

解法

シミュレーションするだけ.

Aizu 0220 - Binary Digit A Doctor Loved (この記事を編集する[管理者用])

Source

PC Koshien 2010予選 (パソコン甲子園2010予選)
Aizu 0220

問題概要

整数部8桁以下,小数部4桁以下の実数が与えられるので,小数点以上8桁,以下4桁の2進数に直す問題.
不可能なら(桁が足りないなら)NAと出力する.

解法

整数部と小数部に分けてやるだけ.
丸め誤差が怖いが,double使えば分けずにできるかも.

Aizu 0219 - A Popular Ice-cream Shop (この記事を編集する[管理者用])

Source

PC Koshien 2010予選 (パソコン甲子園2010予選)
Aizu 0219

問題概要

10種類のアイスクリームの販売履歴が与えられるので,販売個数のヒストグラムを出力する問題.

解法

やるだけ.

Aizu 0218 - Dividing Students (この記事を編集する[管理者用])

Source

PC Koshien 2010予選 (パソコン甲子園2010予選)
Aizu 0218

問題概要

3科目の試験結果に基づいてAクラス,Bクラス,Cクラスに分ける.
分け方は問題文に与えられている.
試験結果が与えられたとき,どのクラスに属するか求める問題.

解法

やるだけ.

Aizu 0217 - Walking in the Hospital (この記事を編集する[管理者用])

Source

PC Koshien 2010予選 (パソコン甲子園2010予選)
Aizu 0217

問題概要

1日2回ウォーキングを行う.
 人番号,1回目の歩いた距離,2回目の歩いた距離
が与えられるので,最も長く歩いた人の人番号と歩いた合計距離を求める問題.
答えは一意に定まる.人の数は10000以下.

解法

やるだけ.

Aizu 0216 - Cutting Down Water Bills (この記事を編集する[管理者用])

Source

PC Koshien 2010予選 (パソコン甲子園2010予選)
Aizu 0216

問題概要

水道料金を計算方法が書かれている.
10m^3までは基本料金で,その後段階的に単位水量あたりの価格が変わっていく.
今月使った水量が与えられるので,先月との今月との差額を出力する問題.
先月の水道料金は4280.

解法

やるだけ.

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

Source

TopCoder SRM319 DIV1 HARD (1000pt)
Problem Statement

問題概要

2次元平面上の250000個以下の点が与えられるので,マンハッタン距離で最も離れている点の組を見つける問題.
複数あるなら辞書順で最小のものを求める.

解法

x[i]-y[i]の値でソートした時の最小値と最大値の組,もしくは
x[i]+y[i]の値でソートした時の最小値と最大値の組,が最も離れている組.

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

続きを読む

Appendix

Recent Articles

ブログ内検索

Ads


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