Entries

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

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

Beta Round #94 DIV2 B問題 - Students and Shoelaces (この記事を編集する[管理者用])

Source

Codeforces Beta Round #94 DIV2 B問題 (1000pt)
Problem description

問題概要

ノード数100以下の無向グラフが与えられる.
1回の作業で,次数が1のノードがいっぺんに取り除かれる.
取り除くノードがなくなったら終了する.
何回取り除く作業を行うか求める問題.

解法

シミュレーションする.愚直にやってもO(ノード数^3)ぐらいになるので間に合う.

C言語のスパゲッティなコード

続きを読む

Beta Round #94 DIV2 A問題 - Cookies (この記事を編集する[管理者用])

Source

Codeforces Beta Round #94 DIV2 A問題 (500pt)
Problem description

問題概要

n個 (100以下) の袋があって,それぞれの袋の中にはクッキーがa[i]個 (100以下) 入っている.
1個袋を取り除いて,残りのクッキの総数を偶数にする方法は何通りあるか求める問題.

解法

やるだけ.

C言語のスパゲッティなコード

続きを読む

Beta Round #94 DIV1 D問題 - Numbers (この記事を編集する[管理者用])

Source

Codeforces Beta Round #94 DIV1 D問題 (2000pt)
Problem description

問題概要

10^9以下の正整数がn個 (3以上10^5以下) 与えられる.
円形に数字を並べて,隣り合う数字の差がちょうど1になるようにできるかどうかを判定する問題.

解法

greedy.
ソートして,一番小さいのを1個,一番大きいのを1個,その間は2個とりあえず使う.(いってかえるだけ)
あとは,隣り合うのを1つずつ使うことができる.(適当な場所に挿入すれば良い)
そうやって全部消費できるか調べる,などの方法でできる.

C言語のスパゲッティなコード

続きを読む

Beta Round #94 DIV1 C問題/DIV2 E問題 - Games with Rectangle (この記事を編集する[管理者用])

Source

Codeforces Beta Round #94 DIV1 C問題 (1500pt)
Codeforces Beta Round #94 DIV2 E問題 (2500pt)
Problem description

問題概要

グリッドがあって,グリッドに添うように長方形を描く.
最初,サイズn*mの長方形が書かれている.
最後に書いた長方形の厳密に内側に長方形を描く作業をk回行う.
書き方は何パターンあるかmod 1000000007で求める問題.
n, m, kは1000以下.

解法

使うx座標を2k個選んで,使うy座標を2k個選べば,端から使って行かないとダメなので,一意に定まる.
よって,コンビネーションの積.

C言語のスパゲッティなコード

続きを読む

Beta Round #94 DIV1 B問題/DIV2 D問題 - String (この記事を編集する[管理者用])

Source

Codeforces Beta Round #93 DIV1 B問題 (1500pt)
Codeforces Beta Round #93 DIV2 D問題 (2500pt)
Problem description

問題概要

長さ10^5以下のアルファベット小文字のみからなる文字列が与えられる.
その空でない部分文字列 (重複も含めて) を全部もってきて,ソートした時,k番目のものを答える問題.
kは10^5以下.

解法

Suffix ArrayとLCPを使って,1番目から列挙してあげた.O(length log length + k)ぐらい.
他の方法は,最初,全部一文字の部分文字列をheapにつっこみ,小さい順に取り出す.
取り出されたものに,後ろを一文字加えて突っ込み直す.というのをk回繰り返せば良い.
その際,文字列の比較が重たいので,ローリングハッシュで,どの部分文字列が一緒かを判定できるようにしておいて,最初に異なる文字を二分探索で探すなどすればO(length (log length)^2)とかになると思う.
後,実は,一文字ずつ確定して行っても,O(length^1.5)とかになって通るのかもしれない.

C言語のスパゲッティなコード

続きを読む

Beta Round #94 DIV1 A問題/DIV2 C問題 - Statues (この記事を編集する[管理者用])

