Latest Entries

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

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

移転 (この記事を編集する[管理者用])

移転しました. http://rsujskf.s602.xrea.com/

SPOJ 16282 - Horace and his primes [TAP2013H] (この記事を編集する[管理者用])

Source

SPOJ 16282 [TAP2013H]
Argentinian Programming Tournament 2013

問題概要

正整数 $n$ に対して,$f(n)$ を $n$ を割り切る素数の和で定義する.
$n$ を $f(n)$ に置き換えていく手順を繰り返すといずれ $n$ は素数になる.
$n$ から始めた時,素数になるまでに必要な手順の数 $+1$ を $g(n)$ とする.
$P$ 個のテストケースが与えられる.
各テストケースでは $A \leq n \leq B$ かつ $g(n) = K$ を満たす $n$ の個数を求める.
$1 \leq P \leq 10^5$
$2 \leq A \leq B \leq 10^6$
$1 \leq K \leq 10^6$

解法

$g(n)$ の最大値は $12$ 程度なので,$1\leq K \leq 12$ に対して,$g(n)=K$ となる $x$ 以下の $n$ の数を前計算しておく.
$f(n)$ の値は篩っぽく求めて,$n > f(n)$ なので,$g(n)$ の値はDPで計算できる.

Timus 1998 - The old Padawan (この記事を編集する[管理者用])

Source

NEERC 2013 Eastern Subregional (2013-10-26)
Timus 1998

問題概要

$n$ 個の石の重さ $w_1,w_2,\ldots,w_n$ が与えられる.
これらの石を順番に空中に浮かすお仕事を行う.
$1$ 秒ごとに $1$ 個の石を空中に浮かべることができる.(まだ浮かべていないうち,番号の若い石から浮かべていく)
ただし,悪友が $m$ 回邪魔してくる.
邪魔してくるタイミングはわかっており, $t_1, t_2, \ldots, t_m$ 秒目に邪魔してくる.
邪魔されると,その秒は石を浮かべることができず,更に,浮かべた石のうち新しい方から
 落とした石の重さが $k$ を厳密に超えるまで(もしくは浮かんでいる石がなくなるまで)
石が落とされる.
全ての石を浮かべるまでにかかる時間を求める問題.
全ての邪魔が行われる前に浮かべ終わることもある.
$1 \leq n, m \leq 10^5$
$1 \leq w_i \leq 10^4$
$1 \leq k \leq 10^9$
$1 \leq t_1 < t_2 \cdots t_m \leq 10^9$ $(t_i < t_{i+1})$

解法

まず,どの段階で邪魔されたらいくつ石が落とされるかをしゃくとりメソッドか二分探索などを用いて求めておく.
後は,イベントが起こるまでの時間を端折りつつシミュレーションすれば良い.

Timus 1997 - Those are not the droids you're looking for (この記事を編集する[管理者用])

Source

NEERC 2013 Eastern Subregional (2013-10-26)
Timus 1997

問題概要

とある店に客が入ってきた,出て行ったというログが $n$ 個与えられる.
どの客が入ってきて,出て行ったかは分からないが,その時間 $t_i$ と,入ってきたのか出て行ったのかがわかる.
すべての客は,$a$ 秒以上滞在するか,$b$ 秒以下しか滞在しないかのどちらかである.
また,必ず $1$ 秒以上滞在する.
また,ログをとる前にいた客や,ログを取った後にいた客などはいない.
ログに矛盾がないかを調べ,矛盾がないなら各客の滞在した時間帯のうち,考えられるものを $1$ つ出力する問題.
$2 \leq n \leq 1000$
$1 \leq a,b,t_i \leq 10^9$
$b+1 < a$

解法

入ってきた回数,出て行った回数が一致しないなら矛盾.
後は,それぞれ入ってきたログと出て行くログが対応付けられるかどうかを調べて2分グラフの最大マッチング.

Timus 1996 - Cipher Message 3 (この記事を編集する[管理者用])

