ホームに戻る

TopCoder SRM div2 Hard 100問100答

0、はじめに

div2 Hard は難易度的には div1 medium より簡単なイメージ。

SRM div2 Hard を 500 から 599 までやってみました。
どんな傾向があるかを探ってみます。

これ以降の記述の利用方法としては、

・問題の意味を簡単に知りたい。
・どんな問題がでるかの傾向を知りたい。
・各問題のジャンルを大雑把に知りたい。
・各ジャンルのおすすめ問題を知りたい。
・各問題の解き方の考え方を知りたい。

以上で利用できるかと思います。

1、傾向分析

ジャンルを以下の7ジャンルに分けてみます。

・実装問題(34問)
・動的計画法(43問)
・数学問題(5問)
・確率、期待値(5問)
・幾何の問題(7問)
・グラフ(7問)
・数え上げ(4問)

実装は総当りや貪欲、シミュレーションなど。
動的計画法はそのまま動的計画法を使うもの。
数学問題は素数や約数を使って解くような問題。
確率、期待値はそのまま確率、期待値を求める問題。
幾何は図形などを使った問題。
グラフはグラフ構造を使った問題。
数え上げは n! や nCr を使うような問題

以上のように決めました。

総和が 100 を超えるが重複も含めるため。

傾向をみると動的計画法の頻度が桁違いに高いことがわかる。
数え上げの問題の頻度が少ないことからも、
計算が間に合わないと思えば動的計画法が解法である確率が高い。
問題を見たらまず動的計画法と思え、と言っても過言でない。

次に多いのは実装問題である。
制約を見て時間が間に合えば実装問題と判断しても良い。
div1 の問題の制約をゆるくしたものが出題されることが結構あり、
この場合、制約がゆるいために処理時間としては余裕で回ってしまう場合が多い。
ただ、実装は時間のかかる難しいものなので簡単では無い。

数学問題、確率、期待値、幾何の問題、グラフ、数え上げに関しては、
そのジャンルというだけで難しい問題といっても良い。
どのようなアプローチがあるかを知っておかないと難しい。

たまにすごく簡単な問題が出ることがある。
以下のような問題は単純では無いが少し考えればできるし実装も簡単。

SRM503、SRM512、SRM522、SRM551、SRM598

とりあえず問題を読んでおいて損は無い。

以下、各ジャンルで学習効率の高そうなおすすめ問題をピックアップしてみました。
上から簡単な問題であるように並べてあります。

2、実装問題のおすすめ問題

SRM529:
いっけん法則性がまったくわからない問題。
とりあえず簡単な例を書き出してみて方向性を探るのはとても有効。

SRM514:
巨大な文字列をあたかも扱うかのような問題。
メモリの制限でひっかかるので実装で補う問題。

SRM525:
文字を3×3のマスに当てはめる実装。
高速化の工夫もよくある方法なので勉強になる。

3、動的計画法のおすすめ問題

SRM551:
びっくりするぐらい基礎の問題。
はじめて動的計画法を練習するにはもってこい。

SRM502:
動的計画法の基礎の問題を少し難しくした問題。
動的計画法はどうしたら難易度を足せるか?が垣間見える問題。

SRM597:
ビットを使った動的計画法の問題。手順は複雑だが決して発想が必要な問題では無い。
この実装を音をあげずに着実にできたらかなり上級者だと思う。

4、数学問題のおすすめ問題

SRM577:
最大公約数を使う問題。
数学問題のなかでもまだ意味がわかりやすい。

SRM540:
無限小数を判定する問題。
有限小数の判定に置き換えて考えればすこし簡単になる。

SRM510:
b進数について考える問題。
場合分けのやりかたなど非常に難解。

5、確率、期待値のおすすめ問題

SRM518:
期待値の計算のみを使う問題。ただ、発想は難しい。
期待値の問題は難しいようにみえて結局公式通りであることが多い。

SRM537:
期待値の計算のみを使う問題。
この問題も期待値の公式に従って考えれば解ける。

SRM533:
最善の戦略をとる場合の動的計画法も使う期待値の問題。
よくありそうな問題なのでやり方を覚えておきたい。

6、幾何のおすすめ問題

SRM521:
幾何では本当によくありそうな問題。
座標を2倍したり±1で探索したりは本当によくある。

SRM528:
判定タイミングと誤差対策が難しい問題。
これを正解できればかなりの勉強になると思う。

SRM565:
幾何の分野では外積と面積計算を使う問題。
加えて動的計画法も使うのでかなり難易度は高い。

7、グラフのおすすめ問題

SRM531:
最小全域木の求め方について知っていればできる問題。
その前にグループの結合も考えないといけない。

SRM549:
基本的には動的計画法の問題。
動的計画法を使って閉路の除去というのは面白い。

SRM570:
グラフを探索しながら作成して計数する問題。
基本的なグラフの操作のやり方が練習できる良い問題。

8、数え上げのおすすめ問題

SRM586:
問題を解く発想はそれほど難しく無い。
nCr の計算と n! の計算が正しくできれば解ける。

SRM584:
基本的には動的計画法の問題。
動的計画法の更新のときに nCr を用いる。

SRM565:
動的計画法で解くのか数え上げなのか迷う問題。
状態を数え上げとみなす発想も必要。

9、全100問についての簡単なコメント

SRM500:
数学問題。裏技を使えば少し楽。
SRM501:
比較的やさしめの動的計画法。
SRM502:
比較的やさしめの動的計画法。
SRM503:
実装問題。簡単。
SRM504:
実装問題。逆シミュレーション。
SRM505:
実装問題。発想が難しい。
SRM506:
実装問題。迷路探索と総当り。
SRM507:
動的計画法+ある法則について知らないと解けない。
SRM508:
動的計画法。普通にやると間に合わない。
SRM509:
比較的やさしめの動的計画法。
SRM510:
数学問題。発想で処理を削る問題。
SRM511:
比較的やさしめの動的計画法。
SRM512:
実装問題。簡単。やるだけ。
SRM513:
やるだけだが実装が難しい。
SRM514:
発想を変えると解きやすくなる。
SRM515:
動的計画法と期待値。
SRM516:
やるだけだが実装が難しい。
SRM517:
動的計画法。発想が必要。
SRM518:
期待値の問題。期待値に詳しくないと難しい。
SRM519:
一見難しいが、わかれば簡単。
SRM520:
比較的やさしめの動的計画法。
SRM521:
幾何。いかに探索をかけるかがポイント。
SRM522:
実装問題。無駄なループを削る努力をする。
SRM523:
典型的な動的計画法。
SRM524:
探索。ただし、数学的な考え方が必要。
SRM525:
総当り。文字列をそのまま使うと時間が足りない。
SRM526:
動的計画法。いわゆる桁DPができれば簡単。
SRM527:
貪欲。簡単。
SRM528:
幾何。探索を工夫し、誤差で落とさない注意が必要。
SRM529:
そのままやると時間が足りない。法則を見つける問題。
SRM530:
グラフ。考え方に工夫が必要。
SRM531:
基本的なアルゴリズムを使うグラフの問題。
SRM532:
動的計画法。2次元のやり方を知っていれば解ける。
SRM533:
動的計画法を使う期待値の問題。
SRM534:
メモリの節約を考える動的計画法の問題。
SRM535:
動的計画法の問題。いわゆる桁DP。
SRM536:
順番を考える動的計画法。
SRM537:
期待値の問題。
SRM538:
実装問題。
SRM539:
発想の問題。実装は簡単。
SRM540:
数学問題。問題はややこしいが計算自体は簡単。
SRM541:
実装問題。ただ普通にやると落とす。
SRM542:
期待値の問題。
SRM543:
幾何の問題。
SRM544:
動的計画法の問題。メモ化再帰を使うとやりやすい。
SRM545:
幾何の問題。
SRM546:
実装問題。場合分けに注意。
SRM547:
動的計画法。ビットDP。
SRM548:
動的計画法。桁DP。
SRM549:
グラフを使った動的計画法の問題。ビットDP。
SRM550:
実装問題。
SRM551:
比較的やさしめの動的計画法。
SRM552:
法則を見つける問題。
SRM553:
少し発想のいる動的計画法。
SRM554:
典型的な動的計画法。
SRM555:
少し変わった動的計画法の問題。
SRM556:
実装問題。
SRM557:
難しい動的計画法。
SRM558:
実装問題。ある方法を知らないとできない問題。
SRM559:
実装問題。
SRM560:
実装問題。
SRM561:
グラフの問題。
SRM562:
典型的な確率を使った動的計画法。
SRM563:
すこし考える動的計画法。
SRM564:
実装問題。
SRM565
数え上げ。発想が難しい。
SRM566
幾何と動的計画法。
SRM567:
動的計画法。メモ化再帰。
SRM568
期待値の問題。期待値に詳しくないと難しい。
SRM569
動的計画法。
SRM570
グラフの問題。
SRM571
グラフ探索。
SRM572
動的計画法と数え上げ。
SRM573
典型的な動的計画法。
SRM574
実装問題。
SRM575
動的計画法。
SRM576
実装問題。全探索。
SRM577
数学問題。
SRM578
動的計画法。
SRM579
幾何の問題。
SRM580
比較的やさしめの動的計画法。
SRM581
グラフの問題。
SRM582
実装問題。全探索。
SRM583
実装問題。全探索。
SRM584
動的計画法と数え上げ。
SRM585
幾何の問題。
SRM586
数え上げ。
SRM587
実装問題。
SRM588
動的計画法。
SRM589
実装問題。
SRM590
動的計画法。
SRM591
動的計画法。発想が難しい。
SRM592
難しい動的計画法。
SRM593
動的計画法。発想が難しい。
SRM594
実装問題。
SRM595
実装問題。
SRM596
実装問題。
SRM597
動的計画法。
SRM598
簡単。やるだけ。
SRM599
動的計画法。