Source

Codeforces Beta Round #94 DIV1 A問題 (1000pt)
Codeforces Beta Round #94 DIV2 C問題 (2000pt)
Problem description

問題概要

8*8のチェス盤で,最初,自分は一番左下にいる.
いくつかのセルには障害物がある.
毎ターン,
 自分が上下左右斜め障害物のない場所に移動する.もしくは動かない.
 その後,障害物が一斉に1マス下に移動する.自分が潰されたら死ぬ.
一番右上のセルに辿りつけるかどうかを求める問題.

解法

7ターンぐらい生き残れば,障害物はいなくなって,勝てるし,辿り着くまでに7ターンぐらいかかるので,7ターン生き残れなければ勝てない.
全探索なり,DPなりで7ターン後に生き残れているかどうかを調べる.

C言語のスパゲッティなコード

続きを読む

Beta Round #93 DIV2 B問題 - Canvas Frames (この記事を編集する[管理者用])

Source

Codeforces Beta Round #93 DIV2 B問題 (1000pt)
Problem description

問題概要

長さが正整数で100以下の棒がn本 (100以下) 与えられる.
くっつけたり,折ったりできない.
長方形,または,正方形の枠をできるだけ多く作りたい.
何個作れるかを求める問題.

解法

全ての長さに対して,その長さの棒が何本あるか数えて,それを2で割った数だけ,向かい合う辺の棒に使える.
向かい合う辺に使える組の数を2で割ったら答え.

C言語のスパゲッティなコード

続きを読む

Beta Round #93 DIV2 A問題 - Wasted Time (この記事を編集する[管理者用])

Source

Codeforces Beta Round #93 DIV2 A問題 (500pt)
Problem description

問題概要

2次元平面上のn個 (100以下) の点が与えられる.
最初の点から,順番に,最後の点まで,k回 (1000以下) 移動する.
スピードは50.
必要最小移動時間を求める問題.

解法

やるだけ.

C言語のスパゲッティなコード

続きを読む

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

Source

TopCoder SRM216 DIV1 MEDIUM (500pt)
Problem Statement

問題概要

整数n (2以上2*10^8以下) が与えられるので,それを2つ以上の2以上の整数の積で各方法は何通りあるかを求める問題.
順番が違うだけのものは同じとみなす.(x*yとy*xなど)

解法

サンプルにこれが最悪ケースだよと最悪ケースが書いてある.
その答えを見るかぎり全探索で間に合いそうで,実際に間に合う.

C++によるスパゲッティなソースコード

続きを読む

SRM216 DIV1 EASY/DIV2 MEDIUM - RockStar (この記事を編集する[管理者用])

Source

TopCoder SRM216 DIV1 EASY (250pt)
TopCoder SRM216 DIV2 MEDIUM (500pt)
Problem Statement

問題概要

曲の初めは速くて,曲の終わりは速い,そういう曲がff曲 (1000以下) ある.
曲の初めは速くて,曲の終わりは遅い,そういう曲がfs曲 (1000以下) ある.
曲の初めは遅くて,曲の終わりは速い,そういう曲がsf曲 (1000以下) ある.
曲の初めは遅くて,曲の終わりは遅い,そういう曲がss曲 (1000以下) ある.
アルバムに収録するにあたって,
 曲の終わりが速い曲の後ろには,曲の初めは速い曲でなくてはいけなく,
 曲の終わりが遅い曲の後ろには,曲の初めは遅い曲でなくてはいけなく,
 曲の始めが速い曲が1曲でもあるなら,アルバムの最初の曲の初めは速くなければいけない.
最大で何曲アルバムに収録できるかを求める問題.

解法

最初も最後も速い曲とか,最初も最後も遅い曲は,使える時にとりあえず使ってしまえば良い.
後は,シミュレーションでO(曲数)でも,解析的に求めてO(1)でもどっちでも良い.
以下のコードはできるだけ場合分けを少なくする目的でシミュレーション.