Source

NEERC 2013 Eastern Subregional (2013-10-26)
Timus 1996

問題概要

$n$ 個のバイト($8$ ビット)からなる列 $A$ と,$m$ 個のバイトからなる列 $B$ が与えられる.
何箇所か $A$ の要素のうち最下位ビットを書き換えて良い.
そうして,$A$ の連続する部分バイト列で, $B$ と一致する部分を作りたい.
書き換える最小ビット数と,それで一致させることができる場所を求める問題.
場所は複数あるなら,一番最初のものを求める.
$1 \leq n, m \leq 250000$

解法

$m > n$ なら不可能.
上位 $7$ ビットは全部一致しなければならない.
一致する場所は,ローリングハッシュやKMPを使って求める.
各場所で何文字置き換えなければいけないかはFFTすれば良い.
例えば,$B$ を逆順にして,最下位ビットが $0$ なら $-1$ とみなして,$1$ なら $1$ とみなすなどとすれば,$3$ 回のFFT($A$ で $1$ 回,$B$ で $1$ 回,逆変換 $1$ 回)で計算できる.
一致する場所は $1$,一致しない場所は $-1$ が出てくる.

Timus 1995 - Illegal spices (この記事を編集する[管理者用])

Source

NEERC 2013 Eastern Subregional (2013-10-26)
Timus 1995

問題概要

$n$ 個の荷物があって,順番に重さを量る.
それぞれの荷物の重さ $w_i$ は正整数.
$2$ 個目以降の荷物は,今まで量った荷物で,より軽いものの割合が $p$ %以上あるなら破棄する.
破棄された荷物の数はちょうど $k$ 個であった.
$n,k,p$が与えられるので,重さの総和の最小値と,それを満たす $w_1,w_2,\ldots,w_n$ を $1$ つ求める問題.
$1 \leq k < n \leq 10^5$
$1 \leq p \leq 100$

解法

最初 $n-k$ 個の荷物は全部重さを $1$ にして,最後の $k$ 個は
 前の荷物と同じ重さで破棄されるなら,そうする
 そうでなければ,前の荷物の重さ + 1
とすれば良い.
重さの総和は32ビットに収まらないことに注意.

Timus 1994 - The Emperor's plan (この記事を編集する[管理者用])

Source

NEERC 2013 Eastern Subregional (2013-10-26)
Timus 1994

問題概要

$n$ 人の議員の中に $k$ 人のスパイが紛れ込んでいる.
各ターン以下の行動を行った時,最終的に残るスパイではない議員の人数の期待値の最大値を求める問題.
 1. 各スパイが,スパイでない議員を $1$ 人ずつ殺す
 2. 好きな人数を選び,その人数だけ議員をランダムに選び,議員資格を剥奪する
スパイがいなくなるか,スパイしかいなくなると操作を終わる.
議員資格が無いスパイは活動できない.
$1 \leq n \leq 200$
$1 \leq k \leq \min(20, n)$

解法

$n,k$ を状態にしてDPする.

Timus 1993 - This cheeseburger you don't need (この記事を編集する[管理者用])

Source

NEERC 2013 Eastern Subregional (2013-10-26)
Timus 1993

問題概要

主語,動詞,目的語のみからなる文が幾つか","区切りで与えられる.
主語は()で,動詞は[]で,目的語は{}で囲まれている.
最初の文の最初の文字だけアルファベット大文字で,他のアルファベットは小文字.
ただし,","の後には主語,動詞,目的語以外が挿入されている可能性がある.(カッコで囲まれていない)
それぞれの文を目的語,主語,動詞の順番に並び替えて,最初の文の最初の文字だけ大文字で田を小文字で出力する問題.
文字列の長さは $100$ 以下.

解法

やるだけ.

Timus 1992 - CVS (この記事を編集する[管理者用])

Source

NEERC 2013 Eastern Subregional (2013-10-26)
Timus 1992

問題概要