10、問題の簡単な説明と考え方のヒント

SRM500

b1*q1^i(0<=i<n1)、b2*q2^i(0<=i<n2)

上の2つの式で生成される数字はいくつか?
重複は取り除く。

考え方1:

b1,b2 ともにスタートし小さいほうに q を乗算する。
値が等しければカウントする。
オーバーフローしないように適宜 gcd をとる。
オーバーフローしたら終了する。
n1+n2 からカウントを引き算する。
b や q が 0 や 1 のケースのみ例外として書く必要がある。

考え方2:

計算結果を 1000000007 で割った値を set に入れていく。
ただし、1000000007 のみではたまたま重複する場合がある。
例えば 3 と 1000000010 が重複する。
回避するために 1000000007 と 1000000009 の2通りで行う。
両方重複すれば真の重複と判定し、片方なら偽の重複である。
2通りでも 1/(1000000007*1000000009) の確率で重複するが、
システムテストは通過する。

SRM501

-1 がワイルドカードである配列がある。
ワイルドカードに適当な値を入れていく。
次の2つの条件を満たす配列は何通りか?

A[i] <= (A[0] + A[1] + ... + A[i-1]) / i (1 <= i < N)
A[i] > A[i+1] > A[i+2] (0 <= i < N-2)

考え方:
動的計画法
dp[項数][総和][前回が減少か?のフラグ]
総和を見ながら1つ目の条件をチェック
前回が減少か?のフラグを見て2つ目の条件をチェック

SRM502

0からN-1番の牛がK匹逃げた。
牛の番号の総和がNで割り切れる牛の番号の組み合わせはいくつ?

考え方:
動的計画法
牛は48匹以上は数える必要は無い。
また総和は %N で記録すること。
番号は 0 と 1 を入れ替えて更新していくこと。 
dp[番号][逃げた匹数][総和%N]

SRM503

XY座標上にCityとVillageがある。
VillageはCityと繋げるとCityになる。
すべてのVillageをCityに繋げてCityにする最短距離は?

考え方:
Cityからの距離が短いVillageから繋げていく。
Cityに繋がったVillageはCityとして考える。
距離の計算は long long にしないと落ちるので注意。

SRM504

InputからOutputに変換するルールが与えられる。
OutputからInputを逆算せよ。

考え方:
右下から左上に処理を行う。
妥当性のチェックと逆操作を分けて考えるとやりやすい。
答えは辞書順なので W or B なら B を入れる。

SRM505

W*Hの不規則な間隔のグリッドがある。
1つのグリッド内の面積がわかっていると'Y'である。
全体の面積を推測するには最低あといくつ'Y'が必要か?

考え方:
すべての縦横グリッドについて
隣り合うグリッドの比の関係がわかれば良い。
隣あう2つのグリッドが'Y'同士であれば連結できると考える。
縦の連結を 0〜h-1 横の連結をh〜h+w-1 とする。
memo[h+w][h+w]を用意して連結を調べていく。
連結していなければカウントして連結を増やす。

SRM506

スライムを全て倒すための最少の歩数を求めよ。
ただし数字nのスライムはn歩歩くと復活する。 

考え方:
スライムは最大9匹しか倒せない。
10匹以上いたら不可能なので -1 を返す。
bfs で2地点の最小距離のリストを作る。
スライムを倒す順番は9!なので総当りできる。

SRM507

四角形が無限の1直線上にある。
四角形が落ちる穴が数箇所ある。
四角形は1回でちょうどn^2転がすことができる。
スタートからゴールに着くまで最小何回転がすか?

考え方:
穴がスタートとゴールの間にある場合は不可能 -1。
穴が両端に存在する場合は幅優先探索で動的計画法。
穴が片側の場合は、
g-s == n^2 のとき1回でゴール
(g-s)%4 != 2 のとき2回でゴール
(g-s)%4 == 2 、g-s == n1^2+n2^2 のとき2回でゴール
それ以外は3回でゴール
n^2 の移動法について知らないとできない問題

SRM508

以下の条件を満たす組み合わせを求めよ。

ちょうどN個の整数で、すべての値はR以下。
A0+A1+...+AN-1 = A0|A1|...|AN-1 を満たす。

考え方:
N 個の整数が各ビット桁で 1 を重複しなければ良い
個数、全ビットの動的計画法を行う。
途中で値が R 以下であるかどうかをチェックする。
ただし 10*(1<<14)*1500 のループは大きすぎる。
よって、R のループを現在のビットについて、
ビットマスクを用いながら更新する必要がある。
ビットマスクを用いた部分集合の列挙。
for(int i = m; i &gt;= 0; i--){
  i &amp;= m;
  //処理
}

SRM509

数字nが描いてある床は1回で上下左右にn進める。
'.'の床は0から9をK回まで描いて移動してよい。
スタートからゴールまでの最小回数を求める。

考え方:
X位置、Y位置、回数Kでの動的計画法。
特に工夫は必要無い。

SRM510

数字nが与えられる。
b進数にしたとき4と7のみで表示できるbは何通りか?

考え方:
nが最大10^12なので10^12のループが必要になるが回せない。
4*b+7など2桁の場合はbが逆算できるので、
4*b+4、4*b+7、7*b+4、7*b+7の4通りは逆算で確認。
nがb進数で2桁以下なのはn<b*bのとき。
よってn>=b*bであるbで全ループして3桁以上を確認。
すると最大10^6のループで足りる。

SRM511

数字を交互に選択する対戦ゲーム。
カードをひくたびに数字のORをとっていく。
カードがひけないか、511になってしまったほうの負け。
どちらが勝つかを答えよ。

考え方:
ビットの状態と順番での動的計画法。
dp[1<<9][2]で可能。
メモ化再帰を使うとやりやすい。

SRM512

2人で両手じゃんけんをする。
両手で勝てば2点。
右手が勝ちで左手があいこなら1点。
候補を組み合わせてAshの得る最高を求めよ。

考え方:
2点の組み合わせを先に総当り。
その後1点の組み合わせを総当り。

SRM513

図のように切り分けて最高点を得るには?

考え方:
サイズが最大4×4なので総当りできる。

SRM514

次の法則にしたがって
'0'と'1'からなる文字列を生成する。

0 <= i < K, A[i] = first[i]. 
A[i] = A[i-1] + A[i-K-1] + A[i-2K-1] + ... 

指定した範囲にある'1'の個数を求めよ。

考え方:
メモリが足らないので文字列を作成してはならない。
i番目の文字列が何文字あるのかを記録していき、
x番目の文字がもともとどの文字列の何番目の文字なのか遡る。
x番目の文字が'0'か'1'を得る関数を作成すると楽。
指定した範囲でループして'1'の数を数える。

SRM515

1個の商品をAとBの2人が買いに来る
各々来る時間と確率と買う値段が決まっている。
来るのは1人1回限りで2人同時には来ない。
より高く売ろうとするとき売り上げの期待値を求めよ。

考え方:
期待値で使用する確率は次のように求める。
1時20%、3時30%、5時10%のとき、
3時の期待値のための確率は30/80である。
そのまま30/100を用いないこと。
客が来る場合、
E'= max(来た客が買う値段,以降のもう1方の客の期待値)*来る確率
客が来ない場合、
E''= 以降の来た客の期待値*(1-来る確率)
「以降の」が必要になるため動的計画法を後ろから用いる。
E = E'+E'' を更新する。
dp[時間][Aが来たかどうか][Bが来たかどうか]

SRM516

1つの文字列が分裂した複数の文字列があるので復元せよ。
ルール1:1つの文字は1回しか使わない。
ルール2:文字の順番を変えてはいけない。
考えられる辞書順で最初の文字列を答えよ。

考え方1:
とくに処理時間が足らなくなることはないので直感的にやる。
前の文字列に対して新しい文字列を挿入していく。

考え方2:
ある文字の次にある文字がくるというグラフを作る。
あとはトポロジカルソートする。

SRM517

複数の芝の初期値と1日伸びる長さが与えられる。
次の日からどれか1本だけカットし長さを0にできる。
目標の長さH以下にできるのは最小で何日後か?

考え方:
順番を考慮すると50!になり不可能。
芝の伸びる速度の遅い順に切れば良いことに注目。
例えば、1と2伸びる芝が1本ずつあったとき、
2→1の順では4しか短くできないが、
1→2の順であれば5短くできる。
よって、まずgrowの値でソートする。
growの小さいものから切るか切らないかで動的計画法。
dp[芝の番号][切った本数]
日数ごとに短くできる芝の最大値を覚えておき、
その日数での芝の長さの総和から引いたものを判定。

