Entries

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

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

ZJU 3405 - Counting Factor Trees (この記事を編集する[管理者用])

Source

ZOJ Monthly, September 2010 (blog)
ZJU 3405

問題概要

10^9以下の整数nが与えられたとき,問題の図のように,2分木を作る方法は何通りあるかを求める問題.
子供を掛けると親になり,葉は素数.
答えは2^63未満であることが保証されている.

解法

nを素因数分解した時の指数にのみ依存し,指数の順番も関係ない.
ので,指数をソートしたものでメモ化してメモ付き探索する.

ZJU 3403 - Strange Calendar III (この記事を編集する[管理者用])

Source

ZOJ Monthly, September 2010 (blog)
ZJU 3403

問題概要

X年にはX mod 12 + 1個だけ月がある.
i番目の月にはi^3個の日がある.ただし,Xが11の倍数のときの1月は2日ある.
2つの日付が与えられたとき,その間(両端を含む)に何日あるかを求める問題.
与えられる年は0以上10^9以下.

解法

閏年で増える日付は別処理すると,12年の間にある日付の数は固定なので,適当にまとめて計算する.
2つの日付の大小関係が指定されてないのに注意.

ZJU 3402 - Marble (この記事を編集する[管理者用])

Source

ZOJ Monthly, September 2010 (blog)
ZJU 3402

問題概要

15*15以下のマスに命令セットが振られている.
各命令セットは高々周期6で,命令は
 このマスにマーブルをn個加える (nは0以上9以下)
 このマスのマーブルを上下左右のどこかに移動させる
 このマスのマーブルを全部捨てる
のどれか.
最初すべてのマスにマーブルはないとして,時間t後に一番マーブルの多いマスのマーブルの数を求める問題.
tは10^9以下.

解法

常にマーブルが1個のマスを付け加えて,時間発展を行列で表し,それをかけていく.
行列はLCM(1,2,3,4,5,6)周期になるので,全部かけるときに高速冪乗を使う.

ZJU 3401 - Guitar (この記事を編集する[管理者用])

Source

ZOJ Monthly, September 2010 (blog)
ZJU 3401

問題概要

6弦ギターで,
 押さえ方を変える (指の位置を変える)
 どれかの弦を鳴らす
の2つの操作の列が与えられる.
鳴る音を順番に出力する問題.

解法

やるだけ.

ZJU 3397 - Change the Major (この記事を編集する[管理者用])

Source

ZOJ Monthly, September 2010 (blog)
ZJU 3397

問題概要

19人以下の人がいる.19人のスコアと,クラスがA,B,Cと3種類ある.
それぞれが今のクラスと,なりたいクラスが与えられている.
 クラスAの人がクラスBに移動する
 クラスBの人がクラスAまたはクラスCに移動する
 クラスCの人がクラスBに移動する
ことができるが,移動元のクラスと移動先のクラスに自分よりスコアが高い人が存在したら移動できない.
全員の希望を満たす最小移動回数を求める問題.
同スコアの人はいないとする.

解法

ハノイの塔みたいになる.
スコアの小さい人から動かすことを考えて,スコアの高い人が邪魔なら動かすという形の再帰.
ちゃんと考えれば良いのだろうが,普通に再帰で書いて適当にメモ化した.

ZJU 3396 - Conference Call (この記事を編集する[管理者用])

Source

ZOJ Monthly, September 2010 (blog)
ZJU 3396

問題概要

ノード数500以下,枝数10000以下の無向グラフが与えられる.
枝は最初使用不能で,使用可能にするためのコストが与えられている.
ある3点が指定されて,その3点を連結にするために使う枝のコストの和の最小値を求める問題.

解法

答えの最小木は,T字型にある1点を中継地点として,そこからそれぞれ3ノードへの最小パスを引いたものになる.
3回ダイクストラして,3ノードから全ノードまでの距離を求めておいて中継地点を全部試して最小値を求める.
ノード数的にワーシャルフロイドするとTLEかと思ったけど通った.

ZOJ Monthly, September 2010 (この記事を編集する[管理者用])

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

