2010-12-01から1ヶ月間の記事一覧
問題概要 数列a1,a2,……,anに転置(i,j)を施すと、aiからajの部分が逆順になる。 元の数列は1,2,3,...,Nで、ここに与えられた転置を施すとき、元の数列のi番目の数字は何番目に来るか答えよ。 N≦50000,転置回数≦1000,求める数字の個数≦100を満たす。
問題概要 半径が1の円柱を積み上げる。 n+1列目の円柱は全て、n列目の円柱のちょうど二つに接している。 円柱は、円柱が列に一つだけになるまで積み上げられる。 1列目の円柱のx座標が与えられたとき、一番上の円柱の中心の座標を求めよ。
問題概要 接頭辞と接尾辞から、単語の意味を作る表が与えられる。 接頭辞と接尾辞のついた単語を、意味の文に変換せよ。
問題概要 ,-,(),および一文字の変数からなる式が与えられる。 この式の括弧をできるだけ外し、空白を取り除いた式を出力せよ。 ただし-二回が+になるような変形は行ってはならない。
問題概要 座標平面上の格子点にM個の隕石が降ってくる。 それぞれの隕石の座標(xi,yi)および時間tiが与えられる。 マスに隕石が落ちると、それ以降、そのマスおよび接する4マスに立ち入ることはできなくなる。 最初Bessieは(0,0)にいて、第一象限を、時間1ご…
問題概要 二列に整数が並んでいる。上の列と下の列の同じ数字を線で結ぶことができる。 このとき、次のようなマッチングの数を最大にしたい。 一つの数字からは最大一つの直線しかひかれていない 全ての直線は、異なる数字同士を結ぶ直線と一度だけ交わって…
問題概要 N個のノードとM個の辺からなる無向グラフで、1番のノードからN番のノードまで行くパスを作りたい。 好きなK本の辺は無料にしてもらえて、残りの辺のうち最大の長さがパスのコストになる。 パスのコストの最小値を求めよ。
問題概要 牛がN分間の間次のようなマラソンをする。 1分間ごとに走るか休むかを選べ、走る場合にはi分目にはd[i]の距離を走れて、疲労度が1増える。 休む場合1分間に疲労度が1回復するが、0になるまで再び走ることができない。 疲労度はMを超えてはならない…
問題概要 長さ40000以下の文字列が与えられる。 この文字のi番目までの部分文字列が元の文字列の接頭辞かつ接尾辞であるとき、そのようなiを全て昇順で出力せよ。
問題概要 非負整数n,d,b,eが与えられるとき、n/dを7進法で表したときの、小数点下b桁目からe桁目を出力せよ。
問題概要 ノード数200以下の木を使った次のようなゲームがある。 最初にK個の石をかごに入れる。 かごの石は好きな葉に置くことができる。 子全てに石のおかれたノードがあるとき、子の全ての石をかごに戻し、そのノードに石を置くことができる。 根に石が置…
問題概要 連結な無向グラフで表されるコンピュータネットワークがある。 このネットワークから、1台のコンピュータを取り除いたとき、ネットワークが2つ以上のサブネットワークに分断されるとき、そのようなノードをSPFと呼ぶ。 ネットワークの全てのSPFおよ…
問題概要 絵の具のセット一つにはN色の絵の具がそれぞれ50mlずつ入っている。 異なる3色の絵の具をxmlずつ混ぜるとxmlのグレーの絵の具を作ることができる。各色の必要量および、グレーの色の必要量が与えられるとき、 絵の具のセットを購入しなければならな…
問題概要 V,Aの列が与えられるとき対応する直線を描くPostScriptを出力せよ。 ただしVは反時計回りに直角に曲がる折れ線を描くことを、Aは時計回りに直角に曲がる折れ線を描くことを意味する。 描画の開始位置は(300,420)、各線分の長さは10である。
問題概要 人iが「木jから音がした」と言っているというリストが与えられる。 このとき、音がしている木の集合は何通り存在するか。
問題概要 与えられた文字列全てを(連続する)部分文字列として含むような文字列の最短の長さを求めよ。 文字列の数は10以下、各文字列の長さは20以下である。
問題概要 AOJに日本語の問題文があるのでそちら参照。 (http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1138&lang=jp)
問題概要 タクシーのスケジュールが"時間 タクシーの出発位置 目的地"のリストにより与えられる。 このとき、スケジュールを満たすために必要なタクシーの最小の台数を求めよ。 タクシーの台数は500以下、 任意の二点(x,y) (v,w)をタクシーが移動するのにか…
問題概要 5チームのランキングがいくつか与えられる。 これらに対してmedian rankingを次のように定める。 median rankingと、それぞれのランキングについて任意の二つのチームの上下関係が逆転しているたびに値に1を足す。 この値が最小になるようなランキ…
問題概要 英数字からなる文字列は、 Jを通ると一文字左にずれる。("aB23d"は"B23da"になる) Cを通ると一文字右にずれる。("aB23d"は"daB23"になる) Eを通ると左半分と右半分が入れ替わる。文字数が奇数の場合中央の文字は変化しない。(e3ac"は"ace3"に…
問題概要 1 - (1/k1 + 1/k2 + … + 1/kn)を正で最小にするような数列、 k1,k2……を求めよ。 ただしkiは自然数でありki<ki+1を満たすものとする。 n≦18とする。
問題概要 頂点数nの単純無向グラフで、連結なものはいくつあるか求めよ。 n≦18とする。
問題概要 n枚の数字の書かれたカードが一列に並んでいる。 これを使って以下のようなゲームをする。 両端以外のカードを一枚選び、そのカードと、その両隣のカードの数字3つを掛けた数をスコアに足す そのカードを取り除く この操作を残りのカードが2枚にな…
問題概要 a進数で表現された数nが与えられる。これをb進数へ変換せよ。 ただし結果が7桁に収まらない場合はERRORを出力せよ。
問題概要 有向グラフで表されるソフトウェア配布ネットワークが与えられる。 このネットワークについて以下の二つの値を求めよ。 全てのノードにソフトウェアを行き渡らせるために、最初にソフトウェア配布しなければならないノードの数。 どんなノードに最…
問題概要 6種類のコインの価値が与えられる。 このとき1〜100の値段を支払うのに使うコインの最小の枚数の平均値を求めよ。 ただし支払いに使うコインの枚数は、こちらが渡すコインの枚数と、おつりで貰うコインの枚数の和を表すものとする。
問題概要 目標物二つの座標および北から測った角度が与えられる。 このとき現在地の座標を求めよ。
問題概要 鍵は、入力文字列から異なる5文字を任意の順番で選び、 A=1,B=2...Z=26で整数を対応させて、v,w,x,y,zとしたときにv - w2 + x3 - y4 + z5 = target の式を満たすようなもののうち、最も辞書順で最後に来るものである。 入力文字列およびtargetが与…
問題概要 二分木が与えられる。キーの値が与えられるとき、葉のノードの値を出力せよ。
問題概要 正整数n,mが与えられる。n/mが割り切れるならそれを、そうでないなら最初の循環節の終わりまで小数を出力し、循環節の長さを出力せよ。 小数は50字ごとに改行せよ。