SRM518

N枚のコインが表を向いている。
次にa枚ずつランダムに裏返す。
試行を終えたとき、表の枚数の期待値は?

考え方:
表の期待値=裏の期待値*裏が表になる確率
            -表の期待値*表が裏になる確率
よって、 E = E + (N-E)*a/N - E*a/N でできる。

SRM519

カードを使ってAからBの数字を順に表示する。
2のk乗のカードを裏返して更新する
更新は数の大きいカードから順に行う。
6から8の更新では
2、4 で「6」
1、2、4 で「7」
1、2、4、8
1、2、8
1、8
8 で「8」
の順に行う。
途中経過で最も大きくなる数字はいくつか?
上の例では1+2+4+8=15が答え

考え方:
long long 値を使って考えると大きい数字で間に合わない。
よってビットを使って考える。
このときAとBでビットを上位から探索
要は繰り上がりのときにそれ以降がすべて'1'が発生するので、
B = '1' A = '0' になる地点があればそれ以降は '1' にする。 

SRM520

YとNからなるリストが与えられる。
Yには「Passed」か「Challenged」か「Failed」が入る。
列ごとに次のルール
「Passed」の数は優先して降順に。
「Passed」の数が等しいとき「Challenged」の数は降順になる。
考えられる「Passed」「Challenged」「Failed」の入れ方は?

考え方:
典型的な動的計画法の問題
dp[列の数][Passedの数][Challengedの数][Failedの数]

SRM521

XY平面に複数の座標がある。
1辺の長さがわかっている正方形で座標を囲う。
ただし正方形は必ずXY軸に平行であること。
囲うことのできる座標の組み合わせはいくつか?

考え方:
座標はせいぜい50個なので、
X、Y座標のすべての組み合わせの点で
その付近の点をすべて総当りする。
正方形を0.5の位置配置できるので注意。
例えば(-1,0)(0,0)(1,0)で正方形の1辺が1のとき、
(0,0)のみで囲うことは可能。
座標をすべて倍にして考えるなどが必要。

SRM522

a*b=cが成り立つようにしたい。
しかし、a,b,cの値が適切でない場合がある。
それぞれa,b,cの値を加算減算してA*B=Cを作った。
|A-a|+|B-b|+|C-c| の最小値を求めよ。
ただし、A,B,Cはそれぞれ正の整数である。

考え方:
Aですべての値を総当りする。
Aが定まればBとCの調節をするだけだが、
CにあわせるようにBを動かしたほうが有利であるので、
Aからまず目標とするCを定め次にBを求める。

SRM523

1*1、1*2、1*3のブロックを横にして積んでいく。
このとき幅wと高さhが指定されている。
ブロックの下にブロックが無く浮いた状態は許されない。
ただし、1*3のブロックのみ中央の下に無いことは許される。
ブロックの積み方は何通りか?

考え方:
動的計画法。
ブロックがあるかどうかでビットで記録していく。
まず1段目の置き方をビットごとに数える。
例えば、w=3のとき 001 は1通り 011 は2通りなど。
2段目以降は1段下の場合のビットを見ながら更新。

SRM524

指定された数字を使わずにNの最小の倍数を求めよ。
ただし、9桁以上の場合には次の記法に従う。
1234567890 のとき 123...890(10 digits) のようにする。

考え方:
下の桁から幅優先探索を用いて更新する。
ただし、1度でた余りは2度使わなくても良い。
N%a==N%b であれば N%(10*a+y)==N%(10*b+y) であるため。
この方法を用いないと時間が足りない。

SRM525

縦横の文字列が3つ与えられる。
順に文字列を切って3×3のマスに入れていく。
空のマスもあって良いものとする。
成立するパターンは何通りか?

考え方:
上の2列を総当りする。
下の1列は縦を見て自動的に決まる。
3列目が正しければ1カウントする。
ただしループ内で文字列処理すると間に合わない。
よって以下のメモを作っておく。
memo[文字列A][文字列B][Aの位置][Bの位置][文字列の長さ]
これは3*3*51*51*51で作成できる。

SRM526

ラッキーナンバーの点数は桁の数字をみて、
絶対値|4の個数ー7の個数|で決める。
4 は1点、44 は2点、47 は0点、56 は0点となる。
ある数からある数までの点数の合計を求めよ。

考え方:
上の桁から動的計画法を行う。
最上位桁が上限に引っかかるかそうでないかでフラグを立てる。
例えば、3400 が上限値であれば、
最上位が 3 のとき次の数字は 0-4 までしか使えない。
最上位が 0-2 であれば次の数字は 0-9 まで使える。
この状態を動的計画法のフラグで記録していく。
いわゆる「桁DP」の問題。
更新しながら4と7の数を数えていく。
dp[桁の数][4の個数][7の個数][フラグ]

SRM527

2のn乗までの通貨しか無い世界がある。
例えば n = 3 であれば 1,2,4 という通貨があることになる。
count 枚で通貨の価格の合計が sum になるようにせよ。
ただし、できるだけ大きい数字の通貨を使え。

考え方:
まずできるだけ大きい数値の通貨で合計金額を作る。
枚数を増やすには大きい数値の通貨から切り崩せばよい。

SRM528

1直線上に蚊の初期位置と速度が与えられる。
1点に爆弾を置いて前後 R の距離の蚊を退治する。
一度により多くの蚊を退治するときそれは何匹か?

考え方:
例えば蚊の位置が 0.07 だとか 時間が 0.2 だとか、
爆弾を置く位置が 0.5 だとか整数に限られない。
よって、次のような総当りをかけるべきである。
時間0とすべての蚊の接触する時間を配列に入れる。
その時間においてすべての蚊の前 R と後ろ R を調べる。
このときも double を使うと誤差で落とす場合がある。
時間は分子と分母で分けて整数値で扱うこと。

SRM529

問題文の操作を行ったとき袋4に入っている小石の数は?

考え方:
問題文のままコードを書くと速度が間に合わない。
法則を導き出すために N について 0-100 くらいで試す。
すると答えは N を積に戻して和に変換した数値のようである。
例えば、N=6 なら 5(2*3,2+3)、N=7 なら 8(1*7,1+7) のよう。
N=36 のとき 20(2*18,2+18)、N=39 のとき 16(3*13,3+13)になる。
推測すると、素数を小さい数から割っていって割りきれたら、
その素数と商を足し算したものが答えになる。
この推測は正しい。

SRM530

0からN−1ステージまであるゲームがある。
あるステージからあるステージに行けるかの表が与えられる。
次に行けるステージは必ず番号が大きいステージである。
0からN−1にたどり着くまでの方法は最大で何通りか?
ただし、1つの場合はかならず新しいステージの移動が必要。
例えば、新たな1通りの方法を追加するには、
いままでに1度もない「ステージ1から3の移動」を含む、などが必要。

考え方:
まず、0からN−1に行くために通過するステージを求める。
通過しないステージは不要なので除外する。経路も除外する。
0からN−1のステージをすべて繋ぐ経路があったとする。
ここに新たな経路を1つ増やすと答えがひとつ増える。
このように考えるとステージ数と経路の数から答えが求まる。
実際には「経路の数-ステージ数+2」が答えになる。

SRM531

町と町をつないで王国を再構築する。
道があるかどうか、道を作るコスト、道を壊すコストが与えられる。
閉路がなく、すべての町を行き来できるように再構築したい。
最小のコストはいくらか?

考え方:
作る場合と壊す場合を分けて考える。
まず作る場合は Union-Find でグループ分けし、
コストの安い順から結合していく。
以上で構築のコストがすべて算出できる。
破壊するコストはすべて壊すコストから最大全域木のコストを引く。
最大全域木のコストはコストを(100-コスト)とすると、
最小全域木のアルゴリズムを使って求めることができる。

SRM532

隣あう偶数のマスが塗られているようにマスを塗る。
マスの塗り方は何通りか?

考え方:
M が最大 8 なのに注目する。
M=8 のとき過去8マスの状態をメモする。
状態はビットを使ってメモしていく。
過去のマスの状態すべてを見て更新していく。

SRM533

最初体力がMあり1進むと1減少する。
位置Xで敵が登場し戦うか戦わないかを決める。
戦う場合P%の確率で勝つと体力がGだけ回復する(最大M)。
負けると体力0になり終了する。
最善の戦略を用いたとき進むことのできる距離の期待値は?

考え方:
前から考えると最善の戦略が戦うのか戦わないのかわからない。
よって後ろから前に更新していくことになる。
戦う場合の期待値と戦わない場合の期待値を比較し有利なほうを選ぶ。
動的計画法を使用しないと時間が間に合わない。

SRM534

丸机の回りに5つの数字がある。
隣り合う数字は共に奇数であれば1引く。
隣り合う数字が共に0でなければ2で割る。(余りは捨てる。)
の2通りの処理方法の選択を繰り返す。
すべての数字が0になるような処理の方法は何通りか?

考え方:
1つの数字が最大10000なのが問題点。
dp[10001][10001][10001][10001][10001] はできない。
ここで奇数の値を2で割るのは1を引いて2で割るのに等しい。
ということに注目する。
よって、例えば 10000 であってもせいぜい、
10000,5000,2500,1250,625,624,312,156,78,39,38,19,18,9,8,4,2,1,0
くらいの数字しか発生しない。
よって 0->0、1->1、2->2、3->4、4->8、5->9 などの対応表を作れば良い。
最大は 8191 のときの26個である。
よって dp[26][26][26][26][26] で動的計画法が可能である。

