PKU
問題 変数a〜zおよび+, -からなる式が与えられる。 変数は式中で(一つの変数に対して最大1個の)--または++が前置、または後置されることがある。 変数に++が前置された場合は、式の値を求める前にその変数の値を+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マイルの球とし、距離は地球表面上の最短距離をいうものとする。
問題 クロスワードパズルの図が与えられる。 縦のキーワードと横のキーワードを、番号をつけて出力せよ。 縦のキーワードの開始位置となるのは、 最初の行の文字のマス、あるいは一つ上が黒いマスである文字のマスであり、 横のキーワードの開始位置となるの…
問題 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に収まる
問題 NxMのグリッドにアルファベットが書かれている。 ここからP個の単語を抜き出す。 単語はグリッド中で縦または横に連続してつながっていなければならない。 P個の単語は全て抜き出す必要がある。 一つのグリッドの文字は一つの単語にしか使えない。 単語…
問題 与えられたm個の数字x1,x2,...,xmのみを使ってできる、最小のNの倍数を求めよ。 作れない場合は0を出力せよ。 制約条件 m個の数字は全て異なる。 0≦N≦5000
問題 モールス信号が与えられる。 この信号は、すべて辞書の単語をモールス信号に変換したものを並べたものである。 モールス信号の解釈の仕方は何通りあるか、出力せよ。 ただし、モールス信号を解釈した際に過不足があってはならない。 制約条件 データセ…
問題 単語のリストが与えられる。 このリストの単語を使ってしりとりをする。 与えられた単語を、全てちょうど1度ずつ使うしりとりができるかどうかを判定せよ。 制約条件 単語の数≦100000
問題 hxwマスの迷路が与えられる。 '#'のマスは壁で入ることができず、'.'のマスは立ち入ることのできるマスである。 任意の二つの'.'のマスは、それをつなぐパスがただ一つ存在する。 最も離れたマスとマスの距離を求めよ。 制約条件 h,w≦1000