検索

Google
Web www.icefree.org

RSS of recent changes

  
Top / ソフトウェア / プログラミング / GoogleCodeJam2008 / 問題

問題

2017-06-20 (火) 23:23:54 (2995d)

コンテスト自体については、
ソフトウェア/プログラミング/GoogleCodeJam2008
に書いています。

問題文については解けるレベルでは書いていません。
問題文自体は、公式サイトを参照してください。

詳細な解説も、しばらく待っていると公式サイトに載るようです。
画面左側の柱の問題選択とQuestions asked の間に「Contest Analysis」と出るので、それです。今のところ1Aまで（8/9)。

一般知識 †

TopCoder?とか、ICPCとか（ICPCは詳しく知らない）、もちろんGoogleCodeJam?とかでも必要になる知らないと困る一般知識に関して。

私は一般知識に欠けていて、とても解説できるレベルにないので、ネットで学べるリソースだけ挙げておきます。

DynamicProgramming?に関しては、前述のTopCoder?のDPの解説と、前原さんの実際の実装例を見ると分かりやすいと思います。

数学問題は、基礎力と少しのひらめきが必要。本気の難題が出ると誰も解けません。
幾何、整数論あたりが第一でしょうか。
解析は微積分程度で十分？
複素数はほとんど使わないような気がします。

↑

Qualificationラウンド †

↑

Saving the Universe †

使用できるいくつかのサーチエンジンの名前と、いくつかのクエリーが渡されます。
両方とも文字列です。
・クエリーは順番に処理する
・サーチエンジンとクエリーが同じ文字列ではいけない
この条件で、サーチエンジンの切り替えの回数を最小にします。

クエリーを順番に見ていって、全種類のサーチエンジンが出揃った時点が
切り替えを行わなければならない地点で、これが最小の方法の１つになります。
切り替えたら、最後に使ったサーチエンジンから、再び同じ処理をします。

C++だとSTLのsetを使えば簡単です。エラー処理が要らないので
サーチエンジンのリストすら覚えておく必要がありません（個数は必要）。

↑

Train Timetable †

二駅間を運転している列車ダイアが渡されます。
そこで、使用する車両数の最小を求めます。

グラフを作って求めてもいいのですが、もっと簡単に、時間軸で順に状態を追っていけば解けます。

↑

Fly Swatter †

ラケットでハエを打ち落とせる確率を求めます。
ハエの大きさと、ラケットの寸法が渡されます。

円の中に縦横に張られたストリング（ガット）の面積を求めればほぼ終わりです。
計算自体は単純な積分ですが、交差するのでちょっと面倒です。
ちなみに、モンテカルロは単純に使うと時間的に厳しそうです。

ラケットを1/4に切って（45度で対称になっているので、90度で切っても問題ありません）、
半径を1に正規化すると（しなくても良いですが、行うと途中の計算で変数が１個減ります）
y = sqrt(1 - x*x)
になって、積分すると
x * sqrt(1 - x*x) / 2 + asin(x) / 2
で、場合分けを頑張ると解けます。
空白の部分を求める方が若干楽かも。
格子状に現れる空白に対して、
・すべて範囲外
・すべて範囲内
・一部が切り取られる
で判定して計算すれば良いです。

計算はdoubleで行います。途中でfloatを使うと誤差が問題になるでしょう。
丸めずに長い桁で出しても大丈夫ですが、問題と同じ表示にするなら、最後に6桁に丸めます。

↑

Round1A †

↑

Minimum Scalar Product †

問題
n次のベクトルが２つ渡されます。
各ベクトル内の要素を好きに並べ替えて、内積が最小になるようにします。

解答例
各ベクトルをソートして、片方の一番小さいものと残りの一番大きいもの、次に小さいもの次に大きいもの・・・と掛けていけば最少になります。

↑

Milkshakes †

問題はややこしいのですが、がんばって要約すると、
問題
Ｎ個のフレーバーのミルクシェイクを売っています。
フレーバー毎に麦芽入りと無しのいずれかが用意できます（途中で変更不可）。