SRM535

0 から 999999999999999999 までの数字がある。
これを次の規則でソートする。
1、各桁の数字の和が小さいものが先になる。
2、1の条件が等しければ文字列として昇順にする。
すなわち、 999 < 30 、111 < 3、10 < 100 である。
そのソート後の N 番目の数字はいくつか?

考え方:
1の条件は桁DPをしてその和になる数を数える。
和が 0 になるのは何通りか?
和が 1 になるのは何通りか?
これはそれぞれ数えることができるので、
結局 N 番目の数字の桁の和がいくつかはわかり、
その初めての数字が何番目なのかもわかる。
2つめの条件にも桁DPを用いる。
先頭の数字を 1 から試し、
続けて次の桁の数字を 0 から確定していく方法をとる。

SRM536

現在の価値が定められた会社がいくつかある。
k つ以上の会社を合併すると価値が平均値の会社が1つできる。
最終的に1つの会社に合併するとき価値の最大値を求めよ。

考え方:
平均の平均をとるとさらに価値が低くなる。
価値の高いものはできるだけあとで合併したい。
よって、価値の低いものを優先的に合併し、
合併した会社を以降の合併で必ず使うと良い。
ただし、例えば k = 3 で 6 つの会社があったとき、
先に 3 社合併して次に 4 社合併するか、
先に 4 社合併して次に 3 社合併するかは結果が異なる。
よって、ここで動的計画法を用いる。
dp[n 社まで合併したときの最大価値]

SRM537

最初の状態では -1 と書いてあるトーストのみ食べることができる。 
i 番目のトーストを食べると i と書いてあるトーストを食べれる。
トーストを食べる順番をランダムに決めたとき食べれる枚数の期待値は?

考え方:
期待値の考え方のみで解くことができる。
トーストが -1,0 であったとき。
-1 を1番目に食べる確率は 1 なので期待値は 1 である。
0 を2番目に食べる確率は -1 を食べたあとなので 1/2 で期待値は 1/2。
トーストが -1,0,1 であったとき。
1 を3番目に食べる確率は 1/(2*3) で期待値は 1/6。
よって、トータルの期待値は 1+1/2+1/6 = 10/6 となる。
この計算の実装は動的計画法などを要さない。

SRM538

1×1の赤、青、黄と1×2の黒ブロックがある。
黒ブロックは縦にしか詰めない。
指定された幅に自由にブロックを積んだとき、
横から見た配置がありえるかありえないかを返す。

考え方:
シュミレーションなのでがんばって実装するしかない。

SRM539

'O' と 'X' と '*' の3種の魚が一列に並んでいる。
この魚を図のように囲んで2群に分ける。
ただしすべての 'O' と 'X' は同じ群に含むこと。
また 'O' と 'X' は仲が悪いので一緒にはできない。
魚は最低でも 'O' が1匹は存在する。
囲い方が偶数か奇数かを答えよ。

考え方:
偶数か奇数を返すのですべての場合の数を返さなくても良い。
こういう場合はすべての場合の数を返すのは不可能である。
例えば "OXO" があったとき 'O' を囲むやり方を考える。
このとき上と下から囲う2通りがある。
よって離れた2つを囲うには必ず上下反転のパターンがある。
よってかならず偶数の囲み方となる。
ゆえに、"OXO" の 'X' のときのように、
上下反転しても変わらない囲い方でしか奇数は発生しない。
よって、すべての 'O' か 'X' を囲んでおり、
かつ連続した1つの範囲で囲めるものの場合を数えれば良い。
注意として「魚は最低でも 'O' が1匹は存在する。」なので
"*O" のとき "*O" と "*" と "O" の3通りなので注意する。

SRM540

数値 P と Q が与えられる。
これは P/Q であらわされる分数である。
A 進数から B 進数の間で無限小数になるものの数は?
例えば、1/3 は 10 進数では 0.333・・・ となり無限小数である。
1/3 は 3 進数では割り切れて有限小数である。

考え方:
無限小数になるかどうかの判定は難しい。
よって有限小数を数えて全体から引くことにする。
有限小数になるということは、
P/(2*3) では 2*3*x 進数であれば有限小数である。
P/(2*2*3) では 2*3*x 進数であれば有限小数である。
よって約分後の Q の重複しない因数の積の倍数は有限小数になる。
約分は (P/gcd(P,Q))/(Q/gcd(P,Q)) でできる。
あとは Q を因数分解して因数の重複を取り除くだけ。
たとえば Q = 2*2*3*7*7*11 であれば 2*3*7*11 を求め、
B-B/(2*3*7*11) すれば 2 から B 進数までの無限小数の数がわかる。

SRM541

'o' は1秒後に上下左右に増える。
K 秒後の 'o' の数を数えよ。

考え方:
毎秒ですべての 'o' に更新をかけると時間が足らなくなる。
ある 'o' は1秒後は上下左右に 'o' があるに決まっているから、
その 'o' については以後増える処理を書かなくても良くなる。
次の更新は新たにできた 'o' のみで行うようにすれば良い。
幅優先探索で更新を行うと実装しやすい。

SRM542

文字列を辞書順に並び替える。
ただし、評価する文字順が順列で変動する。
aab,aba で比較するとき、
普通は 0 文字目、1 文字目、2 文字目の順で比較する。
よって aab < aba である。
ただし、2 文字目、1 文字目、0 文字目の順で比較すると、
aab > aba である。
ランダムな順列で比較していくとき、
i 番目の文字列は何番目に配置されるか期待値を求めよ。

考え方:
文字列のそれぞれの順番の文字は均等に評価される。
2つの文字列 a と b (a!=b) を比較したとき、
すべての a[i] >= b[i] が成り立つ場合、
E(a) = 1.0、 E(b) = 0.0 である。
すべての a[i] <= b[i] が成り立つ場合、
E(a) = 0.0、 E(b) = 1.0 である。
a,b 内の a[i] > b[i] の比率で順番が決まる。
E(a) = (a[i] > b[i] の数)/(a[i] != b[i] の数)
この式が出ればすべての組み合わせに対してこの式を適応するだけ。

SRM543

図のような川が3本ある。
川はそれぞれ幅と泳げる速度が決まっている。
また川沿いを歩くこともでき歩く速度も決まっている。
Start から End まで最短の時間で移動したい。
最短の時間を求めよ。

考え方:

例図では歩く場所を2ヶ所に分けているが、
最初にまとめて歩けるだけ歩いても結果は同じである。
よって、まず歩く距離 H1 を決め時間を求める。
次にそこから川0を斜めに泳ぐ縦の距離 H2 を決め時間を求める。
次にそこから川1を斜めに泳ぐ縦の距離 H3 を決め時間を求める。
これらはそれぞれ3分探索によって距離を変動させ時間の最小を求める。
3分探索内で3分探索を用い、さらにその3分探索内でも3分探索を用いる。
というような方法を用いれば解くことができる。

SRM544

カードの山A、Bがある。
山の上から1枚ずつとって新たな山C、Dを作る。
C、DができるA、Bから取り出すカードの順番は何通り?

考え方:
動的計画法。
dp[Aの山][Bの山][Cの山][Dの山]
メモ化再帰でAからとるかBからとるか分岐し、
Cに割り振るかDに割り振るかを書くとやりやすい。

SRM545

x軸上の 0 から L 地点から直線でy軸の正の方向にロケットを打ち上げる。
図のように打ち上げたときグリッド上の格子点で信号を送ることができる。
信号は 0 から L で高さ H の範囲でちょうど K 回送る。
信号を送る場合の地点の組み合わせは何通りか?

考え方:
打ち上げポイントは最大 200 ある。
すべてのポイントからすべての格子点への打ち上げを試す。
格子点の数も 200*200 なので、
200*200*200 は処理速度としては問題ない。
すべての場合を試し、nCr などを用いて数を数える。

SRM546

数値 N が与えられる。
N 以上の大きさで次の条件を満たす最小の数値を作る。
このとき桁の数字のうち2つの数字について個数を指定の数以上にする。
できる数字はいくつか?

考え方:
数字をそのまま探索すると時間が足りない。
下の桁から必要な数字に変えていき最後に N 以上になるように調節する。
桁の数字に 0 があるとき先頭が 0 であってはいけない。
よって 0 がある場合のみ場合分けを考える。

SRM547

1 から 100 までの数値のいくつかが含まれるリストがある。
1 と異なる素数の積によってリストの数値を作る。
数値は多くていくつ作れるか?
例えば、リストが {2,6,14,15} のとき。
2,15 は 2,3,5 が重複していないので2つの数値が作れる。
14,15 でも 2,3,5,7 で重複しないのでこの場合も2つ作れる。
しかし、どのようにしても3つは作れないので答えは2つ。

考え方:
1 と 53 から 97 までの素数は単独で作れる。
2 から 47 までの素数は 15 個ある。
どの素数を使うのかの組み合わせで動的計画法を使う。
2 から 47 の素数をビットに割り当ててビットDPする。