クエリが与えられるのでそれをこなす問題.
最初クローン $1$ のみがいて,クローンを作った順に $2,3,\ldots$ と番号を付ける.
クエリは以下の $5$ 種類がある.
 learn $c_i$ $p_i$ : クローン $c_i$ が授業 $p_i$ を学ぶ
 rollback $c_i$ : クローン $c_i$ が最後に受けた授業を忘れる
 relearn $c_i$ : クローン $c_i$ が最後に行ったrollbackを忘れる
 clone $c_i$ : クローン $c_i$ と全く同じ状況を持つクローンを新しく作る
 check $c_i$ : クローン $c_i$ が最後に受けた授業を出力する(受けてなければbasicと出力する)
授業を新しく受けた場合,rollbackしてたログは全て削除されrelearnできなくなる.
クエリの数は $5 \times 10^5$ 以下.

解法

クエリ先読みできるので,クエリをクローンの種類 $c_i$ 別に分けておく.
クローンが新しく作られない場合は,スタックとrollbackを何回行われたかを覚えておけば良い.
また,クエリを逆に遡ることは簡単なので,新しくクローンが作られたときは,そのクローンに対するクエリを処理して,逆にさかのぼって戻ってきて,もともとのクローンの処理に戻るといった感じのDFSをすれば良い.
永続データ構造っぽくやっても良い.

Timus 1991 - The battle near the swamp (この記事を編集する[管理者用])

Source

NEERC 2013 Eastern Subregional (2013-10-26)
Timus 1991

問題概要

$n$ 個の場所のそれぞれに $k$ 体のロボットを配置した.
敵対勢力が,場所 $i$ に爆弾を $a_i$ 個送り込んだ.
爆弾 $1$ 個につき,ロボットを $1$ 体破壊できる.
使われなかった爆弾の数と,生き残ったロボットの総数を求める問題.
$1 \leq n, k \leq 10^4$
$0 \leq a_i \leq 10^5$

解法

各場所別々に求めて足す.やるだけ.

Timus 1990 - Podracing (この記事を編集する[管理者用])

Source

NEERC 2013 Eastern Subregional (2013-10-26)
Timus 1990

問題概要

レースのコースが与えられる.
車は $x$ 軸に平行な長さ $W$ の線分として,回転はできず自由に平行移動できる.
スタートからゴールできる最大の $W$ を求める問題.
コースは,左端を表す頂点数 $n$ 折れ線と右端を表す頂点数 $m$ の折れ線が与えられる.
それぞれの折れ線は,$y$ 座標方向に厳密に増え,互いに触れたり交わらない.
また,最初の点と最後の点の $y$ 座標の値は一致しており,そこがスタートライン,ゴールラインである.
スタートラインのどこからスタートしてもよく,ゴールラインのどこにゴールしても良い.
また, $q$ 個のカメラの位置が与えられる.カメラはコースの中か外とかはわからない.
車はカメラにあたってはいけない.
$2 \leq n,m \leq 10^5$
$0 \leq q \leq 10^5$
座標の絶対値は$10^9$以下

解法

折れ線の頂点,カメラのある位置の全ての $y$ 座標について,それを通過できる最大の車幅を求める.
それは,その $y$ 座標での障害物の $x$ 座標の位置をソートして最大の幅の場所を抜ければ良い.
コースの外のカメラは無視することを忘れないようにする.

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

Source

TopCoder SRM598 DIV1 HARD (950pt)
Problem Statement

問題概要

$N$ ノードの木が与えられる.
測定装置を $k$ 個のノードに置く.
各ノードに対して,測定装置からの距離の組を考え,それが各ノードについて異なるようにしたい.(測定結果からどのノードが判断できるようにしたい)
最小の $k$ を求める問題.

解法