客には、好みのフレーバー（麦芽ありなしを含む）がいくつかあります（１個以上）。
麦芽入りのものは高々１個です。
好みのフレーバーのうちの１つを販売します。

用意する麦芽入りのフレーバーはなるべく少なくします。
すべての人に販売できるような麦芽を入れるパターンを見つけます。
不可能な場合はIMPOSSIBLEを返します。
解答例
という感じです。
ややこしいけど、麦芽入りしか提供できないものから取っていけば答えが出ます。

↑

Numbers †

問題
(3+√5)^n
の整数部の下３桁を返します。
解答例
(3+√5)^n を展開すると、P + Q√5と書け、
P_n = 6P_{n-1} - 4P_{n-2}
になります。

Q√5がどうにも邪魔なので、
(3+√5)^n + (3-√5)^n
とします。展開すると、
P + Q√5 + (P - Q√5)
で、
2P
になります。

これでは、求めるものよりH = (3-√5)^n多いので、
これをひきます。3-√5 = 0.7639... なので、0<H<1です。
Pは整数なので、かならず整数部が1減って少数部が登場します。
したがって、求める答えは2P-1になります。

Pは、計算途中で剰余をとっても問題ないので、intで十分計算できます。
さらに、3桁だけ残すと、周期100で循環します。

余談
P/Q は√5に収束します。 そのときの誤差がHです。

↑

Round1B †

↑

Crop Triangles †

問題
ストーリー的な解説がありますが、要約すると

n, A, B, C, D, x0, y0, M

が整数で渡されて、

X = x0, Y = y0
print X, Y
for i = 1 to n-1
 X = (A * X + B) mod M
 Y = (C * Y + D) mod M
 print X, Y

で座標が作られます。
その座標を頂点とし、重心の座標が整数になるものの数を数えます。

面積０の三角形も有効です。

解答例
小さいセットは総当りで解けます。
大きいセットは総当りだと時間がかかりすぎるので、
座標を３の剰余でグループ化して、３の倍数になるパターンを計算します。

↑

Number Sets †

問題
AからBまでの整数があります。
まず、すべて自分自身のみの値があるグループに分けます。
２つのグループの要素について、P以上の共通の素因数を持つものを含む場合には、二つのグループを統合します。
最終的なグループ数を求めます。

解答例
大セットの場合、
A,B <= 10^12
A+B <= 1000000
なので、適当に解くと時間がかかりすぎます。

素数毎に共通化してまわります。

↑

Mousetrap †

問題
1〜Kまでのカードが重ねてあります。
上からめくっていって、ｘ枚めくったときのカードの数値がｘだったら
そのカードを取り除いて、カウントを０に戻します。
取り除けないときは、一番下に戻します。

数字が小さいカードから順に取り除いていける並びを作ります。

Input/Outputがやや特殊で、
できた並びの先頭からd_i番目（１から）にあるカードの値（k_i)を返します。

大セットの場合で、Kは最大1000000です。

解答例

１から順に配置していき、作り終えてから回答すべき場所の情報を返すことになります。

いかに先頭からｎ番目の空き領域を高速に探すか、というところにかかってきます。
先頭からいくつ空白があるかというカウントの処理は、順番が前後しますが、Round1C:Increasing Speed Limitsの後半と同じです。

↑

Round1C †

↑

Text Messaging Outrage †

問題
携帯電話のように、K個のキーがあり、キーを何回か押すことで違う文字を入力できるデバイスがあります。１つのキーに割り当てられる文字数は最大P個です。

K,Pと、割り当てるべき文字の総数L、そして入力する文字の出現頻度が全文字（L)に対して渡されます。その場合に、キーを押す回数が最小となる配列にしたとして、その押す回数を求めます。

キーへの文字の割り当ては連続である必要はありません。

解答例
出現頻度でソートして割り当てれば求まります。

↑

Ugly Numbers †

