CF 508D

問題

3文字の文字列がn個与えられる。これらの文字列を連続部分文字列として含むような文字列を構成せよという問題。

解法

以前紹介したしりとりの問題と同じような感じでやってDFSする。
しかし文字の種類が62種類あり、グラフのノード数はその二乗あるので上手くDFSしなきゃいけない。

POJ 3254 Corn Fields

問題

http://poj.org/problem?id=3254

n*mのグリッドが与えられる。各要素は0または1であり、1のグリッドには物を置くことが出来る。隣接した二つのマスにものを置いてはいけないという制約下で、何通りの置き方があるかを答える問題。

解法

dp[i][bit] = i列目を状態bitで置いた時の置き方の場合の数

とするとO(2^(n+m))で解ける。

最初は0も連続してはいけないと勘違いしてて変なこと書いてた。

yukicoder 150 "良問"(良問とは言っていない

問題

http://yukicoder.me/problems/344

要するに入力された文字列sを、

先頭から見たときに"good","problem"がこの順に見つかるようにするためには何文字変更するべきかを求める問題。

100個の100字以内の文字列に対して探さなければならない。

解法

tbl1[i] = str[0~i]の中で"good"とのハミング最小距離

tbl2[i] = str[i~n-1]の中で"problem"とのハミング最小距離

とすると,tbl1[i]+tbl2[i+1]で求めることが出来る。

tbl1[i] = min(tbl[i-1], haming("good", str[i-3~i])

で求められるのでO(4・n) = O(n)

tbl2も同様にして求めることが出来る。

なので全体としてO(n)で求めることが出来る。

SRM 647 Div2 Hard

問題

各成分が0以上の成分であるa[i](1<=i<=N)を以下の条件を満たすように定めたい。
1. | a[i] - a[i+1] | <= K
2. a[x[i]] <= t[i]
取りうる数列の最大値を求めよ.
ただし
N<=10^9くらい
size(x) = size(t) <= min(500,N)

解法

xとtのサイズが小さいのでa[x[i]]から傾きKの直線を弾いて交差するものを縮め、それを逆向きにもやって更新がなくなるまで続けた後に最大の高さを求めるみたいなことをやる。

SRM 648 Div2 Hard

問題

整数NとKが入力として与えられる。
次の二つの条件を満たす長さnの文字列sをどれでも良いので一つ出力せよ。
1. sの各文字はA,B,Cのどれかである
2. s[i]<s[j]かつi<jとなるような(i,j)のペアがちょうどK個ある

3<=N<=30, K<=N(N-1)/2

解法

A,B,Cで構成出来る10文字くらいまでの全ての文字列に対してKを求めて色々眺めてみると、「前半2/3はA,Bのみで構成しても良い」ということが分かる。

(例えばN=8とN=9に対して並べたもの)

よって前半2/3文字は全探索で予めテーブルを
tbl[Aの個数][Kの値]
で作っておき、残りの1/3は全探索して足してvalidになったらそれを出力する。
残りの1/3の全探索の時、テーブルのどこが条件を満たすかの条件はO(N)で分かる。

N<=30なので、計算量としては2^(20)*3^(10)*30でかなり危なかったけどなんとか通った。

他のコードを見ると場合分けしまくっててかなり賢かった。

SRM 649 DIV2 Mid

問題

自然数NとKが入力される(どちらも100以下)
最初、集合AをA={N}とする。
何度かのステップでAの要素を全て0にしたい。一つのステップでは、Aの要素全てに対して、それぞれに1と2のどちらかを適用することが出来る。
1.その要素akをAから削除した後、akを二つの和に分割してAに追加する。
つまり、A -> A-{ak}+{i,ak-i}(1<=i<=ak-1)
2.akの値を1減らす
また、制約として1.の操作は全部で2回しか行うことが出来ない。

(最終的なAの要素数はいくらになっても構わない)
最小ステップ数はいくらか。

Sample Input

N=5,K=2の場合
{5} -> {2,3} (1の操作) -> {1,2} (2の操作) -> {1,1}(1の操作を1に,2の操作を2に) -> {0,0}

N=15,K=4の場合
{15} -> {7,8} (1の操作) -> {3,4,4,4} (2の操作を2回適用) -> {2,2,2,3,3} (1の操作は残り1回しか適用できないので一つの4に適用してあとは1の操作) -> {0,0,0,0,0}(1の操作を3回)
の合計6ステップ。

解法

f(n,k) = {n}をk回の分割が許容された状態における最小ステップ数
とおいてDP.

yukicoder 134 走れ！サブロー君

問題

http://yukicoder.me/problems/273

解法

bitDP.
解法は問題見てすぐ分かって紙にプログラム書いてバカみたいにたくさんメモリとってたけどまぁなんとかなった。
状態を規定するのは訪問済みノードのbitと今いるノードで十分だけどdfsするときに引数として今の重さを持ってると余計な計算しなくて良いから楽だと気づいた。

yukicoder 106 素数が嫌い！2

問題

http://yukicoder.me/problems/158

解法

エラトステネスっぽくやって各数字の異なる素因数の数を足してく。
布団で問題読んですぐ思いついてすぐ解けた。

yukicoder 64 XORフィボナッチ数列

問題

http://yukicoder.me/problems/119

解法

さすがにすぐ解けた

yukicoder 130 XOR Minimax

問題

http://yukicoder.me/problems/282

解法

最小値を上のビットから求める。

再帰で分割統治法ができる。

yukicoder 136 Yet Another GCD Problem

問題

http://yukicoder.me/problems/254

解法

k個に分割せよって勘違いしてたけどよく見たら2以上k個以下に分割せよだった。
最終的によく考えると入力kは関係ないね

yukicoder 139 交差点

問題

http://yukicoder.me/problems/250

解法

場合分けがんばる

yukicoder 144 エラトステネスのざる

問題

http://yukicoder.me/problems/242

解法

2~Nの間の各数字iに対してPr{iが生き残る}を計算する.

E{残った数字の個数} = Σ( E{1{iが生き残る}}) = ΣPr{iが生き残る}

となるので計算したものの総和でおk.

Pr{iが生き残る}はエラトステネスで倍数のやつに1-p倍するみたいなことをする.

こういう問題をぱっと解けるようになりたい

Rockethon C(CF 514 C)

問題

http://codeforces.com/problemset/problem/513/C

解法

なんか確率を頑張る。場合分けして足す。nが5以下と小さいので2^nとかも普通に出来る。分母に1足し忘れたりとかでコンテスト終了にギリギリ間に合わなかったのが悔やまれる。。。

Rockethon B2(CF 513 B2)

問題

http://codeforces.com/problemset/problem/513/B2

解法

コンテスト中は値がmaxとなるようなpermutationを全部出力して実験して法則性見いだしてやってたけどよくよく考えてみるとこんな感じになる。値が最大となるようなpermutationは2^n個あるから入力でオーバーフローしてWAった。
とりあえず左らへんに書いてある日本語が重要。

AOJ 0225

Kobutanukitsuneko

問題:

n個の文字列が与えられたときにそのn個全部を使ってしりとりのループを作ることが出来るかどうかを判定する問題。

解法:

アルファベットをノード、単語をエッジと見て各単語の最初と最後の文字のアルファベットノードに有向枝をはったグラフを作り

・グラフが連結かどうか

・オイラーグラフかどうか

を判定すれば良い

CF 510 D

問題

n要素の数列c[]とl[]が与えられる.

l[]の中からいくつか一つずつ選び,これらが互いに素となるような条件化でcの総和を最小にする問題。

解法

dp.

A(t) : lからいくつかとってgcdしてtにした時の最小コスト.

とおいて更新。

0<= t <= 10^9なのでmapでやる。

CF 510 C

問題

文字列がn個与えられ、これらの文字列が"辞書順でソートされている"と言えるようなアルファベットの並びを答える問題。

解法

入力文字列を比較していき、アルファベット26文字間での大小関係を有向グラフにしてdfs.閉路があったらImpossible.

ただし

2

aa

a

のような入力があったりするので注意。

CF 509 E

問題と解法

CF 509 C

問題

数列a[i],b[i]があり(1<=i<=n)

b[i] = (a[i]の各桁の和)

となっている。今、nとb[]が入力として与えられたときにa[]を復元せよ(ただしa[n]が最小となるものを出力せよ.

サンプル

n=3, b=[3,2,1] ⇒ a=[3,10,100]

解法