まず,$N=1$ なら $k=0$ で良いので,例外処理しておく.
そうでなければ,$1$ 個は測定装置を置かなくてはいけないので,$1$ 個置く場所を全探索して,固定して考える.
測定装置をとりあえずおいたノードを根とした根付き木で考える.
各ノードについて,自分の子供が $2$ つ以上あるなら,それを区別するために,子供からなる部分木のうち,1個を除いて全てのものに測定装置がなければならない.
よって,測定装置を置かなければいけないノードは,子供の方から再帰的にgreedyに求めることができる.

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

続きを読む

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

Source

TopCoder SRM598 DIV1 MEDIUM (550pt)
Problem Statement

問題概要

2人でゲームを行う.最適に行動した時,先手必勝か後手必勝か,永遠に決着がつかないかを判定する問題.
無限に長い一直線上で戦う.
最初,座標 $0$ に先手が,座標 $d$ に後手がいる.
先手の移動力は $M_1$,射程は $R_1$,後手の移動力は $M_2$,射程は $R_2$ である.
各ターン,
 移動力以下だけ離れた場所に移動し,相手キャラまでの距離が射程以下だと勝ち
ということを繰り返す.

解法

$1$ ターン目で先手が勝つ,$2$ ターン目で後手が勝つは,判定しておく.
$2$ ターン目までで決着がつかないなら,移動力が高い方しか勝つ可能性はない.勝てないなら逃げられるから.
移動力が高い方は,好きなように相手との距離を詰めることができる.
近づきすぎると負けるので,相手の移動力 $+$ 射程より $1$ だけ離れた場所に行き,相手が全力で離れた後,$1$ ターンでトドメがさせるかどうかを判定すれば良い.
それができないなら,引き分け.

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

続きを読む

SRM598 DIV1 EASY - BinPacking (この記事を編集する[管理者用])

Source

TopCoder SRM598 DIV1 EASY (250pt)
Problem Statement

問題概要

$N$ 個のアイテムがあり,$k$ 番目のアイテムの重さは $W_k$ である.
$1$ 個のビンには合計で重さ $300$ までのアイテムを入れることができる.
全てのアイテムを入れるためのビンの数の最小値を求める問題.
$1 \leq N \leq 50$
$100 \leq W_k \leq 300$

解法

まず,重さ $100$ のアイテム以外は高々 $2$ 個までしか同じ瓶に入れることができない.
よって,重さ $100$ のアイテムをどれだけ同じビンに $3$ つ詰め込むかを全探索して,残りはgreedyに詰め込めば良い.(以下の解答)
また,重さ $200$ のアイテムは重さ $100$ のアイテムと一緒に詰め込むほうが良いので,各ビンに対して重いアイテムから詰め込めるだけつめ込むというgreedyでも良い.

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

続きを読む

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

Source

TopCoder SRM564 DIV1 HARD (850pt)
Problem Statement

問題概要

m要素 (50以下) の正整数列Aと正整数Nが与えられるので,以下の条件を満たす非負整数列Xは何個存在するかをmod 1000000007で求める問題.
 X[1] XOR X[2] XOR ... XOR X[m] = N (XORはビットごとにXOR)
 0 ≤ X[k] ≤ A[k]
各整数は10^9以下.

解法

一番大きいXの要素の最上位ビットを使うかどうかで場合分けをする.
最上位ビットを使う場合は,そのビットと,Nの対応するビットを反転させて1つ合計ビットの少ない問題に帰着される.
最上位ビットを使わない場合は,その要素は,最上位ビット以外は自由に設定できる.
ので,他要素のXORの最上位ビットがNと一致していれば,後はその要素で調整できる.
なので,最上位ビットだけを状態としてDPして数えれば良い.
小さい状態に帰着していって,すべてのビットがなくなった場合,N=0のときのみ1つ答えがあるのを忘れないこと.(忘れてしまった)

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

続きを読む

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

Source

TopCoder SRM564 DIV1 MEDIUM (500pt)
Problem Statement

問題概要

