Entries

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

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

Aizu 1203 - Napoleon's Grumble (この記事を編集する[管理者用])

Source

ACM/ICPC Tokyo 1998
UVa 689
ZJU 1660
Aizu 1203

問題概要

1024文字以下の文字列が与えられる.アルファベット以外は無視し,アルファベットは全て大文字に変換する.
その文字列の長さ3以上の部分文字列で極大の回文となっているものを全て出力する問題.
ただし,極大の回文という意味は,文字列Xが回文で,ある文字cに対してcXcという文字列も部分文字列に含まれるならXは出力しないという意味.
Aizuでは出力する順番は任意,UVaとZJUでは辞書順に出力しなければいけない.

解法

中心を決め打って,答えの候補を全部列挙する.
後は,それが他の中心の回文に含まれなければ出力するとかそんな感じで適当にやる.
O(n^3)の気もするけど通る.(n=文字列の長さ)

記事更新履歴 (2009-08-28 01:50)

ソースにZJUへのリンクを追加.
ZJUに関する仕様追記.(UVaでは→UVaとZJUでは)

続きを読む

Aizu 1201 - Lattice Practices (この記事を編集する[管理者用])

Source

ACM/ICPC Tokyo 1998
UVa 687
ZJU 1658
Aizu 1201

問題概要

{0,1}からなる5文字の文字列が10個与えられる.
それを縦に5個,横に5個並べて,重ねて,全てのマスが0と1が1個ずつあるようにしたい.
そのような組み合わせ方の数を求める問題.
各文字列は回転とか自由にして良くて,最終形態も回転とか鏡像とかして同じに見えるなら重複してカウントしてはいけない.
与えられる文字列は(鏡像を同値とみても)同じものは2つ以上ない.

解法

バックトラックで枝刈り全探索.
1行目,1列目,2行目,2列目,…という順番で探索してみた.
最終的な答えの数は最高でも数十のオーダー.
重複してカウントしてはいけないという部分をいいかげんな処理をしていたらAizuでは通ったっけどUVaだとWAだった.
反例が思い浮かばなかったんだけど,愚直に調べたらUVaでも通った.
UVaの方がジャッジデータが厳しいらしい.

記事更新履歴 (2009-08-28 01:50)

ソースにZJUへのリンクを追加.

Aizu 1202 - Mobile Phone Coverage (この記事を編集する[管理者用])

Source

ACM/ICPC Tokyo 1998
UVa 688
ZJU 1659
Aizu 1202

問題概要

2次元平面上に,x軸,y軸に平行な正方形がn個与えられる.
その正方形でおおわれている面積を求める問題.
nは100以下.

解法

座標圧縮して塗りつぶす.O(n^3).

記事更新履歴 (2009-08-28 01:50)

ソースにZJUへのリンクを追加.

SPOJ 2150 - Counting Subsequences [SUBSEQ] (この記事を編集する[管理者用])

Source

IPSC 2006
SPOJ 2150 [SUBSEQ]

問題概要

長さnの整数列が与えられるので,その連続する部分列で和が47になるものの数を求める問題.
問題文には書かれていないが,nの最大値は数十万~百万程度の様子.

解法

最初から和を計算していって,同時に 和-47 の値が今まで出てきた回数を足していけば答えになるはず.

続きを読む

Another HTML-lint gateway (この記事を編集する[管理者用])

Another HTML-lint gatewayでこのブログのトップページを採点するとマイナス90点ぐらいという悲惨な結果になった….
これからは少しは気をつけていこうかな….

UVa 11655 - Waterland (この記事を編集する[管理者用])

Source

Once Again! A Bangladeshi Contest (2009-08-22) (blog)
UVa 11655

問題概要

ノード数5000,枝数25000以下のグラフが与えられる.
始点から終点に向かう長さ∞のパス(ループを含むパス)は存在しないことが保証されている.
始点から終点に向かうパスの総数と,そのパスに含まれる枝の数の和をmod 100000で求める問題.

解法

時間O(n+m),領域O(n)のDP.(nはノード数,mは枝数)