SRM548

最大16桁の 0 を含まない数字 N が与えられる。
各桁に使ってはならない数字が新たに設定された。
最初の数字にいちばん近い大きさで数字を並び替えたい。
もし、近い数字が上下に2つあれば低いほうを答えとする。
不可能な場合は -1 を答えとする。

考え方:

使う数字は最大16個なので、
数字を使ったか使わないかをビットで記録できる。
よって、上の桁から使える数字で数字を確定していく。
ここで動的計画法を用いる。
dp[桁数][数字を使ったかどうかのビットフラグ]
記録する値は N より大きい数字で最小のものを記録するパターンと、
N より小さい数字で最大のものを記録するパターンの2通りやる。
どちらの結果を使用して最終的な答えにするか選択する。

SRM549

最大20個の頂点がある。
頂点から頂点への移動可能かどうかがグラフで与えられる。
ルートが閉路であれば辺を取り除いて閉路を解消していく、
すべての閉路を無くすために取り除く辺の最少数は?

考え方:
問題のデータはグラフだが動的計画法で解く。
頂点をひとつずつ追加していき、
追加した頂点がすでにある頂点に逆向きであれば、
その数を数えて加算する。もし最少であれば更新する。
dp[すでに追加した頂点をビットで記録]

SRM550

グリッド上に文字を長方形の形に配置する。
さらに上から違う文字を長方形の形に配置できる。
最終的にできた配置が与えられる。
考えられる文字を配置した順番を答えよ。
ただし解答が複数ある場合は辞書順で小さいものとする。
配置がありえない場合は ERROR! を返す。

考え方:
それぞれの長方形のありえる最小のサイズを求める。
長方形の上に別の文字があれば取り除けない。
辞書順で大きい文字から上から取り除ければ取り除いていく。


SRM551

ABC の3文字を隣り合わないように環をつくる。
何通りの環ができるか?

考え方:
動的計画法。
先頭を決めて終点まで更新を続ければ良いが、
先頭と終わりが同じ文字ではいけない。
よって先頭と終わりの文字を記録しておく必要がある。
dp[先頭の文字][Aの文字数][Bの文字数][Cの文字数][終わりの文字]

SRM552

初めの K 項が与えられる。
以降は式に従って i 番目の項を求める。
初めの K 項は自由に並び替えることができる。
N 番目が最大になるような K 項の並びを求めよ。
複数ある場合は辞書順で最初のものを答えよ。

考え方:
値が大きいのでループは無理なので法則を探す。
まず小さい値で実際に結果がどうなるかで傾向を探って解く。
すると、項数が奇数と偶数で結果が異なる。
また、結果の傾向が K の周期でループする。
という2つのことがわかる。
ただし、注意すべきことは項数が偶数の場合に、
k から 2*k のときのみ特殊な結果を返さないといけない。
この点に注意すること。

SRM553

いくつかの数字があり総和は4の倍数ではない。
ここから全部で k 個だけ任意の順番でひとつずつ数字を取り除いていく。
ただし総和はどの状態でも4の倍数であってはならない。
k 個取り除いた時点での最大値はいくつか?
例えば、{5,5,7} から 2 個取り除くとき。
7 → 5 の順番で取り除けば最大値は 5 になる。
最初に 5 を取り除くと 4 の倍数の 12 になってしまうのでできない。

考え方:
動的計画法。
4の倍数にならなければ良いので、
4で割って余りが同じ値であれば小さいほうから引いていけば良い。
貪欲と動的計画法が混在している。
まず4で割って割り切れる数、1余る数、2余る数、3余る数でグループを分ける。
それぞれのグループはソートしておく。
どのグループを選ぶかで動的計画法を用いる。

dp[割り切れる数][1余る数][2余る数][3余る数]=総和

SRM554

C 色の1×1×1のブロックで塔を作る。
ただし1層はブロック4個を使って2×2とする。
隣り合う同じ色のブロックの和の制限 K がある。
1 から H 層までの塔は何通りか?

考え方:
隣り合う同じ色のブロックとは塔全体で K までということ。
動的計画法で普通にやっていけばよい。
下の層をみて上の層を積んでいけばよい。
その際に隣り合う同じ色のブロックの数を数えていく。
dp[階層][色1][色2][色3][色4][隣り合う同じ色のブロック数]

SRM555

N 地点ある道がある。
0 地点がスタートで N-1 地点がゴール。
この間に k 個の沼地点がある。
スタートとゴールは沼ではない。
いちどに1地点もしくは2地点移動できる。
沼には止まることはできない。
2地点移動すれば沼を1つ飛び越えることができる。
スタートからゴールに移動する方法が偶数通りになるような、
沼の配置方法は何通りか?

考え方:
例えば沼でない地点が3つ続くと偶数通りである。
いくつの沼でない連続地点が偶数通りかは動的計画法で求める。
最初に連続数から偶数かどうかを判定するリストを作っておく。
途中に沼でない連続地点が偶数通りの場合が1箇所でもあれば、
すべてのルートにおいて偶数通りといえる。
これは偶数×偶数も偶数×奇数も偶数であるため。
次に、例えば N が 8 沼が 2 だったとき、
まず .##. と配置し、置き残りの沼で無い地点 4 個を、
.# の間 ## の間 #. の間にはさんでいけば良い。
このとき空白区間に偶数通り区間があったかどうかフラグを持つ。
これを動的計画法で解く。
dp[間の数][残りの沼で無い地点数][偶数区間を持つかのフラグ]

SRM556

数字からなる文字列がある。
先頭から順番に最初は真ん中、次から左か右に置いていく。
0から始まらない最も小さい数字を作れ。
例えば、213 であれば 2 を真ん中 1 を左、3 を右で 123 にできる。

考え方:
まず0でないひとつの数字を先頭候補にする。
先頭候補に来るまでは数字がより小さくなるように左右に割り振る。
先頭候補は左に割り振り以降はすべて右に割り振る。
できる数字のうち最少のものが答え。

SRM557

N 個の上り下りをする山がある。
山は登りを U とし下りを D とする。
例えば登山の過程を UUDUUDDD と書くことができる。
必ず高さ 0 地点から出発し高さ 0 地点に下りる。
ただし UDDUUD は無い。 -1 地点には下れない。
いま上り下りの総数とある一部の上り下りの記憶がある。
N が 4 で記憶が UD のとき、
ありうる場合は UUDD と UDUD の2通りがある。
N と記憶が与えられるときありうる場合は何通りか?

考え方:
記憶といくつまで一致したかを覚えていく動的計画法。
dp[横の位置][高さ][記憶との一致数]
例えば記憶が DUDUU であれば、
D のとき記憶の一致数を 1 とし DU となったら 2 とする。
DUDU の次に U がくれば記憶の条件をクリアするので、
以降は自由に U と D できる。
DUDU の次に D がくれば記憶の条件はいったんクリアになるが、
DUD になるので記憶の一致数は 3 から続けることに注意。

SRM558

黒と白のカードが並んでいる。
黒から右か左へ黒に当たるまで好きな数だけ白を黒にできる。
この作業を交互のプレイヤーで行うとき、
最初に黒にできるカードを失ったほうが負けである。
どちらが勝つかを判定せよ。

考え方:
Nim というゲームと同じとみなせる。
XORを使った特殊な判定法なので解き方を知らないとまず解けない。
Nim の勝敗判定はとても有名なので解説はすぐに見つかるはず。

SRM559

A B S の3タイプのレーンがある。
S のレーンを追加することでレーンの環を完成させる。
環は切れたり交差してはいけないが、複数の環に分かれても良い。
ただし数字のマスにレーンを置くとその数字のコストがかかる。
最少のコストを求めよ。できない場合は -1 を返す。

考え方:
複数の S の置き方を試して最少コストを求める問題に見える。
しかし、実は1つのパターンができるかできないかのどちらかしかない。
よってできる場合はそのコストを求め、できなければ -1 を返せば良い。

SRM560

幅1の四角の4点に囲われていると次のターンで中央に点が描かれる。
前のターンの点は次のターンで消える。
問題で与えられるのは現在の点の状態である。
矛盾を生じないように何ターンまで遡れるだろうか?
無限に遡れる場合は -1 を答えとする。

考え方:
xターン戻してxターン進める。
このとき元の状態と同じであれば可能といえる。
可能な場合の最大ターンを求めれば良い。
処理時間的にこのシュミレーションをすべてやる余裕はある。
ただし -1 を返す場合の判断が非常に難しい。
この問題の場合、盤面の最大サイズが40*40なので、
21か22くらいまでシュミレーションをして、
それでも可能であれば無限に遡れると判断しても良い。

SRM561

n-1本の道で繋がったnの町がある。
町と町は必ず1本以上の道で繋がっている。
町と町の間の道の長さはすべて 1 とする。
町にはいくつかの家族が住んでおり、
すべての家族がある日別の町に旅をすることになった。
ある家族がどの町に行くかは等確率で決められる。
すべての家族が通る道の長さの平均値を求めよ。