問題
１桁の素数(2,3,5,7)で割り切れるものを醜い数とします。
０は醜い数で、１は醜くない数です。負数の場合は、絶対値をとった正数と同じです。

数字の列が渡されます。先頭から続く０にも意味があります。
数字の間に、何も入れない、+を入れる、-を入れるの３種類のいずれかを行います。全部で3^(文字数-1)の組み合わせがありますが、計算した答えが、醜い数になる組み合わせの数を返します。

大セットの場合で、文字数は最大40文字です。

解答例

ある位置（+,-記号の区切り位置）で、そこまでの計算結果cに対してc%2,c%3,c%5,c%7の４つが完全に一致していれば、残りの結果は同じになります。
これを使って、適当に解きます。再帰でもいいし、片っ端から作っていってもＯＫです。

↑

Increasing Speed Limits †

問題
数列（非負の整数）が与えられたとき、順序は入れ替えずに適当に抜き出して上昇列になるような抜き出し方の個数を返す。

数列の中身は最大10^9で、個数は500,000個まであります。
抜き出した数列は空ではいけません。
答えはすごく大きくなるので、1,000,000,007の剰余で返します。

解答例
数が多いので、O(n^2)でも耐えられません。
グラフを使って解く方法もあるようですが、使わない場合だと、

基本方針としては、元の数列の位置 x で終わる組み合わせの数を集めていきます。

解きやすいように、値の昇順を第一で、元の位置の降順を第二にソートします。ソートしたあとの配列の値は、元の位置にします。これで、元の位置だけで上昇列の判別ができます。

位置xのときには、位置x-1までの組み合わせの数に加えて、自分自身のみの組み合わせ１つを足したものが、xで終わる組み合わせの数になります。

さて、位置x-1までの組み合わせの数を求めるには、0〜x-1までの値を足さないといけませんが、大セットの場合、これでは時間がかかりすぎます。
そこで、位置に対して、2個のまとまり、4個のまとまり、... 2^p個のまとまりでの総数も平行して計算しておいて、最大19個(log(50,000)<19なので)の探索だけで済むようにします。たとえば、12の位置であれば、(0〜7の総和)+(8〜11の総和)を足せば0〜11の総和が求まります。
構造としては、二分木で累積頻度を管理している形になります。

累積頻度の管理には、もう少し複雑になりますが、BinaryIndexedTree?
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees
というものもあります。

↑

Round2 †

↑

Cheating a boolean Tree †

問題
全二分木（すべてのノードが２つの子を持つか、子をまったく持たないかのいずれか）で、一番下層以外はすべて埋まっていて、一番下層は左側に寄っているものがある。外部ノード（下端の葉）は、０か１の値を持っていて、内部ノードはAND,ORのいずれかの属性と、変更可と不可のいずれかの属性を持っている。
内部ノードは、子ノードの持つ値とその論理演算により、自分の値を決める。
今、ルートノードの値を決めたとき、変更可の内部ノードのAND/ORを切り替えて、ルートノードの値が生成されるようにする。最小の切り替え個数を求める。ただし、不可能な場合もある。

この問題の場合、問題文の図を見るのが一番わかりやすいです。

解答例
下層からノードを0/1にする最小手順をそれぞれ求めていけば求まります。
小セットであっても、DPで解くのが、総当りで解くよりも楽なような気がします。

↑

Triangle Areas †

問題
N,M,Aが与えられる。
0<=x<=N, 0<=y<=M の整数の格子点があり、その点上に三角形の三点を取る。
そのときの三角形の面積がA/2になるような３点を求める。
３点は複数のとり方ができるが、答えはそのいずれでも良い。

大セットの場合、1<=N<=10000, 1<=M<10000。

解答例
１点は原点固定で問題なくて（回転とかさせれば必ず原点にできる）、
残りの２点(a,b),(c,d)が、|a*d-b*c|がAになるようにします（内積が面積*2なので）。