N個 (100000以下) のボールがあって,それぞれ赤・緑・青のどれかの色をしている.
 赤いボールがあれば赤いボールを1個捨てる
 緑色のボールがあれば緑色のボールを1個捨てる
 青いボールがあれば青いボールを1個捨てる
 以下繰り返し
としたとき,K番目に捨てられたボールが赤であった.
赤・緑・青のボールの数の分布としてありうるのは何通りあるかを求める問題.

解法

今何個目のボールを捨てたか,残ってるボールの種類はどれかを状態としてDPする.
O(色の種類 * N),または,O(2^色の種類数 * N).

本番では,K番目のボールが捨てられた時,残っているボールの種類数が1種類,2種類,3種類で場合分けした.
1種類,2種類の場合は,なくなったボールの種類が使われた個数でループを回して数えた.O(N).
がすぐO(1)にすることもできる.

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

続きを読む

SRM564 DIV1 EASY - KnightCircuit2 (この記事を編集する[管理者用])

Source

TopCoder SRM564 DIV1 EASY (250pt)
Problem Statement

問題概要

W*H (45000*45000以下) のチェス盤を考える.
ナイトを好きなセルにおいて,自由にナイトの動きにそって動かして,元のセルに戻ってくる.
同じセル(最初のセルを含む)を何回訪れても良い.
訪れた(異なる)セルの数の最大値を求める問題.

解法

手を動かして規則を探す.
min(W, H) = 1なら1セルのみ.
min(W, H) = 2なら,(max(W, H) + 1) / 2セル.
W = H = 3なら8セル.(中央以外)
それ以外なら全部のセルを訪れることができる.

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

続きを読む

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

Source

TopCoder SRM586 DIV1 MEDIUM (500pt)
Problem Statement

問題概要

$K$ 個の国がある.($K \leq 26$)
各国は1年は同じ長さで,同じタイミングに都市が始まるが,基準となる年が異なる.(A国の第71年目はB国の第91年目かもしれない)
各国は,それぞれ10人以下の王様がいて,王様の任期はある年の始まりから,ある年の終わりまで.
王様の任期が何年に始まって,何年に終わったかというリストが,その国の年の数え方で与えられる.
過去戦争が起こった記録が,どの国のどの王様と,どの国のどの王様とが戦ったか,という記録のリストが与えられる.
戦争は,1年以内に終わり,年をまたぐことはない.
クエリが50個以下与えられるので,それぞれのクエリに答える問題.
各クエリでは,異なる国の王様の名前が2つ与えられるので,その2つ王様が同時に王様になっていた時期がある可能性があるかどうかを求める.

解法

各国同士の年の数え方がどのぐらいずれている可能性があるか,その最大値と最小値を更新していく.
それは,最短路問題に帰着されるので,ワーシャルフロイドなどで計算できる.
あとは,各クエリに答えるだけ.

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

続きを読む

SRM586 DIV1 EASY - PiecewiseLinearFunction (この記事を編集する[管理者用])

Source

TopCoder SRM586 DIV1 EASY (250pt)
Problem Statement

問題概要

関数 $y = f(x)$ は定義域 $[1, n]$ の区分線形関数.$2 \leq n \leq 50$.
$x$が整数の時 の$f(x)$ の値が整数で与えられ,その間は線分で繋いだものが $f(x)$ となる.
$f(x)$ の値は,$-10^9$ 以上 $10^9$ 以下.
$y$ を何か定数とした時,$y = f(x)$ を $x$ についての方程式と思った時の解の個数の最大値を求める問題.
有限でないならそれを指摘する.

解法

$f(x) = f(x+1)$ となる整数 $x$ があれば,答えは無限.
$y$ の値を端点の周辺のみ調べれば良い.(ただし,$y$ の値は整数だけに限定してはいけない)
$y$ を固定した時,$y = f(x)$ の解の個数は,各折れ線と交わるかを端に注意しながら1つずつ判定していけば良い.(これはDIV2 MEDIUMの問題)
以下のコードでは,値が大きいので無駄に座標圧縮して$y$の値を全部調べた.

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