C++によるスパゲッティなソースコード

続きを読む

SRM523 DIV2 HARD - SmallBricks31 (この記事を編集する[管理者用])

Source

TopCoder SRM523 DIV2 HARD (1000pt)
Problem Statement

問題概要

問題文の図を参照.
この問題では奥行はすべて1.
最初,幅w (10以下) の土台があって,最高の高さがh以下 (10以下) になるようにブロックを置くパターンの数を mod 1000000007 で求める問題.
使えるブロックは全部高さ1で,幅1以上3以下のものが使用できる.
ブロックを置くときは,置いた場所の両端の下の段にはブロックがなければいけない.

解法

まず,下の段の全ての状態に対して,一つ上の段の置き方を全部列挙する.
後は,今何段目か,一つ下の段の状態,を状態にして,DPする.

C++によるスパゲッティなソースコード

続きを読む

SRM523 DIV2 EASY - AlphabetPath (この記事を編集する[管理者用])

Source

TopCoder SRM523 DIV2 EASY (250pt)
Problem Statement

問題概要

幅50以下,高さ50以下のグリッドが与えられ,各セルは空白かアルファベット大文字が一文字が書かれている.
各26種類のアルファベットは,ちょうど1回だけ,書かれている.
上下左右に隣接しているとして,Aから順番に移動して,Zまで移動する長さ26のパスが存在するかどうかを求める問題.

解法

各アルファベットについて,自分より1つ先のものが隣にあるかどうかを調べた.

C++によるスパゲッティなソースコード

続きを読む

SRM523 DIV1 HARD - AlphabetPaths (この記事を編集する[管理者用])

Source

TopCoder SRM523 DIV1 HARD (900pt)
Problem Statement

問題概要

幅21以下,高さ21以下のグリッドが与えられ,各セルは空白かアルファベット一文字が書かれている.
この問題においては登場するアルファベットは
 A B C D E F Z H I K L M N O P Q R S T V X
の21種類のみを考える.
上下左右に隣接しているとして,グリッド上の長さ21のパスで,全てのアルファベットが1回ずつ出現するものは何パターンあるかを求める問題.

解法

11番目に訪れるセルがどこかで21*21パターン全探索する.
そこから,10マス移動する経路を全列挙し,ちょうど,全て異なる文字を踏んだ組に対して,その数の積を答えに加えていく.
移動する際,後戻りはしないので,大体,O(21^2*3^10)程度でできる.自分はソート使ったのでもう1個logがかかっているが最悪ケースで1秒程度だった.

C++によるスパゲッティなソースコード

続きを読む

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

Source

TopCoder SRM523 DIV1 MEDIUM (500pt)
Problem Statement

問題概要

問題文の図を参照.
この問題では奥行はすべて1.
最初,幅w (50以下) の土台があって,最高の高さがh以下 (50以下) になるようにブロックを置くパターンの数を mod 1000000007 で求める問題.
使えるブロックは全部高さ1で,幅1以上k以下のものが使用できる.
ブロックを置くときは,置いた場所の下の段には全てブロックがなければいけない.

解法

DP.今考えている一番下の段の,一番左のスペースの位置で場合分けする.
その際,それより左をブロックで詰めるパターンの数が必要になるので,それは最初に別途DPで求めておく.

C++によるスパゲッティなソースコード

続きを読む

SRM523 DIV1 EASY/DIV2 MEDIUM - CountingSeries (この記事を編集する[管理者用])

Source

TopCoder SRM523 DIV1 EASY (250pt)
TopCoder SRM523 DIV2 MEDIUM (500pt)
Problem Statement

問題概要

初項a,公差bの等差数列と,初項c,公比dの等比数列を考える.
少なくても片方に含まれる,upperBound以下の整数はいくつあるかを求める問題.
a, b, c, upperBoundは1以上10^12以下.dは10^5以下.

