Le Algorithm: 3月 2015

2015年3月30日月曜日

問題

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

解法

二分探索

2015年3月2日月曜日

問題

http://yukicoder.me/problems/125

解法

DP.

f(i,j,k) : 1000円をi枚 100円をj個 1円をk個持ってるときにいける回数とする.

1000円を沢山持ってると後々で困ったりするので、Db円やDc円を払うときは1000円、100円を出来るだけ使うようにする必要がある。つまり払うときの枚数は貪欲にすれば良い。なので、(i,j,k)持ってるときに

・Bさんのとこに行った後の枚数(ib,jb,kb)

・Cさんのとこに行った後の枚数(ic,jc,kc)

を求めると

f(i,j,k) = max(f(ib,jb,kb),f(ic,jc,kc))+1

とすれば求まる。

Problem

https://www.hackerrank.com/contests/koder-kombat-mar/challenges/divide-it

Solution

When we used i segments and got t-divided paper and add a new segment to it , we can get k new intersections(k=0,1,...,i-1) and t+i+1-divided paper.
Let (t,i) is a state of t-divided paper using i segments.
Then, (t,i) -> (t+1,i+1) , (t+2,i+1) , ... (t+i-1,i+1).

Code

int main() {

int t;cin>>t;

while(t--){

int m;cin>>m;

for(int i=0;i<m;++i){

if(1+i*(i+1)/2>=m){

cout<<i<<endl;

break;

}

return 0;

}

2015年3月1日日曜日

HackerRank: AntiPalindromic Strings

問題

https://www.hackerrank.com/challenges/antipalindromic-strings
m種類のアルファベットによって表記されるn文字の全ての文字列の中で、その2文字以上の連続部分文字列として回文を一つも含まないようなものは何通りあるか。

解法

nとmで表せる。

CF 518 C. Anya and Smartphone

問題

http://codeforces.com/problemset/problem/518/C
スマホのホーム画面のアイコンを選択するのに最小のタップ数を求める感じの問題。

解法

読んで書くだけ

CF 518D. Ilya and Escalator

問題

エスカレーターの前にn人並んでいる。先頭の人は1分毎に確率pで勇気を振り絞ってエレベーターに乗り、1-pでその場にとどまる。エレベーターに乗れるのは先頭の人だけ。また、一度乗ったエレベーターは二度とおりることはない(こわい)
この時、t分後にエレベーターに乗っている人数の期待値を求める問題。

解法

前からi番目の人がt分以内に乗る確率をDPで求めて足す。

CF 518F. Pasha and Pipe

問題

http://codeforces.com/problemset/problem/518/F

二次元グリッド内にパイプが何通り引けるかを求める問題。

グリッドのセルは * か . で構成されていて、パイプは . のセルにしか引けず、更に様々な条件がある。

解法

[座標][次に向かおうとする方向][何回曲がったか]でDP.

CF 514 E. Darth Vader and Tree

問題

http://codeforces.com/problemset/problem/514/E
各ノードの子の数がn個でそれぞれの子へのエッジの重みがd[i]で与えられた木に対して、根ノードから距離x以下にあるノードの個数をカウントする問題。

解法

d[i]の範囲が1以上100以下なので100*100の行列にして繰り返し二乗法

Le Algorithm