続きを読む

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

Source

TopCoder SRM599 DIV1 MEDIUM (500pt)
Problem Statement

問題概要

各頂点が格子上の単純な多角形のうち,周の長さが $L$ (整数)のもので,
 (1) 頂点数が最も小さいもの
 (2) その中で,最も長い辺と最も短い辺の長さの差が最も小さいもの
を考える.
最も長い辺と最も短い辺の長さの差を求める問題.
ただし,そのような多角形が存在しないならそれを指摘する.
$1 \leq L \leq 5000$

解法

まず,$L$ が奇数ならそのような多角形は存在しない.
なぜなら, $a^2 + b^2 = c^2$ を満たす整数 $a,b,c$ を考えると,奇数の数は $0$ か $2$ 個であるから,一周回って戻ってきて,周長が奇数になることはない.
また,$L \geq 4$ かつ $L$ が偶数なら,四角形は作れて,$L$ が $4$ の倍数なら正方形,そうでないなら,縦の長さが $1$ だけ長い長方形が作れる.
よって,三角形が作れるかどうかを探索し,最も長い辺と短い辺の長さの差が小さい三角形を見つける問題になる.
そこそこうまく探索すると間に合う.
$L$ が $5000$ 通りしかないので,間に合わない場合は,答えを埋め込んでも良い.

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

続きを読む

SRM599 DIV1 EASY - BigFatInteger (この記事を編集する[管理者用])

Source

TopCoder SRM599 DIV1 EASY (250pt)
Problem Statement

問題概要

$X=1$ から初めて毎ターン以下のどちらか操作を行う.
 素数 $p$ を $X$ にかける
 $X$ の約数を $X$ にかける
$X=A^B$ となるまでの最小ターン数を求める問題.
$2 \leq A \leq 10^6$
$1 \leq B \leq 10^6$

解法

まず,$A$ の素因数は全部操作1で加えておく.
後は,それぞれの素因数は毎回倍々にできる(端数は適当に調整できる)ので,操作2の回数は最も多い素因数に依存する.
操作1の回数,操作2の回数は愚直に調べれば良い.

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

続きを読む

Round #219 DIV1 C問題/DIV2 E問題 - Watching Fireworks is Fun (この記事を編集する[管理者用])

Source

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

問題概要

一直線上に $N$ 個の区画($1,2,\ldots,N$)があり,隣り合う各区画間の距離は $1$ である.
$M$ 回だけ花火が上がる.
$k$ 回目の花火が上がる場所は $A_k$ で,時刻は $T_k$ である.
その花火が上がった時に区画 $x$ にいたなら $B_k - |A_k - x|$ だけ満足度が得られる.(負もありうる)
単位時間あたり $D$ だけ移動できるとして,得られる満足度の和の最大値を求める問題.
ただし,花火の上がる時間には,区画のどこかにいなければいけない.また,花火は同時に複数上がる場合がある.
$1 \leq N \leq 150000\ (1.5 \times 10^5)$
$1 \leq M \leq 300$
$1 \leq D \leq N$
$1 \leq A_k \leq N$
$1 \leq B_k \leq 10^9$
$1 \leq T_1 \leq T_2 \leq \cdots \leq T_M \leq 10^9$

解法

DPする.状態は 最後に上がった花火と最後に花火を見た場所 にして それまでの満足度の最大値 を計算する.
その際,状態を更新するのにある区間にある最大値というのが必要になる.
スライド最小値や,Range Minimum Queryを使う.

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

続きを読む

Round #219 DIV1 B問題/DIV2 D問題 - Counting Rectangles is Fun (この記事を編集する[管理者用])

Source

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

問題概要

$N \times M$ のサイズのグリッドが与えられる.それぞれのセルには $0$ か $1$ が書かれている.
$Q$ 個のクエリが与えられる.
各クエリでは,長方形領域が与えられるので
 その長方形領域に含まれる長方形領域の中で,セルが全部 $0$ となるようなものの数