AがNの倍数のときは、(0,N),(A/N,0)で、Aになります。
A/N>Mなら解はありません。

AがNの倍数でないときは、
一点を(N,1)にすると、もう一点を(x,y)として |N*y - x|となります。
これがAとなるようにしてやれば、答えになります。
y = A / N + 1（xを引くので1足しておく）
x = N - A % N
です。
尚、N*M<Aの条件で、x,y<Mも満たせます。

↑

Star Wars †

問題
ストーリーを飛ばして要約すると、
(x_i,y_i,z_i,p_i)の組が複数渡されたとき、
ある１点(x,y,z)に対して、
P_i = (|x_i - x| + |y_i - y| + |z_i - z|) / p_i
とするとき、max(P_i)を最小にする(x,y,z)を求め、
そのときのmax(P_i)を返す。

解答例
総和なんかだと重心とかになるのですが、ここでは最大の値を持つもののみが必要な点が大切です。
雰囲気的に、線形計画法(LP)で解くのがセオリーっぽいです。

最小値が一点のみで、他に極小がない点に注目すると、
探索していけば特定の精度以下で答えが見つかります。

XYZ独立で解いても大丈夫かとちょっと思いましたが、
最大のものだけしか影響しないので、そうではありませんでした。
典型的３変数の線形計画法で、高速に解けます。多分。
ただ、コーディングが結構大変なので、うろついて探した方が簡単です。

↑

PermRLE †

問題
ランレングス圧縮（同じ文字が続くときに圧縮できる）の前処理として、
文字列を先頭からｋ文字単位のブロックに切り分けて、
その中で文字の並びを入れ替えます。入れ替えの方法は文字列ごとに１つのみで、
n番目(1<n<=k)の文字をp[n]番目(1<p[n]<=k)にするというものです。

文字列とkが与えられたときの、圧縮後の最小サイズを求めます。

圧縮後のサイズは、連続する文字を１単位とするものです。
aaabbcd なら abcd と同じで４です。

大セットの場合、2<=k<=16,S<=50000（文字列の長さ）です。

解答例
あらかじめブロック内の任意の入れ替えによる2文字の繋がり具合と、
ブロック間の繋がり具合をテーブル化しておきます。

これを使って、DPで最適解を求めます。
具体的には、並び替えで取りうるパターンの少ない方から計算していきます。

↑

コメント †

  • http://oakleyfrogskinsholbrookradar.blinkweb.com/ 2013-03-16 (土) 07:36:15
    He is used to eating out all the timeThis work itself is very easy.What a nice day it is!I saw him playing football on the playground.Don't worry.We need more than listening.We need more than listening.I could hardly speak.I saw it with my own eyes.＾I wish I'd known about that rule earlier", she said.
  • maillot alg辿rie 2010 2013-08-17 (土) 08:39:32
    I think this is a real great article post.Much thanks again. Want more.
    maillot alg辿rie 2010 http://maillotalgerie.1to1elite.com
  • maillot croatie 2011 2013-08-21 (水) 17:05:24
    I¨ll apply this idea´´ It can be fun!
    maillot croatie 2011 http://maillotcroatie.ethicalbase.com
  • maillot br辿sil hulk 2013-08-23 (金) 17:30:23
    viewtopic.php?t=*
    maillot br辿sil hulk http://maillotbresil.1to1elite.com
  • trikot nationalmannschaft 2010 ausw辰rts 2013-09-08 (日) 22:12:05
    I value the article.Really looking forward to read more.
    trikot nationalmannschaft 2010 ausw辰rts http://trikot-nationalmannschaft.asktorihartman.com
  • retro trikot adidas 2013-09-09 (月) 11:35:04
    I similar to the significant details you provide inside of your article content.I¨ll bookmark your blog site and check again here repeatedly.I¨m quite sure I will gain knowledge of quite a bit of latest stuff best suited listed here! High-quality luck for that upcoming!
    retro trikot adidas http://borussia-monchengladbach-retro-trikot.youaresomebody.org