解法

色々場合分けが出てくるので,しっかり確かめながらやる.
等差数列に対しては,割り算で項の数がわかって,等比数列に対しては,upperBoundを超えないものを列挙して,それが等差数列に含まれないなら数える.

C++によるスパゲッティなソースコード

続きを読む

COJ 1591 - King's Poker [KPOKER] (この記事を編集する[管理者用])

Source

The 2011 Caribbean Finals of the ACM-ICPC - Real (Open) (2011-11-10)
COJ 1591 [KPOKER]

問題概要

3枚の数字が書かれたカードが与えられる.
カードに書かれた数字は1以上13以下.
以下の基準で強さを判定する.
 定義:3枚とも同じ数字ならsetといい,2枚が同じ数字で残り1枚が異なるならpairといい,その他はその他という.
 任意のsetは任意のsetじゃないものより強い
 任意のpairは任意のその他より強い
 set同士なら,数字が大きい方が強い
 pair同士なら,揃っている数字が大きい方が強い,同じなら残りの数字が大きい方が強い
 その他同士は,全て同じ強さ
与えられた3枚のカードより強くて,最も弱いカードの組を,カード番号が昇順になるように出力する問題.
存在しないなら*を出力する.

解法

やるだけ.

COJ 1590 - Jupiter Attacks! [JUPITER] (この記事を編集する[管理者用])

Source

The 2011 Caribbean Finals of the ACM-ICPC - Real (Open) (2011-11-10)
COJ 1590 [JUPITER]

問題概要

数列 a0, a1, a2, ..., an に対して,以下の形のハッシュを考える.
 a0 * B^n + a1 * B^(n-1) + ... + an * B^0 mod P
Pは与えられた素数で,Bは与えられた整数.
長さL (10^5以下) の数列で,最初は全部0のものがある.
クエリがN個 (10^5) 与えられるのでそれに答える問題.クエリの形式は以下のとおり.
 クエリ1: 数列のある1つの要素を,ある値に変更する
 クエリ2: 数列の連続する部分列を1つ指定して,そのハッシュを求める.

解法

平方分割で解いた.Segment treeでもOKだと思う.

COJ 1589 - In Braille [INBRAILE] (この記事を編集する[管理者用])

Source

The 2011 Caribbean Finals of the ACM-ICPC - Real (Open) (2011-11-10)
COJ 1589 [INBRAILE]

問題概要

0~9までの点字が問題分で与えられている.
点字を数字に直す,また,数字を点字に直す問題.

解法

やるだけ.

COJ 1588 - Hedge Mazes [HEDGEMAZES] (この記事を編集する[管理者用])

Source

The 2011 Caribbean Finals of the ACM-ICPC - Real (Open) (2011-11-10)
COJ 1588 [HEDGEMAZES]

問題概要

ノード数10^4以下,枝数10^5以下の無向グラフが与えられる.
ノードの組が1000個以下与えられる.
各ノードの組に対して,そのノード間のシンプルなパスがちょうど1つだけかを判定する問題.
シンプルなパスとは同じノードを2回以上通らないパス.

解法

橋のみを通っていけるノード間はシンプルなパスがちょうど1つになる.
橋を列挙してあげて,union findでまとめておくと,すべてのクエリに対してすぐ答えれる.
橋の列挙は例えば,Spaghetti Sourceを参照.

COJ 1582 - Ball Stacking [BALLSTACKING] (この記事を編集する[管理者用])

Source

The 2011 Caribbean Finals of the ACM-ICPC - Real (Open) (2011-11-10)
COJ 1582 [BALLSTACKING]

問題概要

図のようにボールが高さN (1000以下) の三角形状に積み重なっている.
ボールには絶対値が10^5以下の整数が書かれている.
あるボールを取ると,その上にあるボールは全て取らなければいけない.
取ったボールに書かれている整数を最大化したい.最大値を求める問題.