を求める.
$1 \leq N, M \leq 40$
$1 \leq Q \leq 3 \times 10^5$

解法

クエリの数を考えると最悪ケースでほぼすべてのパターンのクエリが来うるので,最初に全部の長方形領域に対して答えを計算しておく.
まず,ある場所より左上にある $0$ の数とか,そういうのは,縦に横に累積和を取ったり,包除原理を用いたりで $O(\mbox{セルの数})$ 計算できる.
全部 $0$ となるような長方形のうち,左上の場所 $(r_1, c_1)$ を決めつける.
右下の座標としてvalidがどうかを判定する.それは,左上に $1$ がある場所の数が $0$ 個であれば良い.
次に,ある座標 $(r_2, c_2)$ より左上に右下とvalidな座標の数を同様の方法により数える.
後は,その数を,左上 $(r,c)$,$(r \leq r_1,\ c \leq c_1)$,右下 $(r_2,c_2)$ に対応するクエリの答えに足していく.
$O(N^3 M^3)$.
他にもいろいろな方法があるらしい.

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

続きを読む

Round #219 DIV1 A問題/DIV2 C問題 - Counting Kangaroos is Fun (この記事を編集する[管理者用])

Source

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

問題概要

$N$ 匹のカンガルーがいて,$k$ 番目のカンガルーの大きさは $S_k$.
それぞれのカンガルーは $1$ 匹まで他のカンガルーを自分の袋の中に入れることができる.
ただし,袋に入れることができるのは,自分の半分の大きさ以下のカンガルーのみで,袋の中に入ったカンガルーは袋の中にカンガルーを入れていてはいけない.
袋の中に入っていないカンガルーの数の最小値を求める問題.
$1 \leq N \leq 5 \times 10^5$
$1 \leq S_k \leq 10^5$

解法

袋の中に入るカンガルーの数を最大化する.
答えを決めつけると,袋を提供するカンガルーはできるだけ大きいものを,袋に入るカンガルーはできるだけ小さいものを選べば良い.
よって,二分探索で答えを決めつけると,greedyにそれより大きいかどうかが判定できる.(以下のコード1)
また,袋の中に入るカンガルーは最大 $N/2$ 匹程度で,小さい方から半分は袋に入る側,大きい方から半分は袋を提供する側と分類してgreedyにマッチングしていっても良い.(以下のコード2)

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

続きを読む