考え方:
「道の長さの平均値」で考えると難しいので考え方を変える。
これは、ある道をすべての家族が通る確率(100%を1とする)を求め、
すべての道で足し算した結果と同じである。
例えばExamples 0)では、
0-1を通る確率が1.0、1-2を通る確率が0.5であるので、
1.0+0.5=1.5 が答えになる。
Examples 1)では、0-1を通る確率が1.0、
1-2を通る確率は家族が2つなので0.5*0.5=0.25であるので、
1.0+0.25=1.25 が答えになる。
よって、ある道をある家族が通る確率さえわかればよい。
ある道について家族がある地点からすべての別の地点へ行くとき、
その道を通る場合の確率を求めることができる。
i番目の道をj地点からk地点へ行くとき横切るかどうか判定する場合、
「j->A[i]の距離+A[i]->kの距離」と「j->B[i]の距離+B[i]->kの距離」
が等しければ道を横切ると判定できる。
よって、確率は数え上げによって求めることができる。

SRM562

0〜N-1番までのN個のレーンがある。
隣り合ってはいけないレーンの組み合わせのリストが与えられる。
ランダムで適当にレーンを並べるとき。
隣り合ってはいけないリストに違反しない確率はいくらか?

考え方:
使ったレーンをビットで記録し右端の番号を記録する動的計画法。
dp[使ったレーンのビット][右端の番号]
左から順番にレーンを置いていけば良い。
追加するレーンがリストに違反しないかをチェックするため、
最も右端のレーンが何番のレーンなのかを覚えておく必要がある。
レーンを違反せず追加できるなら追加して右端番号を更新する。

SRM563

カードが並んでいる。
カードには必要枚数と与えるダメージが書かれている。
カードを選ぶとそのカードを含め右にカードに書かれた必要枚数を使って
選んだカードに書かれたダメージを与えることができる。
必要枚数に満たない場合はダメージを与えることはできない。
使ったカードは消滅し消えたカードの間は詰められる。
ダメージは可能な回数だけ与えることができる。
与えることのできる最大のダメージはいくらか?

考え方:
動的計画法。
右からカードを選ぶか選ばないかで試す。
カードを選ぶ場合は必要枚数を消化しダメージを更新し、
カードを選ばない場合は次回に使える必要枚数に1枚追加する。
dp[最大ダメージ][必要枚数の残数]

SRM564

チェスのナイトは 1,2 の比で飛んで移動する。
この問題のナイトは a,b の比で移動する特別なナイトである。
盤面の幅と高さが与えられるので、
任意のスタート位置から到達できる場所の最大値を求めよ。
ただし、いちど通った場所でも何回でも通過できる。

考え方:
盤面が大きすぎるので全探索は無理、
法則を見つけようとしても盤面が小さい場合に対応できない。
こういう問題は良くでる。
対策として盤面が小さいときは全探索し大きい場合は法則で解く。
全探索は移動のシュミレーションをして数えていけば良い。
大きい場合は a,b の偶奇で答えが変わるので場合分けする。

SRM565

数値 N と個数 H が与えられる。
数値 N からスタートし H 個の数列を作れ。
ただし、次の数値は前の数値の約数であること。
数列はいくつできるか?
例えば N=6 、H=2 であれば
(6,6)、(6,3)、(6,2)、(6,1) の4個。

考え方:
nCrを使って数え上げる問題。
わかりやすさのため例を用いる。
例えば N=4 、H=3 の場合、
4 = 2^2 であるので、2 をどこで割るのか割り振ると考える。
1回目で割る、2回目で割る、割らないの3通りがある。
これは 2,2 に仕切りを2個 |,| 立てて分ける作業と同じ。
よって、4C2 で答えが求まる。

(4,4,4)     ||2,2
(4,4,2)     |2|2
(4,4,1)     |2,2|
(4,2,2)     2||2
(4,2,1)     2|2|
(4,1,1)     2,2||

SRM566

N 匹のペンギンがいる。そして環状に M 本の杭が打たれている。
環状の杭をいくつかつないですべてのペンギンを囲いたい。
囲める場合囲んだ面積の最小値を求めよ。
ただしすべての杭と杭の線上の近くにはペンギンはいない。

考え方:
問題文の「杭と杭の線上の近くにはペンギンはいない」は重要。
double座標の杭と杭の線上にペンギンがいるかどうかは判定不能である。
ペンギンが杭の内側か外側かは外積を使って求める。
繋ぐ事ができる杭の組みあわせのリストを作ったら、
杭0 からスタートして杭M まで動的計画法で面積の最小を求める。
dp[現在の杭を使った時の最小の面積]
これを杭1 から 杭M-1 スタートまでのすべてやる。
幾何を使用しかつ動的計画法をM回繰り返すので難易度は高い。

SRM567

座標を指定すると下に幅 1,3,5・・・ で X を描いて山になる。
N 個座標を選択して問題の絵になるパターンは順番を考慮して何通りか?

考え方:
必ず1回は選択する必要のある座標Aの数を a とする。
また選択してもしなくても良い座標Bの数を b とする。
A を1回選択すると次からは選択してもしなくても良いので B になる。
ゆえに A を選択したら N-1、a-1、b+1 とする更新にする。
B を選択したら N-1、a、b とする更新になる。
最終的に N == 0 のとき a == 0 なら 1 を返しそれ以外は 0 を返せば良い。
これを普通に書くと時間が間に合わないのでメモ化再帰する。

SRM568

ランダムで N 枚のカードを並べる。
左から昇順になっていればカードはそのままとし、
昇順になっていないところから右を再度ランダムで並び替える。
例えば 1,2,5,4,3 であれば 1,2 までは昇順である。
よって、次は 5,4,3 のみで並び替えを行う。
次に、3,5,4 となればあとは残りの 5,4 で並び替えを行う。 
このように作業を繰り返すと最終的にはすべてが昇順になる。
すべてが昇順になるまでの並び替え回数の期待値は?
ただし、最初に並べる場合も1回と数える。

考え方:
例えば左の2枚が昇順であればこの2枚を除き、残りで次を評価する。
しかし、この考え方ではこの問題は解けない。
左の1枚が最小であったのでこれを除き、並べ替えを0回し、
左の1枚が最小であったのでこれを除きというふうに考える。
つまり、必ず1枚ずつ取り除いていくものと考える。
いちばん左に最小のカードがくるまでの回数の期待値は、
E=((最小のカードの枚数)/(並び変えたカードの枚数))*E+1
と書ける。
よって、
E=(並び変えたカードの枚数)/(並び変えたカードの枚数-最小のカードの枚数)
とできる。
この作業を左から1枚ずつ続けて結果の和が最終的な期待値となる。
ただし、この考え方では毎回最初に1回の並び替えを行っている。
前の1回の評価が終わったとき次の評価は0回の並び替えしかしない。
よって、最初の1回を除く N-1 回を最終的な結果から引く必要がある。
コードは簡単だが期待値についてよく知らないとかなりの難問。

SRM569

N!K は (N-1)!K*N!(K-1) に分解できる。
n!1 はそのまま n! とみなし n の階乗になる。
0!k は 1 とみなす。
このとき N と K が与えられるので、
N!K の約数の数を求めよ。

考え方:
例えば N!K が 2^3*3^4 に分解できるなら約数はの個数は(3+1)*(4+1)である。
よって N!K がどのように素因数分解できるか動的計画法でやっていけばよい。
このとき状態は dp[Nの数][Kの数] なので dp[1001][101] くらいでできる。
それぞれの dp[n][k] に対して各素数が何乗なのかを記録していけばよい。
しかし、1000 までの素数は 150 程度あり、
dp[1001][101][160] などとするとメモリが足らない。
よって、dp[6][101] のときは dp[6][101][2] などと小さく割り振る。
このように必要なだけギリギリでメモリを割り振ればできる。
これを実現するには vector&lt;int&gt; dp[1001][101] とする必要がある。
メモリへの記録のやり方が面倒な問題。
もし dp[1001][101] で解ければ実装はかなり簡単といえる。

SRM570

N 地点とどのように接続されているかが与えられる。
地点は地点と地点を伝ってすべてに到達でき接続は環になっていない。
A 社と B 社がこの地点を分け合う。
B 社は地点と地点を接続することができるので、
繋がっていない地点でも自社の地点にすることができる。
しかし、A 社は最初から繋がっている地点のみ自社の地点にできる。
A 社と B 社の分け方はいくつあるか?
例えば 1-2-3 と地点が繋がっていたとき。
A-B-B という分けかたができる。これは可能。
ただし、A-B-A は A 社が分断されてしまっているので不可。
B-A-B は B 社が分断されていいるだけで A 社は分断してないので可。
また、A-A-A や B-B-B という分けかたも可能と考える。

考え方:
大きなグラフの中に繋がった小さなグラフがいくつできるか数えれば良い。
1 から N 地点まで存在するので、
まず 1 を必ず含んでそこから探索してできるグラフの数を数える。
次は 1 を使わずに 2 を必ず含んでそこから探索してできるグラフの数を数える。
これを N まで繰り返せばよい。

SRM571

N 個の原子からなる分子がある。
1個の原子はそれぞれ数値を持っている。
ここから k 個選んで原子の数の和を最大にする。
ただし、繋がった原子は必ず少なくとも1つを選ばなければならない。
例えば 100-1-100 から 1 個選ぶ場合。
100 を選べば最大値は 100 になるが、
1 を選ばないと「繋がった原子は必ず少なくとも1つを選ぶ」を満たさない。
よって、この場合は最大値は 1 になる。
 