解法

取らなかったボールの和を最小にすることを考える.
取らないボールは,ギザギザした山形のような形にならなければいけないことがわかる.
図を反時計回りに45度回転して,各行に対して,どこまでボールを取ったかを状態にDPしていく.

COJ 1581 - Army buddies [ARMYB] (この記事を編集する[管理者用])

Source

The 2011 Caribbean Finals of the ACM-ICPC - Real (Open) (2011-11-10)
COJ 1581 [ARMYB]

問題概要

1番からS番までの人が左から順番に一列に並んでいる.
B回操作を行うので,各操作に対して答えを求める問題.
 各操作では,LとRが与えられ,L以上R以下の全ての整数kに対して,番号kの人はまだ存在する.
 L以上R以下の全ての整数kに対して,番号kの人を削除する.
 各操作を行った後,L番目より左に存在する最も右の人の番号と,R番目より右に存在する最も左の人の番号を求める.存在しないならそれを指摘する.

解法

リスト構造的なのを使って,自分より左の最も右の人,自分より右の最も左の人を計算する.

Beta Round #93 DIV1 D問題 - Fibonacci Sums (この記事を編集する[管理者用])

Source

Codeforces Beta Round #93 DIV1 D問題 (2000pt)
Problem description

問題概要

フィボナッチ数とは
 1, 2, 3, 5, 8, 13, ...
である.
正整数n (10^18以下) が与えられた時,それを異なるフィボナッチ数の和で書く方法は何通りあるかを求める問題.
テストケースの数は10^5以下.

解法

DP.
とりあえず,与えられた整数をフィボナッチ進数みたいなので適当に書いた表記を計算する.
 19 = 1*13 + 0*8 + 1*5 + 0*3 + 0*2 + 1*1 = 101001(fib)
みたいなの.とりあえず,自分以下の最も大きいフィボナッチ数で引いていくことで得られる.
 連続する2つの1を消し,その一つ上の桁に1を加える.
 1を消し,1つ下と2つ下の桁に1ずつ加える.
という操作ができるので,適当に,上の桁から確定するとして,今何桁目かと,次の桁と次の次の桁の値を状態にしてDPする.
ある桁の値が3以上になる,-2以下になるなどしたら,それより下の桁で調整できないので,そういう状態遷移は行わない.

C言語のスパゲッティなコード

続きを読む

Beta Round #93 DIV1 C問題/DIV2 E問題 - E-reader Display (この記事を編集する[管理者用])

Source

Codeforces Beta Round #93 DIV1 C問題 (1500pt)
Codeforces Beta Round #93 DIV2 E問題 (2500pt)
Problem description

問題概要

n*n (2000*2000以下) のマス目があって,最初は全てのマスが白色.
1回の操作でできることは,あるマス(x,y)を指定して,
 2つの両端を含む線分,(x,x) - (x,y),(x,y) - (y,y) の少なくてもどちらかに属するマスの白黒を反転させる.
ある図形が与えられるので,それを作るのに最小で何回の操作が必要かを求める問題.

解法

操作は,あるマスから対角線まで2本の線分を伸ばしてそこを反転させるもの.
ちょっと考えると,(同じマスを2回選ばないなら)作る方法は1通りしかないことがわかり,それは,greedyにマスを選べば良い.
つまり,一番左下,もしくは,一番右上の反転させなくてはいけないセルを選び反転させる,を繰り返すことになる.
ただし,1回の反転でO(n)かかる愚直なシミュレーションしていくと,O(n^3)になってしまうので,左下と右上の領域は別々に考えて,
現在の行,現在の列は何回反転したか,という情報だけもっておけば,O(n^2)でできる.

C言語のスパゲッティなコード

続きを読む

Beta Round #93 DIV1 B問題/DIV2 D問題 - Password (この記事を編集する[管理者用])

Source