同じ日の18時からUVaであるコンテストの前哨戦みたいな感じで参加.
6問解いた.
以下解いた順番.

・問題J
小さい値だけメモ化しても大丈夫かと思ったけどテストケースの数が多くてTLE.
ちゃんと,素因数分解して,指数の値にのみ,しかも順番によらないので,それをソートしてメモ化したら通った.
・問題A
T字みたいな感じになるので,ノードkから3点のノードまでの距離の和を全部求めて,kを動かして最小値を取れば良い.
ノード数500なのでワーシャルフロイドして大丈夫か少し悩んだけど大丈夫だった.
クエリの数が少なかったので,毎回3点からダイクストラする方が良かった気もする.
・問題H
やるだけ.
閏年で追加されたのは別計算.後は12年での日付は分かっているので,それをまとめて処理する.
132年で1単位に思っても良かったかもしれない.
最初の日付の方が時間的に後のことがあるという,超古典的な引掛けに1回やられた….
・問題F
やるだけ.これはやるだけ.
・問題G
時間ごとに遷移行列を求めてやって,かけていく.
高々,周期がLCM(1,2,3,4,5,6)なので,tが大きい時は高速冪乗を使う.
行列のサイズが微妙に大きめだけど,答えはlong longに収まり,modを取ったりしなくていいので十分間に合う.
最初,行列をかける方向が逆でちょっとはまった.
この問題を解いてる人が地味に少ないのが謎.
・問題B
最初,不可能な場合があるとか,実は大してステップ数必要ないんじゃないか,と思ってはまってた.
よく考えると,ハノイの塔みたいな感じ.
再帰的にスコアの小さい人を動かすために,その上のスコアの人をどこに動かせばいいかってのを書いていく.
が,愚直に1ステップずつ動かすとTLEなので,adhocにメモ化した.

ZJU 3229 - Shoot the Bullet (この記事を編集する[管理者用])

Source
ZOJ Monthly, July 2009 (2009-07-19)
ZJU 3229

問題概要
射命丸文はn日間かけて,幻想郷に住むm人の可愛い少女の写真をできるだけ多く撮りたい.
m人それぞれに撮らなければいけない最小枚数が定められている.
また毎日,ターゲットは(複数)定められていて,それぞれのターゲットを撮る枚数の最小値,最大値が定まっている.
またそれぞれの日で撮ることのできる最大合計枚数も定まっている.
制約を全て満たすような撮り方のうち,最も多くの写真を撮る方法を求める問題(該当する取り方が複数あればどれか1つ求めればよい).
nは365以下,mは1000以下.

解法
m人のそれぞれ撮らなければいけない最小枚数を撮ることができるかどうかの判定は最大流でできる.
後は,撮れるだけ適当に撮ればOK.

ZJU 3230 - Solving the Problems (この記事を編集する[管理者用])

Source
ZOJ Monthly, July 2009 (2009-07-19)
ZJU 3230

問題概要
初期レベルpと,n種類の問題が与えられる.
問題には,解くのに必要なレベル,解いたら上昇するレベルが定められている.
1日に1問まで解ける.
m日後の最高レベルを求める問題.
n, mは100000以下.

解法
解ける問題の中で,一番レベルが上がる問題を解けばよい.
ヒープなどのデータ構造を用いる.

ZJU 3222 - Coverage (この記事を編集する[管理者用])

Source
ZOJ Monthly, July 2009 (2009-07-19)
ZJU 3222

問題概要
無限大の大きさのグリッドの100×100以下の部分以外は全部0で埋め尽くされている.
100×100以下の部分には整数が入っている.
縦X,横Yの大きさの長方形を2つの長方形に分割して,それぞれを重なっても良いのでグリッドの上に乗せる.
回転してはいけない.
長方形の重なっている部分の数字の和を最大化する問題.
重なっている部分は重複して数える.

解法
適当にDPっぽいこと(和を先に計算しておく)をすれば,後は全ての長方形の分け方とどこに置くかを全て調べてお終い.

Appendix

Recent Articles

ブログ内検索

Ads


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