2011-10-01から1ヶ月間の記事一覧
大体理解した。 完全にソラで書けるように何回か復習すべきである。 問題 N個の線分が接続されたクレーンがある。 それぞれの線分の長さはL[i]で与えられる。 はじめは全ての線分がまっすぐ上を向いて接続されている。 ここにC個の命令がくる。命令iは二つの…
問題 n個の文字列A[0],A[1],...,A[n-1]が与えられる。 接頭辞圧縮とは、次のような圧縮を言う。 A[i]とA[i+1]に対して、j<min(len(A[i]),len(A[i+1])かつ 次が成り立つ最大のjについて、 A[i][0]=A[i+1][0], A[i][1]=A[i+1][1], ..., A[i][j]=A[i+1][j-1] A…
問題 船の現在位置と、氷山の現在位置が与えられる。 船と氷山の距離を答えよ。 位置は緯度、経度によって与えられる。 地球は直径6875マイルの球とし、距離は地球表面上の最短距離をいうものとする。
問題 クロスワードパズルの図が与えられる。 縦のキーワードと横のキーワードを、番号をつけて出力せよ。 縦のキーワードの開始位置となるのは、 最初の行の文字のマス、あるいは一つ上が黒いマスである文字のマスであり、 横のキーワードの開始位置となるの…
問題 NxMマスのグリッドにそれぞれ異なる数が書かれている。 n個のマスには印がついていて、それらの座標はsx[i],sy[i]で与えられる。 それぞれのマスにかかれた数を入れ替えた配置のうち、 全ての印のついたマスからの距離が変わらない配置はいくつあるか、…
問題 lucky numberとは10進数で表したときに、全ての桁の数字が4または7である数を言う。1からnまでの整数の順列のうち、k番目のものについて、 それぞれの数字をa[1],a[2],...,a[n]とおく。1≦i≦nで、iがlucky numberかつa[i]がlucky numberであるようなiの…
問題 a,b,cという三つの数を変えてA * B = Cが成り立つようにしたい。 このとき、|A - a| + |B - b| + |C - c|の最小値を求めよ。 制約条件 a,b,c≦10^9
問題 二人のプレイヤーが'A','B'からなる文字列に対して次のようなゲームを行う。 コインの置かれていない連続する文字列の部分に対して、コインを置く ただし、全ての文字の上のコインが置かれる状態にしてはいけない コインが置けなくなったときに、残った…
問題 n個の文字列が与えられる。 このうちちょうどC個をその部分文字列として含むような、長さLの文字列の個数を求めよ。 制約条件 n≦6 L≦50
問題 座標平面上に縦n横mの長方形がある。 各辺は座標軸に平行で、一つの頂点は原点である。 この長方形の内部(周を含む)に描ける、全ての頂点が格子点上にある凸n角形について。 最大のnはいくつか。 制約条件 n,m≦200
問題 1/2 = .5, 1/3 = .(3), 1/4 = .25 ,...1/nと書いていったとき、 小数部分に数字kは何回現れるか求めよ。 制約条件 n≦100 k≦10
問題 正の整数a,b,c,dに対するFrobenius数とは、w,x,y,z≧0に対してwa+xb+yc+zdとして表すことのできない最大の数である。1000000以下の、wa+xb+yc+zdとして表せない数の個数および、Frebonius数を求めよ。 Frebonius数が1000000より大きい場合-1を出力せよ。…
問題 整数Xに対してX-factor chainとは次を満たす列のことを言う。 1 = X0 < X1 < …… < Xm = X; かつXi+1はXiで割りきれる。 正の整数Xが与えられたとき、このような列のうち最大の長さをもつものおよび、 そのような長さを持つ列の数を出力せよ。 制約条件 …
問題 容量AリットルとBリットルの二つの容器がある。 以下の操作を繰り返してどちらかの容器に入っている水の量をCリットルする。 最短手順の操作をどれか一つ出力せよ。 不可能な場合impossibleを出力せよ。 Aの容器を満タンにする Bの容器を満タンにする A…
問題 n個の都市がある。 1番の都市からn番の都市へ行きたい。 道路がm本あり、それぞれの道路は都市a[i]とb[i]を結んでいる。 道路を通るには交通料がかかり、 都市c[i]を事前に訪れている場合P[i]、そうでない場合R[i]のコストがかかる。 n番の都市へ行くの…
問題 地球上の二点が緯度と経度により指定される。 その二点間の、地表での距離を1メートルの精度で求めよ。 ただし地球は半径6370kmの真球と仮定せよ。 制約条件 なし
問題 N人が橋を渡りたい。 橋は同時に2人までしか渡ることができず、また一つしかない懐中電灯を持って渡る必要がある。 それぞれの人に対して橋を渡るのにかかる時間が決まっている。 二人が同時に渡るときは遅い人に合わせる。 全員が橋を渡り終えるのにか…
問題 2つのどぶにN個の石を投げる。 それぞれの石には重さp[i]および価値v[i]が定まっており、 次の条件を満たすように好きな順にどぶに投げ入れる。 最初に投げるのはAのどぶへ 二つのどぶに入っている石の重さの差がDを超えたら投げ入れるどぶを換える こ…
問題 アルファベットを暗号に変換する変換表が与えられる。 文字列が与えられる。これを暗号に変換し、復号するとき、何通りの文字列に復号できるか答えよ。 制約条件 入力のサイズ≦100
問題 r行c列の'0','1'の行列AとR行C列の'0','1'の行列Bが与えられる。 Bの一部の行と、一部の列を削って、Aを作ることはできるか答えよ。 制約条件 r≦R≦20 c≦C≦20
問題 n個の整数が与えられる。 この中から適当な(空でない)部分集合を選び、その要素の和がcの倍数にすることはできるか。できるならそのような集合(どれでもよい)の要素を全て出力し、 不可能なら"no sweets"と出力せよ。 制約条件 1≦c≦n≦100000
問題 N部屋個の部屋があり、それらはいくつかの一方通行の通路で結ばれている。 各部屋にはそれぞれのエネルギーがあり、部屋に入る度に、自分の持っているエネルギーに部屋のエネルギーが足される。 部屋のエネルギーが負であることもある。 自分は最初100…
問題 平面上に、N個の長方形の建物がある。 建物の一辺はx軸上にある。 建物の上の辺は二点(A[i],H[i]),(B[i],H[i])を結んでいる。 建物一つ以上に覆われている領域の面積の総和を求めよ。 制約条件 N≦40000 A[i],B[i],H[i]≦10^9
問題 雪の結晶は6つの整数により表される。 ただし、整数の順序をシフトさせたものや、順序を反転させたものは同一である。 与えられる雪の結晶の中に、同一の二つがあるなら Twin snowflakes found.を、そうでないなら No two snowflakes are alike.を出力…
問題 数字と'?'からなる文字列wと数xがマッチするとは、 wのそれぞれの'?'を任意の数字一文字に置き換えたとき、xと一致することを言う。 パターンwと数xが与えられる。 xより大きくwにマッチする数の総数を求めよ。 制約条件 wとxの桁は等しく、かつ10桁以下
問題 アルファベットに数字が対応している。 1 ij 2 abc 3 def 4 gh 5 kl 6 mn 7 prs 8 tuv 9 wxy 0 oqz文字列からなる辞書が与えられる。 数字の列が与えられたとき、数字の列を文字列として解釈せよ。 解釈の仕方が複数通りある場合、単語数が最も少ないも…
問題 nxmマスのグリッドがある。 グリッド上にはいくつかの穴があいている。 グリッドに1x2の板を、穴の上を避けて、かつ穴以外の全てのマスを覆うように敷き詰めたい。 それが可能であるかどうか、判定せよ。 制約条件 n,m≦32
問題 アリスはn本の映画に出演したい。 それぞれの映画は、一週間のうちに撮影できる日が決まっている。 それぞれの映画には、定められた期限(w[i]週間)がある。 それぞれの映画が完成するためには、アリスがd[i]日、撮影に加わらなければならない。 アリ…
問題 N箇所の地点に3台の車を使って雑誌を配達する。 N箇所地点のそれぞれの間の距離は与えられている。 車の動かし方には以下のような制限がある。 一度に同時に動かせる車は一台だけ L[i]番目の地点に訪れるにはL[i-1]番目の地点を訪れなければならない 制…
問題文 二つの式が与えられる。 式は、変数または数字と、足し算、引き算、掛け算からなる。 二つの式が恒等であるかどうかを判定せよ。 制約条件 式の文字数≦80 式中には空白またはタブが任意に入る 式の係数は16bitに収まる