Codeforces Beta Round #93 DIV1 B問題 (1000pt)
Codeforces Beta Round #93 DIV2 D問題 (2000pt)
Problem description

問題概要

長さ10^6以下の文字列Sが与えられる.
Sのプレフィックスであり,Sのサフィックスでもあり,Sから最初と最後の文字を取り除いた文字列の部分文字列でもあるような文字列のうち最長のものを求める問題.
存在しないならそれを指摘する.

解法

候補は最初からk文字とってきた文字列だけなので,候補の数はたかだか10^6ぐらい.
最初からと,最後からと,ハッシュを計算しておく,などをして,先頭k文字と最後k文字が等しいかどうかの判定はO(1)でできるようにしておく.
kをn-1から1ずつ減らして行って,先頭からk文字が条件を満たすか調べていく.
最後k文字と一致していれば,間にそれを含むかどうかは,ローリングハッシュかKMPなどでO(len)かけて良い.
最初と最後が一致するのがたくさんあると,一見O(length^2)になりそうだけど,2つ目は必ず答えになって撃ち切れるのでO(length).
(2011-11-14 17:12追記) 2個目が答えになってる説明 http://twitpic.com/7e3lx1

C言語のスパゲッティなコード

続きを読む

Beta Round #93 DIV1 A問題/DIV2 C問題 - Hot Bath (この記事を編集する[管理者用])

Source

Codeforces Beta Round #93 DIV1 A問題 (500pt)
Codeforces Beta Round #93 DIV2 C問題 (1500pt)
Problem description

問題概要

蛇口1からは温度t1の水が出て,単位時間あたり0以上x1以下の整数だけの量の水を出すことができる.
蛇口2からは温度t2の水が出て,単位時間あたり0以上x2以下の整数だけの量の水を出すことができる.
途中で水の量を変更できない.両方の蛇口から出た水は同じ場所に貯められる.
結果的に温度t0以上で可能な最も低い温度の水をいくらか得たい.
最も早く水を得るために,両方の蛇口から出す水の量を求める問題.
t1はt0以下で,t2はt0以上.
x1, x2は10^6以下.

解法

t1, t2がt0に等しい時はコーナーケースになるので特別に処理する.
後は,蛇口1から出す水の量を1以上の整数を全て試す.
あまり変なことをすると多分誤差で死亡するので気をつける.全部整数でやるとか.
自分がやった方法は,蛇口1から出す水の量y1と,蛇口2から出す水の量y2が決まった時,y1とy2がそれぞれx1,x2を超えない範囲で適当に整数倍する.
そもそも,y1とy2が互いに素じゃない場合は,その組み合わせは以前調べたはずで,飛ばす.
とすると,全く同じ温度になるケースは除外できるので,普通に比較していれば誤差死せずに通る.

C言語のスパゲッティなコード

続きを読む

SRM520 DIV1 EASY/DIV2 MEDIUM - SRMCodingPhase (この記事を編集する[管理者用])

Source

TopCoder SRM520 DIV1 EASY (250pt)
TopCoder SRM520 DIV2 MEDIUM (500pt)
Problem Statement

問題概要

3問のSRMライクなプログラミングコンテストが行われる.制限時間は75分.
 1問目を解くのにかかった時間をtとして,1問目を解いて得られる点数は p[0]-2t 点
 2問目を解くのにかかった時間をtとして,2問目を解いて得られる点数は p[1]-4t 点
 3問目を解くのにかかった時間をtとして,3問目を解いて得られる点数は p[2]-8t 点
どの順番から問題を解いても良いし,解かなくても良い.
各問題を解くのに必要な時間が与えられる.
また,運が与えられ,それを1消費することで,1問選んでその問題を解くのに必要な時間を-1分できる.(必要時間は0以下にはできない)
達成できる最大点数を求める問題.運は100以下.

解法