UVa 11654 - Arithmetic Subsequence (この記事を編集する[管理者用])

Source
Once Again! A Bangladeshi Contest (2009-08-22) (blog)
UVa 11654

問題概要
要素数250以下の数列が与えられるので,その長さ1以上の部分列で等差数列となるものの数をmod 10000007で求める問題.

解法
時間O(n^3),領域O(n^2)のDP.(nは要素数)
状態は,最後に使った2項.それで公差は定まる.

UVa 11651 - Krypton Number System (この記事を編集する[管理者用])

Source
Once Again! A Bangladeshi Contest (2009-08-22) (blog)
UVa 11651

問題概要
b進数で,隣り合う数字は異なっていて,最初は0から始まらなくて,隣り合う数字の差の2乗和がsとなる数字はいくつあるかをmod 2^32で求める問題.
bは2以上6以下,sは10^9以下.

解法
行列べき乗.
ただし,何も考えずに行列作ると,サイズが b*(b-1)^2 となって,最大で150になってしまってTLE.
最後の桁を考えているとき,0とb-1は同じように思える,といった対称性を使うとサイズが半分ぐらい( (b+1)/2 (b-1)^2 )になって通る.

UVa 11650 - Mirror Clock (この記事を編集する[管理者用])

Source
Once Again! A Bangladeshi Contest (2009-08-22) (blog)
UVa 11650

問題概要
時間(時間と分)が与えられるので,その時間を指しているアナログ時計を鏡に映してみると何時に見えるかを求める問題.

解法
12時から何分たったかを求めて,その分反時計回りに回せば良いので,12*60から引くと良い感じ.

UVa 11648 - Divide The Land (この記事を編集する[管理者用])

Source
Once Again! A Bangladeshi Contest (2009-08-22) (blog)
UVa 11648

問題概要
台形が与えられたとき,平行な2つ線と平行に線を引くことで台形を同じ面積の2つの台形に分割することを考える.
その時の,片方の辺の長さ(分割するときの縦の比率)を求める問題.

解法
数学.計算するだけ.2次方程式に落ちる.

UVa 11646 - Athletics Track (この記事を編集する[管理者用])

Source
Once Again! A Bangladeshi Contest (2009-08-22) (blog)
UVa 11646

問題概要
1周の長さが400のトラックを作る.
長方形の横縦の比が与えられたとき,横縦の長さを求める問題.
ただし,横は円周上を走る.円の中心はトラックの中心.

解法
数学.計算するだけ.

SPOJ 4681 - Twice [TWICE] (この記事を編集する[管理者用])

Source
SPOJ 4681 [TWICE]

問題概要
長さnの文字列が与えられるので,その部分文字列として2回以上登場するもののうち最長のものの長さを求める問題.
部分文字列は区間がオーバーラップしてても良い.
nは200000以下.

解法
長さkの2回以上登場する部分文字列が存在するかどうかはrolling hashを計算しながらなぞることでO(n)で判定可能. 後は2分探索すると,合計でO(n log n)で計算可能.

SRM443 DIV1 MEDIUM - BinaryFlips (この記事を編集する[管理者用])

あの超有名人のchokudai先生書いた記事の反応が少ないとか嘆いているらしいのでソースコード(C++)張り付けておく.
元記事の方針3の
このコードではループを使って最小のものを求めていますが、これは直接解くことも可能です。
というのを愚直に実装しただけです.
本番で,BFSは区間でやれば大丈夫ってのになるほどと感心したんだけど,それは良いとして,普通に不等式解けるじゃんとか言われてなるほどとか思ってるのはいけないなぁ….
計算時間を見積もって大丈夫なら,それ以上考えないTopCoder脳は時に駄目だと思う.
ICPC形式のコンテストのときは結構考えるのにね.
#include<vector>
#include<iostream>
#include<sstream>
#include<climits>
using namespace std;

// THIS IS O(1) TIME SOLUTION!!