考え方:
k の最大値が14なので全探索が可能。
ある1つの原子とそこに繋がる1つの原子でスタートし、
隣りあうか1つ飛ばしで選んで k 個まで探索する。

SRM572

N の数字をいくつかに分ける。
ただし、分けたすべての値を M で割ったとき、
余りはすべて異ならないといけない。
分けかたはいくつあるか?
N=3、M=2 のとき(3)、(3,0)、(1,2)、(2,1)、(0,3) の5つ。

考え方:
M が最大50と小さいことに注目する。
dp[0からM-1の異なる数字の数][余りの数字の和]
例えば M > 5 のとき dp[2][4] になるのは (0,4)、(1,3)のとき、
このような余りの組み合わせを動的計画法で求めることができる。
あとは並び替えを M! で掛け合わせる。
最後に余りの和が A であったとすると、
(N-A)/M を M 個に分ける組み合わせを考えれば良い。
nCrでいうと((N-A)/M+(M-1))C(M-1)で数えることができる。
動的計画法と数え上げを組み合わせた問題。

SRM573

N 匹のオオカミの初期座標が与えられる。
オオカミは1回で上下左右に1座標移動する。
m 回移動したとき N 匹すべてが同じ座標にいるとき、
その移動方法は何通りか?

考え方:
1匹のオオカミが m 回移動した場合に、
どの地点に何通りで存在するかは動的計画法で簡単に求まる。
移動する可能性のあるすべての点について、
N 匹のオオカミが存在する移動方法を掛け算する。
すべての点の結果の和が最終的な答えになる。

SRM574

正 N 角形がある。
最初に頂点をいくつか結んでいく順番が与えられる。
続けて頂点を結んで最初の頂点に戻る方法は何通りか?
ただし、新たに頂点を結ぶ場合は、
過去に引いた線の少なくとも1つ以上と交差しなければならない。

考え方:
フラグを立てながら交差のチェックをしつつ探索を進める。
完成するパターンを1つずつカウントしていっても間に合う。

SRM575

黒と白のマスの市松模様がある。
ここに3マスからなるL字ピースを置いていく。
L字ピースは X と他のピースと重ならず枠を出てもいけない。
また、L字のカドは黒模様の上に無いといけない。
最大いくつのピースを置くことができるか?

考え方:
高さの制限が4なので動的計画法を用いることができる。
過去2つの黒マスのL字の配置方法がわかれば良い。

SRM576

縦が1000、横がWのテキストフィールドがある。
ここにW文字以下の文字列Sを繰り返し書いて埋める。
y行x列を左上とした文字の領域が与えられる。
これは文字列Sで埋めた結果の一部分である。
このような結果が得られる文字列Sは何通り存在するか?

考え方:
Sの可能性を1文字からW文字まですべて探索する。
与えられた文字領域の文字をインデックスを求めてチェック。
もし食い違いが無くどの文字を埋めても良い場所があれば、
26のその場所数乗がその文字数での答えの数になる。
特に工夫せずに全探索が可能。

SRM577

数字がいくつか与えられる。
ソートしたときに隣り合う数字が素になるようにしたい。
(素とは共通の約数が無いこと。)
そのために間に任意の数字をはさみこむことができる。
目的を達成するために必要なはさみこむ数字の数は?

考え方:
間に1文字はさみこんで素をチェックするのは全探索できる。
もし、1文字で不可能な場合は2文字であれば目的を達成できる。
よって、素で無ければ1文字追加をすべて試し、
それでもダメなら2文字を答えとするのを繰り返す。
「2文字であれば目的を達成できる。」ことの証明は難しい。

SRM578

一列に N 個の地点が存在する。
各地点にはオオカミがいるかいないかのどちらか。
ここに次のような情報が与えられる。
0-1 であれば 0 〜 1 地点に最低1匹はいる。
2-5 であれば 2 〜 5 地点に最低1匹はいる。
このような情報が複数与えられるとき、
オオカミの存在する状態は何パターンか答えよ。

考え方:
地点を左から1地点ずつ追加するものと考える。
このとき、左から i 地点に最後のオオカミがいる場合を記録する。
dp[a地点存在するとき][左からi番目に最後のオオカミが存在する場合]
例えば 3 地点あって特に存在条件が無いのであれば、
dp[3][0] = 1、dp[3][1] = 2、dp[3][2] = 4 である。
次に4地点目を更新する場合に 1-3 という条件があったとき、
dp[4][3] = dp[3][0] + dp[3][1] + dp[3][2] で良いが、
それ以前は、
dp[4][0] = 0、dp[4][1] = dp[3][1]、dp[4][2] = dp[3][2] で更新する。
dp[4][0] = 0 なのは 1-3 に必ず存在する条件があるので、
4地点中0番目に左から最後のオオカミが存在することはありえないから。
この更新を繰り返す。

SRM579

異なる半径の円がいくつかあり接するように並べる。
並べる順番はどのような順番でも良い。
左端と右端の円の中心のx座標からx座標までの距離が最短のとき、
その距離を求めよ。

考え方:
円の数が最大8つなのですべての組み合わせを試せる。
あとは接する円の中心のx座標間の距離を求めるだけの問題。

SRM580

左右下のみの同じ場所は2回以上通らない移動で最下段まで移動する。
数字のポイントでは得点を追加できる。
敵が最小点数になるように最下段まで移動しようとするので、
自分は自由に通過できない壁を設けて得点を最大化したい。
ただし、敵が最下段に到達するルートをすべて遮断するのは違反。

考え方:
壁を作る作業を考えたらこの問題は解けない。
この問題は壁を作って相手の妨害をすると考えてはいけない。
結果として自分が最下段まで最高点数で移動する点数と同じである。
よって、その地点での最大点数をメモする動的計画法で良い。

SRM581

同じ N 点からなるグラフ A と B が与えられる。
A の点と B の点をそれぞれ自由に1対1でつなぐ。
このとき閉路の長さがちょうど k であるものがいくつあるか数える。
最大でいくつできるか答えよ?

考え方:
N 点は最大で9個なので、A と B の組み合わせを9!ですべて試せる。
閉路の長さの数えかたは A の2点とそれに繋がる B の2点があるとき、
長さ=Aの2点の距離+Bの2点の距離+2 である。
よって、1つずつ数えることが可能。

SRM582

横一列に並ぶN地点のうち0地点に立っている。
時間1で横に1つ移動できる。
時間1で横の地点に色を塗れる。
時間1だけ何もせずに待機できる。
また、地点は色を塗ると乾くまで指定された時間だけ到達できない。
すべての地点に色を塗るまでの最小時間を求めよ。

考え方:
地点の数は最大7なので塗る順番を7!で決めてしまえばよい。
ただし、地点を右から塗るか左から塗るかで結果が異なる。
よって、7!*5^2の全探索をシュミレーションする。

SRM583

地点xから地点yに移動する際に通過する1の地点では点数が1加算される。
A と B の2人がいる。
A は自由に地点を定める。
B は A の選んだ別の地点を選ぶ。
A が A の選んだ地点から B の選んだ地点へ移動する。
このとき A は点数が最小になるようにしたいし、
B は点数が最大になるようにしたい。
A と B が最大の努力をした場合に最小の点数を求めよ。

考え方:
まずすべての地点からすべての地点の最短点数を求めておく。
次に A の地点を決める、B の地点を総当りし最大値を求める。
すべての A の地点について最大値の最小値を求める。
最大ケースでも 1600*1600 なので可能。

SRM584

それぞれタイプを持つ未知の N 個の遺跡がある。
このうち発見されたタイプと発見された総数 K がわかった。
(どのタイプがいくつ見つかったかはわからない。)
どの遺跡が発見されたのか考えられるパターンの数を答えよ。

考え方:
次のような動的計画法で解ける。
dp[n個目までの遺跡で][総数kの遺跡が見つかった]
更新に際して数え上げの nCr を用いる。
1個目の遺跡が3つあるとき。
dp[1][1] = 3C1、dp[1][2] = 3C2、dp[1][3] = 3C3
のように更新していけば良い。
最終的な答えは dp[N][K] になる。

SRM585

図のように上下左右にそれぞれ M 個の座標を持つ。
また、その内部に N 個の点を持つ。
上下左右の4つから3つ選んでそれぞれ M 個の点より1つ選ぶ。
このとき三角形を描いて N 個の点が
すべて三角形の内部にくる場合は何通りあるだろうか?

考え方:
上と左から2点選んで条件を満たすか外積で判定する。
あとは右か下より1点選んで判定を総当りする。
次に、下と右から2点選んで条件を満たすか外積で判定する。
左か上より1点選んで判定を総当りする。

SRM586

大文字アルファベットの文字列に対して文字の重さを計算する。
例えば ABABA であれば、
最も外側の A と A の距離は 4 であり
最も外側の B と B の距離は 2 である。
よって ABABA の重さは 4+2 = 6 であるとする。
N 文字の文字列があり最も軽い文字列のパターンはいくつか?