全探索.
運の割り振り方を全部試して,どの問題を解くかを全部試す.
どの問題を解くかだけ探索すれば,運の割り振り方はgreedyでも良い.

C++によるスパゲッティなソースコード

続きを読む

SRM522 DIV1 MEDIUM - CorrectMultiplication / DIV2 HARD - CorrectMultiplicationTwo (この記事を編集する[管理者用])

Source

TopCoder SRM522 DIV1 MEDIUM (450pt)
TopCoder SRM522 DIV2 HARD (900pt)
Problem Statement (DIV1)
Problem Statement (DIV2)

問題概要

正整数a, b, cが与えられる.
A, B, Cは正整数でA * B = Cが成り立つとき,|A-a|+|B-b|+|C-c|の最小値を求める問題.
DIV1ではa, b, cは10^9以下.
DIV2ではa, b, cは10^6以下.

解法

対称性よりaはbより小さいとする.
答えのAはあんまり大きく成り得ないので,Aがsqrt(10^9)+α程度まで全部調べる.
Bはc/Aの周辺を少しだけ調べれば良い.
Aが大きくならないとか,Bが周辺だけでいいとかは,そうじゃなかったらどうなるかを考えると駄目なことがわかりやすい.(と思う)

C++によるスパゲッティなソースコード (DIV1用)

続きを読む

SRM522 DIV1 EASY - RowAndCoins / DIV2 MEDIUM - RowAndManyCoins (この記事を編集する[管理者用])

Source

TopCoder SRM522 DIV1 EASY (250pt)
TopCoder SRM522 DIV2 MEDIUM (550pt)
Problem Statement (DIV1)
Problem Statement (DIV2)

問題概要

長さn以下のAかBからなる文字列が与えられる.
2人でゲームを行う.順番に行動する.
各ターン,まだ消されていない連続する文字の区間を1つ選び,その区間の文字を消す.(消された両隣の文字の間は空白となり,ひっつかない)
全ての文字が消えるような選択はできない.
一文字だけ残ったときにゲームは終了し,残った文字がAなら先手の勝ち,Bなら後手の勝ち.
先手必勝かどうかを判定する問題.
DIV1はnは14以下,DIV2はnは50以下.

解法

ちょっとした考察で,両端が両方共Aの時のみ先手必勝であることがわかる.
理由は,連続する文字の区間の数を数えた時,自分の区間を1つ増やすか,敵の区間をn+1個消し自分をn個消すか,ぐらいの行動にしか意味が無い.
DIV1はビットマスクを使った探索でも良い.以下のコードはDIV1用で探索している.

C++によるスパゲッティなソースコード (DIV1用)

続きを読む

UVa 12333 - Revenge of Fibonacci (この記事を編集する[管理者用])

Source

Asia Shanghai Regional Semilive hosted by Fudan University (2011-10-23)
UVa 12333

問題概要

40文字以下の整数が与えられる.
f(n)をフィボナッチ数として,f(n)の先頭が与えられた整数となるような最小のnを求める問題.
100000未満のnが見つからなければ,見つかりませんでしたと報告すれば良い.
テストケースの数は50000以下.

解法

最初に,上40+α桁程度のみ残しながらフィボナッチ数を99999項目まで計算する.
後は,それぞれの上1桁~40桁をハッシュか何かに突っ込んでおいて,各ケースに対してすぐ答えが見つかるようにしておく.

UVa 12326 - Yummy Triangular Pizza (この記事を編集する[管理者用])

Source

Asia Shanghai Regional Semilive hosted by Fudan University (2011-10-23)
UVa 12326

問題概要

問題文の図のように三角形をn個 (16以下) 連結に繋げてできる図形は何通りあるかを求める問題.
鏡像反転は違う図形とみなすが,平行移動・回転して一致するなら同じ図形とみなす.

解法

OEISのA006534
多分想定解法は全探索.

Appendix

Recent Articles

ブログ内検索

Ads


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