class BinaryFlips {
public:
int minimalMoves(int A, int B, int K) {
  int myonmyon=INT_MAX;

  if(A==0) return 0;
  if(A==K) return 1;
  if(K>=A+B || (A%2 && K%2==0)) return -1;

  if(A%2==0){
    int chota = (3*A+2*B-2*K-1)/(A+B-K)/2;
    int shota = (A+2*K-1)/K/2;
    myonmyon = min(myonmyon,2*max(chota,shota));
  }

  if(K%2==0 || A%2){
    int chota = (3*A+4*B-3*K-1)/(A+B-K)/2;
    int shota = (A+3*K-1)/K/2;
    myonmyon = min(myonmyon,2*max(chota,shota)-1);
  }

  return myonmyon;
}

Once Again! A Bangladeshi Contest (この記事を編集する[管理者用])

2009年08月22日18時から5時間45分,10問.
[ Link ]

色々用事があって3時間遅れぐらいで参加.
参加したとたんサーバが1時間近く落ちてorzだったけど,その分45分延長されて何とか6問正解.
解いた問題はそのうち問題ごとに記事を書く予定.

Fで結構はまったのが痛かった…,なんか最近行列作るの苦手だなぁ….
Jも最初問題読み間違えてて入力がDAGじゃないと思ってて無理無理とか思ってた….
とにかく,焦ると良くない….

前回のUVaも,徹夜+天下一で殆ど問題解いてないし,コンテストランキングが危うい….

ちなみに,Aizuのは完全に用事とかぶってて出れなかった…無念.
そして明日のPKUも無理…orz

SPOJ 3882 - Cijevi [CIJEVI] (この記事を編集する[管理者用])

Source
COCI 2008/2009 - Croatian Regional
SPOJ 3882 [CIJEVI]

問題概要
図の7種類のパイプで適当にMからZまで繋がっていた.
が,1マスだけ空白のマスに変えられてしまった.
そのマスの座標と,変えられる前のマスの種類を特定する問題.

解法
Mから適当に辿って最初に辿り着いた空白のマスが変更されたマス.
そのマスから上下左右のマスに繋がるかどうかで元々そのマスが何だったかはわかる.

SPOJ 3920 - Lucius Dungeon [BYTESE1] (この記事を編集する[管理者用])

Source
SPOJ 3920 [BYTESE1]

問題概要
100*100マスのダンジョンの各マスにモンスターがいて,倒すのに必要な時間が与えられる.
入り口は左上のマスで,上下左右に移動できる.
ヒロインは時間T後に爆弾で殺されるので助け出したい.
ヒロインがいる座標が与えられるので,助けられるかどうかを判定し,助けられるなら最短で爆発のどれだけ前に助けられるかを出力する問題.
助ける=ヒロインの場所に辿り着く.

解法
ダイクストラ.

SPOJ 3889 - Closest Number [MCLONUM] (この記事を編集する[管理者用])

Source
BOI For Kid 08
SPOJ 3889 [MCLONUM]

問題概要
n桁の数字AとBが与えられるので,Bの置換からなるn桁の数字で
 Aより小さいものの中で,最も大きいもの
 Aより小さくないものの中で,最も小さいもの
をそれぞれ求める問題.存在しないならそれを指摘する.
n桁の数字といったとき,最初の桁が0のものは認められない.
nは60以下.

解法
グリーディーに適当に頭の文字から決めていく感じでやる.

片霧烈火 (この記事を編集する[管理者用])

hyon先生のtwitterで見つけたけど片霧烈火のワールドイズマイン(ニコニコ動画)
かわいかっこいい.
烈火さん,CLOSED/UNDERGROUNDとして歌ってるときは,一段と荒く,弾けてて,聴いてて楽しい.
つうか,これ,動画,神藝工房コンビだ.なつかしい(?)

Aliceの新作のデモムービー公開されてたけど,今回もOPがとても烈火さんっぽかった.(確証はない)
Shadeさんの編曲はぱすちゃOPみたいなポップ系.
そのせいで薄められてる気がするけど,地味にメロディが格好良かった.
ボーカルはこっちはちゃんと纏めてきてるけど,地味に声色を使い分けてて,心地よく格好良く,といった感じ.

Aizu 1204 - Pipeline Scheduling (この記事を編集する[管理者用])

Source

ACM/ICPC Tokyo 1998
UVa 690
ZJU 1661
Aizu 1204

問題概要

5*nの一部分黒い,一部分白いピースが与えられる.
白い部分は重なってもよく,黒い部分が重なってはいけないという状況で,5*kに10個敷き詰める.
敷き詰められる最小のkを求める問題.
nは20以下.

解法

メモ付探索.状態は敷き詰めなくて残りのピースの数,現在の敷き詰めたパターンの右からn列.
メモリ使用量が見積もれないけれど,ジャッジデータに対する状態数はそんなに多くない様子(高々数万程度のオーダー).
Aizu Online JudgeだとWAで通らないけど,uoa==3の人も同じらしいのでそのうち修正されると信じている.
(追記) Aizuは2009-08-27にジャッジミス修正された.

記事更新履歴 (2009-08-28 01:50)

ソースにZJUへのリンクを追加.
Aizuのジャッジミス修正に関して追記.

SPOJ 3982 - String problem [MSTRING] (この記事を編集する[管理者用])

Source
COI 04
SPOJ 3982 [MSTRING]

問題概要
長さAの文字列と長さBの文字列が与えられる.文字はアルファベット小文字のみ.
最初の文字列の部分列で,2番目の文字列の部分列でないもののうちで長さ最小のものの長さを求める問題.
部分列は隣接しているところから取ってこなくて良い.
そのような部分列が存在することは保証されている.
A,Bともに1000以下.

解法
部分列の最後の文字を決め付けると,それぞれの文字列の最後に登場するその文字の部分以降を切り落とした文字列の小問題に帰着できる.
なので,計算時間O(ABK)のDPする.K=26はアルファベットの種類数.

SPOJ 3924 - Filchs Dilemna [BYTESH1] (この記事を編集する[管理者用])

Source
SPOJ 3924 [BYTESH1]

問題概要
図の2個のピースで,3*nを埋め尽くす方法の数をmod 10000で求める問題.
nは1000000以下.

解法
適当に漸化式作ってDPするだけ.
テストケースの数が少ないので,行列のべき乗の方が速いのかも?

SPOJ 839 - Optimal Marks [OPTM] (この記事を編集する[管理者用])

Source
SPOJ 839 [OPTM]

問題概要
ノード数500以下,枝数3000以下のグラフが与えられる.
いくつかのノードに数字が指定されてあって,その他のノードの数字は自由に指定できる.
枝のコストが,両端のノードの数字のXORのとき,枝のコストの和を最小化するようなノードの数字の指定の仕方を1つ求める問題.

解法
各ビットごと独立に考えれば良い.
ビットごとに考えると,最小カット(最大流)に帰着できる.
TopCoderのSRM442のDIV1 HARDを参照 (Editorial).

SPOJ 687 - Repeats [REPEATS] (この記事を編集する[管理者用])

Source
BOI 2004
SPOJ 687 [REPEATS]

問題概要
長さnのaとbからなる文字列が与えられる.
その部分文字列で,ある文字列のk回の繰り返しになっているものを探す.
最大のkを求める問題.
nは50000以下.

解法
最悪計算量O(n^2)だけど,nが大きいと答えもそれなりに大きい気がするので愚直にやる.
それでも通る.

SPOJ 696 - Liar Liar [LIAR] (この記事を編集する[管理者用])

Source
ByteCode '06
SPOJ 696 [LIAR]

問題概要
n人の人たちが,互いに正直者か嘘つきか言っている.
嘘つきは少なくても1つの情報が間違っている.
最小・最大で何人嘘をついているかを求める問題.
nは70以下.

解法
全員嘘をついている,あるいは誰かが正直なことを言っていると仮定して,矛盾がないか確かめる全探索.
計算時間O(n^3).

SPOJ 2322 - Tree Game [TREEGAME] (この記事を編集する[管理者用])

Source
MIT 1st Team Contest 2007
SPOJ 2322 [TREEGAME]

問題概要
高さhの完全2分木があって,ノードに数字がついていて,子供が両方1なら0,そうでなければ1となる.
コンピュータは葉の数字を,入力の順番に聞いてくるので,ノードの番号が推測されないようにはどう答えればよいかを求める問題.
hは15以下.

解法
子供の片割れが0になると,親が定まってしまうので,兄弟が定まってなければ1となるようにする.
という感じのことを再帰すればよい.

SPOJ 2742 - Summing Sums [SUMSUMS] (この記事を編集する[管理者用])

Source
USACO Chn 2007
SPOJ 2742 [SUMSUMS]

問題概要
N個の数字がある.
時間が1だけ経つと,それぞれの数字は自分以外の和に変化する.
時間T後の数字たちをmod いくつかで求める問題.
Nは50000以下,Tは1414213562以下.

解法
時間T後の数字は,元々の自分の数字と,自分以外の数字の和の線形結合で書けるはず.
その係数の満たす漸化式作って,いつもどおり行列のT乗を求める.

SPOJ 709 - The day of the competitors [NICEDAY] (この記事を編集する[管理者用])

Source
SPOJ 709 [NICEDAY]

問題概要
N人で3回プログラミングコンテストした順位が与えられる.
毎回同点なくて,完全に順位がついている.
3回とも自分より順位が良かった人がいないような人を優秀者と定義したとき,優秀者の数を求める問題.
Nは100000以下.

解法
まず,1回目の順位でソートして順位の高い順に処理する.
2次元座標に順位をプロットしていくと考えたとき,自分をプロットしたとき,その左下に点がなければカウンターを増やす.
それを毎回O(log n)程度で計算するためにはsegment tree (range minimum query)を使えばできる.

SPOJ 707 - Triple-Free Sets [TFSETS] (この記事を編集する[管理者用])

Source
SPOJ 707 [TFSETS]

問題概要
正整数nが与えられるので,{1,2,...,n}のサブセットで
 セット内に含まれる数の2倍および3倍の数はセット内に含まれない
ようなものの数を求める問題.
要するにThe On-Line Encyclopedia of Integer Sequences: A050295
nは100000以下.

解法
まず,n以下で素因数分解すると2^i * 3^jとなるものだけからなるサブセットの数を考える.
それだけに限定すると適当にDPすると何とか計算できる.
後は,k * 2^i * 3^j (kは2でも3でも割り切れない)となるものをそれぞれ考えると,kの値ごとに独立に考えれるので,
さっきDPで求めた値をかけていけば良い.

SPOJ 2412 - Arranging Amplifiers [ARRANGE] (この記事を編集する[管理者用])

Source
CodeCraft 08
SPOJ 2412 [ARRANGE]

問題概要
長さn (100000以下)の正整数列が与えられるので,その置換で
 a[n-1]^(a[n-2]^(... a[0]^1)...)
を最大にするようなものを求める問題.
ただし,複数存在するなら辞書順最小のものを求める.
数列に1以外の要素は,2個以上同じ数字はない.

解法
基本的に大きいものから出力すれば良い.
ただし,1だけは例外的に最初に出力する.
また,大きいほうから2つが2と3のとき,順番が逆転する.

SPOJ 2727 - Army Strength [ARMY] (この記事を編集する[管理者用])

Source
IPSC 2008
SPOJ 2727 [ARMY]

問題概要
ゴジラ軍とメカゴジラ軍が戦争する.
ゴジラ軍はNG匹のモンスターからなり,メカゴジラ軍はNM匹のモンスターからなり,モンスターの強さが設定されている.
1回の戦闘で,一番弱いモンスターが死ぬ.
一番弱いモンスターが複数いる場合,メカゴジラ軍から優先的にランダムに1匹選んで死ぬ.
何回か戦闘を繰り返して,最終的に全滅したほうが負けとして,どちらが勝つかを求める問題.

解法
一番強いモンスターがいる軍が勝つ.
同率ならゴジラの勝ち.

Appendix

Recent Articles

ブログ内検索

Ads


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