考え方:
N が 26 文字までであれば A から Z を1文字ずつ使えば良い。
このとき重さは常に 0 で並べ方は N! である。
N が 27 文字以上の場合は、
1つのアルファベットでかためる場合が最も軽くなる。
27文字なら AABCDEFGHIJKLMNOPQRSTUVWXYZ など。
A と A を離れさせるメリットは無い。
よって N 個の文字の間 N-1 個の間に 25 個の仕切りを入れて、
A から Z で分ける場合と考える。
この場合は (N-1)C25 で数えることができる。
なお A から Z の順番も考慮し (N-1)C25 * 26! とする。

SRM587

図のような格子がある。
格子には対角線が1つ存在しその向きが N と Z で表される。
線で隣り合う場合同じ色を塗れないとするき、
3色ですべての地点を塗りきることができるか判定せよ。

考え方:
四角い格子の2点が定まれば他の2点は確定する。
1つの四角形が確定すれば隣接する四角形も確定する。
この手順を繰り返せばよい。
確定を続けていき途中で不可能になれば NO を返し、
最後まで可能であれば YES を返す。

SRM588

迷路を A と B が交互に必ず1歩ずつ移動する。
A は動く手順が決められている。
B は A の手順を見ながら自由に移動できる。
B が A と重ならずに逃げ切れるかどうかを判定せよ。

考え方:
B の位置の動的計画法でよい。
dp[n手目][Bのx座標][Bのy座標]
n 手目に B が存在する可能性を動的計画法ですべて求める。
その場所に A がいればその可能性を消去する。
最後に B が存在していれば逃げ切れると言って良い。

SRM589

N 個の 0 と 1 からなる文字列が与えられる。
また N の約数である数字 M が与えられる。
できる操作は3つ。
1、1つの 0 を 1、もしくは 1 を 0 に反転する。
2、最初の x*M 個(xは正の整数)の範囲をすべて反転する。
3、最後の x*M 個(xは正の整数)の範囲をすべて反転する。
すべての文字を 1 にするには何回の操作が必要か?

考え方:
M 区切りで分ける場合をすべて考える。
中央から外へ反転を使うか使わないかで最小を選択するのを繰り返す。
結果的に全探索が可能なので実装問題といえる。

SRM590

将棋盤に歩が上と下向きに存在する。
上向きの歩は上に下向きの歩は下向きに1歩ずつ動く。
歩は駒がぶつかった場合に動けなくなる。
おなじマスに2つの歩が存在することは無い。
また、盤の上端と下端で動けなくなる。
すべての移動を試したとき最終的な状態は何通りか?
(すべての移動は「1歩も動かない」も含む。)

考え方:
動的計画法で解ける。
複数列あるが各列は独立なので、
各列で結果を求めてそれぞれ掛け算すればよい。
1列で考えたとき、
上から n 番目の歩が上から k 番目のマスに移動したとして、
k+1 より下にはまだ歩が置けることをメモしていく。
記録のしかたは dp[n][k+1]
まず 0 番目の歩が -1 に存在しているとして、
dp[0][0] = 1 である。
盤面が

.
U
D
.

のとき、U が上に1歩進むと、
dp[1][1] += dp[0][0]
U が上に1歩も進まないと、
dp[1][2] += dp[0][0]
U は下には移動できないので dp[1][3]とdp[1][4]は更新できない。
D は動かないとき、
dp[2][3] += dp[1][1]
dp[2][3] += dp[1][2]
D が下に1歩動くとき、
dp[2][4] += dp[1][1]
dp[2][4] += dp[1][2]
D は上には移動できないので dp[2][1]とdp[2][2]は更新できない。

SRM591

N 人の選手がいてそれぞれ強さが決まっている。
この選手を2つのグループに分ける。
条件はどちらかの強さの和がもう一方の強さの和より大きいこと。
また強いチームの誰でも1人がもう一方に移ればチームの強さが逆転すること。
1,1,1,2 のとき 2,1 と 1,1 や 2 と 1,1,1 で可能。1 と 1,1,2 では不可。

考え方:
動的計画法を使う。
まずすべての総和を求める。
動的計画法では片方のチームの和を記録しておく。
総和を最初に出しておくことでもう一方の和もすぐにわかる。
強さを降順でソートする。
先頭から順に総和に足す場合と足さない場合を動的計画法で記録する。
追加していく際に移動することで大小が逆転する場合がある。
このときの状態数を答えに追加していく。
このときすでにある和の要素は現在追加した要素より必ず大きい。
よってどの要素を元に戻しても大小関係は逆転するといえる。

SRM592

A と N の2つの数字が与えられる。
ここから A から A+N まで1ずつ増える数列を作る。
次にいくつかの桁の数字を自由に削除する。
(ただし全桁消して 0 にすることはできない。)
(また 201 から 01 にするパターンと 1 にする場合は別と考える。)
このとき非減少数列を維持できるパターンはいくつか?
例えば A=10 N=1 のとき、
(10,11)(1,11)(1,1)(1,1)(0,11)(0,1)(0,1)の7パターンできる。

考え方:
動的計画法を用いる。
数字から桁を削除する方法はビットなどを使って全部作るしかない。
また前後の大小評価はソートなどを用いて効率的に行うべきである。
真面目に数字をすべての場合で100個ぶん評価していく必要がある。
速度やメモリの量にも気を遣う。難しい。

SRM593

リレーの走者が N 人いる。
それぞれに最低タイムと最高タイムが与えられる。
それぞれ2チームに分けたときに、
一方のチームの最高タイムの和と
もう一方のチームの最低タイムの和の差が最小になるようにしたい。
そのときの最小のタイムの差を求めよ。

考え方:
すべての人の最低タイムの和をsum_aとする。
すべての人の最高タイムの和をsum_bとする。
N 人からk人を選び最低タイムと最高タイムをすべて足しk_abとする。
このときk人のチームとk人以外のチームの2チームの
最低タイムの和と最高タイムの和の差の最大は
max(sum_b-k_ab,k-ab-sum_a)
で書くことができる。
よってすべての場合で最大値の最小を求めれば良い。
動的計画法では、
すべての選び方で最高タイムと最低タイムの和をメモすれば良い。
動的計画法自体は簡単だが解答の発想が難しい。

SRM594

黒石を囲碁のルールで置いていき白石をいくつあげられるか?

考え方:
囲碁に詳しい人に有利。
目が2つ以上あるかの判定。やるしかない。

SRM595

0〜A の X と 0〜B の Y のとき X xor Y <= C となる。
このようになる X と Y の組み合わせは何通りか?

考え方:
ビットを上の桁から評価していくだけ。
ただし実際の実装はかなり考えるので面倒。

SRM596

F(n) = (n - 0^2) * (n - 1^2) * (n - 2^2) * ... * (n - k^2)
上記で表される値がある。(n - k^2 は正の整数)
F(lo)からF(hi)までの値でdivisorで割り切れるものはいくつか?

考え方:
まず F(1)からF(n)の場合を考える。
このとき n までで -0*0 した場合に割り切れるもの、
-1*1、-2*2したときに割り切れるものと小さいほうから順に数えていく。
ただし divisor で割った余りが重複すると2回カウントすることになるので、
重複しないようにフラグで覚えておく。
答えはF(hi)-F(lo-1)になる。

SRM597

1 から N までの数字が1個ずつ与えられる。
この数字を使って数字のセットを作れ。
ただし 0 から 9 までの数字が桁に2個以上あってはいけない。
例えば 1 から 10 のときに (1,2,4,7,9) などのセットは作れるが、
 (1,3,10) というセットは 1 が2回以上あるので作れない。
作れるセットは何パターンか?

考え方:
まず 0 から 9 の数字を使って数字を作成する。
これが N 以下であればリストに追加するようにすれば良い。
リストはどの数字を使ったかをビットで記録するようにする。
リストができたらイメージとしては次のように、
dp[0000000011] += dp[0000000001]+dp[0000000010]
などとして動的計画法で更新していけば良い。
最終的にはdp[0000000001]からdp[1111111111]までの和が答え。

SRM598

直線上に A と B の2人がいる。
A と B は初期状態と最大移動距離を与えられ、交互に移動する。
先手で A から移動したとき B の上に重なれば勝ち。
逆に B が移動して A の上に重なれば B の勝ちである。
最善をとる勝負をしたとき勝ち負けと引き分けを判定せよ。

考え方:
先手の A が B に到達できれば A の勝ち。
できなければ A は B が到達できない距離まで逃げる。
もし2手目以降に相手に到達するには、
自分の最大移動距離が相手の最大移動距離の2倍+1であれば良い。
この条件をどちらも満たさなければ決着がつかず引き分け。

SRM599

リストに名前がいくつかある。
最初の L 個は次の名前の先頭部分が前の名前に等しい。
例えば L=2 であれば1人目が ken なら2人目は kenta など。
L=3 ならさらに ken、kenta、kentaro などでないといけない。
それ以降の名前は特に並び替えの決まりは無い。
以上の決まりに従ってリストの名前を並び替える。
並び替え方は何通りあるか?

考え方:
ある名前から次の名前としてありうるものを表にまとめる。
動的計画法としては次のようにして数える。
dp[n番目の名前][最後の名前の番号]
最後に名前が余るがこれは適当に並べれば良いので、
(N-L)!を掛け算すれば良い。

inserted by FC2 system