前回(動的計画法(Dynamic Programming)演習 - るくすの日記 ~ Out_Of_Range ~)の続き。今回は該当するDiv2Hardのうち13問解きました。 [Div2](SRM354) 1000:UnsealTheSafe dp[i][j] := i-1番目にjを押すようなパスワードの総数 sum += dp[i - 1][keypad[ny][…

タイトルのまんまです。 TopCoder SRMの過去問から解法に「Dynamic Programming」が含まれている問題をレベルで昇順にソートして解いていきます。 該当するDiv2Medium全18問中15問解きました。(残り3問は、dpでふつう解かないだろうみたいな問題だったので別…

[問題] 2112 -- Optimal Milking牛とミルクマシーン(適当)が辺で接続されている。全ての牛をミルクマシーンに到着させたい。この時もっともたくさん歩く牛の距離を最小化せせよ。ただし、ミルクマシーンはm匹の牛しか処理できない。 [解法] WarshallFloyd + …

[問題文] 1949 -- ChoresN個の仕事がある。それぞれにかかる時間と、その仕事より必ず先に終わらせなければならない仕事k個の情報が与えられる。 仕事は並列で行うことができる。N個の仕事を終わらせるのにかかる時間を最小化せよ。 [解法] トポロジカルソー…

[問題文] AIZU ONLINE JUDGE [解法] 構文解析 慣れていないのでかなり時間がかかった。 こんなやつの解析 <exp>::= "(" , <exp> , <exp> , ")" | "" 結構楽しい。 struct E{ int l,r,id; int over; E(){ l = r = -1 ,id = 0; over = 0;} }; int now; int p = 0; E memo[400]</exp></exp></exp>…

[問題文] AIZU ONLINE JUDGE [解法] dp + UF木 数列を作っておいて、UF木で集合を作る。 int par[2000]; int rank[2000]; void init(int n){ rep(i,n) par[i] = i; memset(rank,0,sizeof(rank)); } int find(int x){ if(par[x] == x) return x; return par[x…

先日部で、2泊3日の東京遠征に行ってきました。 1日目は秋葉原、2日目は発表練習、そして3日目はGoogle社に訪問させていただきました。Google社では社内食堂で、かの有名な『Binary Hacks』の著者の方とお食事、お話させていただいた後、エンジニアの方々の…

250 TheBrickTowerEasyDivTwo並べるだけ class TheBrickTowerEasyDivTwo { public: int find(int redCount, int redHeight, int blueCount, int blueHeight) { int now_h = 0; int C[2] = {blueCount,redCount}; int H[2] = {blueHeight,redHeight}; memset(…

1651 -- Multiplication Puzzle [問題] N枚のカードが与えられる。これらの中から任意の1枚を取り除く。この際、選んだカード * 左のカード * 右のカードのスコアが加算される。ただし両端のカードは選べない。 可能な限りこれらの操作を繰り返した時の合計…

1611 -- The Suspects [問題] いくつかのグループとそこに所属する生徒のメンバーの情報が与えられる。0番の生徒が強力な風邪菌(意訳)を持っていて、同じグループに所属している生徒に感染してしまう。感染は推移的であり、例えば aグループ と bグループ両…

1564 -- Sum It Up [問題] N個の要素からなる集合が与えられます。合計がtとなる任意の部分集合をdecreasing orderで出力してください。(例) Input: t = 400 N = 12 [50 50 50 50 50 50 25 25 25 25 25 25]Output: Sums of 400: 50+50+50+50+50+50+25+25+25+…

3671 -- Dining Cows [問題] 1または2がランダムにN個並んでいる。任意の箇所を1 -> 2 もしくは 2 -> 1と書き換えることで、全ての1が2より前に来るようにしたい。 書き換える回数の最小値を求めよ。 [解法]1グループと2グループをどこで分けるかで全探索。…

2186 -- Popular Cows [問題] M個のペア(A,B): 牛Aが牛Bを人気者だと思っている が与えられる。ただし (A,B) ,(B,C) => (A,C) とする。(関係は推移的) 自分以外の全ての牛から人気者だと思われている牛の数を求めよ ずっと放置していた蟻本の問題。 すべての…

問題文→ 2140 -- Herd Sums[問題] 自然数Nが与えられる。 Nを連続した自然数の和で表すと何通りできるか。(例) N = 15 [7+8 , 4+5+6 , 1+2+3+4+5 , 15] 4通り Sum(b) - Sum(a-1) = Sum([a,b]) みたいなことすると O(n^2)とかになって間に合わない。なので S(…

問題文→AIZU ONLINE JUDGE 10進数を-10進数に直す問題。 x mod (-10)^nをやっていく (負になった時は正にしてやる) string Trans(int n){ string ans=""; while(n != 0){ int mod=n%(-10); int nxt=n/(-10); if(mod < 0){ mod+=10; nxt++; } char c='0'+mod;…

問題文→AIZU ONLINE JUDGEテープが貼ってあるので、囲まれる領域の数を答える問題。 座標圧縮+幅優先でいける。座標圧縮の解説が少なすぎて萎え...一応この問題、第7回JOIの本選5番なのでそこの解説を見れば座標圧縮の大まかな説明が載っている→ 書く量多す…

問題文→AIZU ONLINE JUDGE正解者数少なかったので、怖くて手をつけていなかった問題。やっと解けたのですごく嬉しいです。メモ化探索しました(ほとんどの方がdpしていたのでそっちの方が良かったかも...) #include<iostream> #include<cstdio> #include<algorithm> #include<vector> #include<string> #inc</string></vector></algorithm></cstdio></iostream>…

問題文→ 3041 -- AsteroidsN*Nの格子上にK個の小惑星があります。小惑星iの位置は(R[i],C[i])にあります。縦または横一直線上の小惑星をすべて一発のビームで破壊できる強力な武器があり、これを用いてすべての小惑星を破壊するために必要な最小の発射回数を…

ネット復旧したので休憩がてらPythonでスクリプト書いてみました。 PKUの各問題を.txt形式に変換するスクリプトです。 変換する問題の範囲を指定できますが、あまり多くしすぎるとDOS攻撃に近い動きをするので、変換は間を置いて少しずつするようにします。(…

問題文→2104 -- K-th Numbersort()とか使うと間に合わないので 区間ごとのx以下の個数を二分探索で数えます。しかし二分探索にはソートが必要なのでマージソートの要領でセグメント木を作っておき、必要な区間に対してのみ二分探索を行えば間に合うみたいで…

問題文→ AIZU ONLINE JUDGE「あるマスを選んでそこの数字を反転(1 0)させる。 この時そのマスの上下左右も反転する。 すべてを0にするために必要な反転箇所を求めよ」 という問題。普通に考えたら O(2^100)とかで無理。 そこで一番上の行の反転の仕方を一意…

問題文→2385 -- Apple Catchingりんごが1分ごとに2本の木のいずれかから落ちてくる。2本の木を決められた回数内行き来して落ちてくるりんごをキャッチする。 キャッチできるりんごの合計の最大値を求めよ。とりあえずメモ化再帰を書いてみる。しかしこれでは…

問題文→AIZU ONLINE JUDGEマスの数を指定して魔法陣を出力する問題 #include<iostream> #include<cstdio> #include<algorithm> #include<vector> #include<string> #include<cmath> #include<map> using namespace std; int context[15][15]; void init(){ for(int i=0;i<15;i++){ for(int j=0;j<15;j++){ context[i][j</map></cmath></string></vector></algorithm></cstdio></iostream>…

printf()関数の脆弱性を利用した攻撃手法です。とりあえず以下のコードを見てください。 #include <stdio.h> #include <stdlib.h> #include <string.h> int main(int argc, char *argv[]) { //お客様の名前を表示---- char text[1000]; strcpy(text,argv[1]); printf(text); printf("\n");</string.h></stdlib.h></stdio.h>…

競技やったりセキュリティ勉強したりといろいろな分野に手を出しすぎている感は否めませんが、とりあえず今回はセキュリティのことについて書きます。脆弱性としてもっとも基本的なものとして「バッファオーバーフロー」が挙げられます。自分の書いたプログ…

今日は時間があまり無かったので5問だけ解きましたSRM488(Score):231.03そんなに難しくない class TheBoredomDivTwo { public: int find(int n, int m, int j, int b) { int result=n; if(j==b && n

最近TopCoderの成績がひどいので、とりあえずDiv2Easyを確実にとれるようにしようと思ってプラクティスしました。 てことでDiv2Easy 10連戦のソース(プリプロセッサ部分とかもろもろは省略してます)SRM416 map使って解いた class MostCommonLetters { public…