ARC 009 D - 覚醒ノ高橋君 (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #009
問題文

問題概要

ノード数T,枝数Mの無向グラフが与えられる.
同じノード間に枝はたかだか1本で,枝には,その枝を壊すコスト(1以上77以下)が付けられている.
ノードはA個 (77以下) の集合にわかれていて,枝は同じ集合に属すノード間にしかない.
各集合に属すノードの数は7以下.
k個の集合に属すノードの数をS[k]とすると,S[k] * (k-1)の和がA-1になっている.(解法1行目参照)
全域木にする方法が幾つか考えられるが,それをコスト順にソートして,コストが小さい方からk番目 (7777777以下) のもののコストを求める問題.
k通りも存在しないならそれを指摘する.

解法

結局は,それぞれの集合に対して,全域木にすれば,全体で全域木になるようになっている.
それぞれの集合に対して全域木を列挙してあげて,使う枝の合計コストcでできる全域木の数をカウントしておく.
(使わない枝のコストは大きくなるので,使う枝のコストを求めて,最後に全体の枝のコストから引く)
後は,DPで,全体のコストcでできる全体の全域木の数を求める.

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

続きを読む

ARC 009 C - 高橋君、24歳 (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #009
問題文

問題概要

要素数Nの置換Sで,S[i]=iとならないものがちょうどK個であるものの数をmod 1,777,777,777 (素数) で求める問題.
N, Kは2以上,8以下で40点.
Nは777,777,777,777,777,777以下,Kは777,777以下で100点.

解法

どの集合がS[i]=iとなってないかを選ぶ方法はC(N, K)で,これはN, N-1, ..., N-K+1をかけて,1, 2, ..., K で割ればよいのでO(K)で求められる.
すべてのiについて,S[i]=iとならない要素数Kの置換の数A[k]は漸化式があって,A[k] = (k-1) * (A[k-1] + A[k-2])などを用いればO(K).

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

続きを読む

ARC 009 B - おとぎの国の高橋君 (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #009
問題文

問題概要

数字 (0~9) の大小関係が与えられる.ただし0は一番小さい.
その時に整数を昇順ソートする問題.
整数を比較するとき,その整数の左には無限に0が詰まってると思い,最も左の桁で最初に違う数字をみて比較する.

解法

大小関係に対応するように数字を置き換えてソートして元に戻す.

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

続きを読む

ARC 009 A - 元気にお使い!高橋君 (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #009
問題文

問題概要

N種類の品物を買う.(Nは10以下)
品物iはa[i]個買いたくて,1つあたり税抜でb[i]円. (a[i]は10以下,b[i]は1000以下)
消費税を5%として,必要な金額を求める問題.
消費税は合計金額にかかり,小数点以下は切り捨て.

解法

やるだけ.

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

続きを読む

ARC 012 D - Don't worry. Be Together (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #012
問題文

問題概要

$N$ 人の人が,二次元平面上の格子点 $(x_i, y_i)$ にいる.
各ターン,各自が上下左右のいずれかの方向に $1$ だけ進む.
$T$ ターン後に,全員が $(0,0)$ にいるような進み方は何通りあるかを ${\rm modulo}$ で割った余りで求める問題.
$N \leq 100000 = 10^5$
$T \leq 100000 = 10^5$
${\rm modulo} \leq 1000000007 = 10^9 + 7$
部分点もあるが,略.

解法

各人が動く方法のパターン数をかければ良い.
まず,初期位置 $(x_i,y_i)$ と $(0,0)$ までの距離の偶奇が $T$ と一致しないなら $0$.
一致していれば,パターン数は\[ \begin{pmatrix}T \\ (T+x_i-y_i)/2 \end{pmatrix} \begin{pmatrix}T \\ (T+x_i+y_i)/2 \end{pmatrix} \]となることが観察できる.
(証明には,無駄な移動を上下か左右にいくら割り振るかで場合分けして,二項係数の積の和などに持ち込んで,Vandermonde's identityを使う)
${\rm modulo}$が素数の時(部分点にある)は,階乗の値を前計算しておいて,二項係数を求めれば良い.
満点を狙うには,$N$ 人通して累計で,各数字の階乗が何回使われたをメモる.(割り算は $-1$ 回とカウント)
後は,各階乗から,累積和を使って,各整数を何回かければ良いかを,求め,
各整数について,素因数分解したものを前計算しておいて,各素数を何回かければ良いか,まで落とす.
後は,かけていきながら,${\rm modulo}$ で余りを取る.

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

続きを読む

ARC 012 C - 五目並べチェッカー (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #012
問題文

問題概要

19*19の碁盤の上で行う,五目並べの盤面が与えられた時,その盤面が正常な状態であるかどうかを判定する問題.
ルールは,oが先手,xを後手として,交互にマークを書いていって,タテ・ヨコ・ナナメどれかに5つ並べたら終了.
それ以外のルールはないものとして扱う.

解法

まず,oとxの数を数えて,
 oの数 = xの数 + 1 なら最後に o が置いた
 oの数 = xの数 なら最後に x が置いた
 それ以外なら不正
とする.
すでに,5つ並んでいるなら,それは最後においた人でなければならない.
また,5つ並んでいるなら,どれか1個を取り除くと,5つ並ばないような状態にできなければならない.
とチェックしていく.
盤面のサイズが小さいので,取り除く石は全部確かめて計算しなおせば良い.

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

続きを読む

Appendix

Recent Articles

ブログ内検索

Ads


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