SRM621の500で閃いたアルゴリズムがちょい面白い気がしたのでメモっておく。 問題自体の解法に直接は触れないので、解説が見たい方は別のところを参照してください。以下の問題を考えます。木をDFS的に探索する。 ある頂点を見ている時に、その頂点から下向…

レッドコーダーに一瞬なってから負け続けてレーティングだだ下がりのまま年を越してしまいました。今年はレッドコーダーでしばらく停滞することを目標にします。 最近練習全然できていないので今のままではムリですね。 SRM練習どこかのタイミングで再開した…

本日付けで会社退職しました。 1週間ほどニートした後に次の仕事はじめます。 早くニートになりたい人よりも先にニートになれました。研修期間を除くと1年と4ヶ月ほどいたことになると思います。 転職の動機はいろいろありますが、開発志望で入ったのに開発…

書籍「RailsによるアジャイルWebアプリケーション開発」のインストール中の話。 Ubuntuで以下のコマンドが失敗する。 $ sudo rvm install 1.9.2以下で対処。 $ sudo emacs /var/cache/ruby-rvm/src/ruby-1.9.2-p180/ext/openssl/ossl_ssl.c 以下をコメントア…

先日TopCoderのAlgorithmでレーティングが2200を超え、赤コーダーになりました。 あと1,2年はかかると思っていたので、自分でもびっくりしています。http://community.topcoder.com/tc?module=MemberProfile&cr=228814592010年の7月から始めたみたいなので3…

Boost1.53.0リリースされてましたね。個人的に気になっているのはCoroutine。 pythonのyeildみたいなことが出来るライブラリ。ローカル変数の寿命が気になったのでちょいと調べた。 #include <boost/coroutine/coroutine.hpp> #include <iostream> typedef boost::coroutines::coroutine<int()> coroutine_typ</int()></iostream></boost/coroutine/coroutine.hpp>…

これまた難しい問題だったけど、綺麗な解法を思い浮かんで気持ちよかった。(問題概要) 立方体の展開図が文字列で与えられる。 立方体の展開図として正しいかどうか判断せよ。(解法) サイコロの展開図として考える。 展開図にそってサイコロを転がして、接地…

ほとんど毎日考えてたけど結局わからなかったのでeditorial見た(問題概要) 目の平均値がM以下になるようなサイコロの作り方は何通りあるか。 ただし全ての目は異なる。(解法) 差分形式に式変形していくとDPに落とせるようだ。 これは難しいけど、汎用的に使…

年末年始はノーカンだから！

インライン化されるのか調べた。 されるっぽい(g++ 4.6.3調べ)。すばらしい。 まあ関数オブジェクト作ってるだけらしいので当たり前かもしれないけど。 int func(int x){ const auto inc = [](int x){ return x + 1; }; return inc(x); } これが _Z4funci: .…

(問題概要) n ( 幾つかのポストカードをすでに持っている。 持っているポストカードは同じ価格で売ることができる。 価値Kを得るにはいくら追加でお金がいるか。(解法) とりあえず持ってるのは全部売って、一から考えると楽。 問題形式的には典型的ナップザ…

(問題概要) 文字列が幾つか与えられる。 すべての文字列が空になるまでどれかの文字列の先頭文字をくっつける操作を繰り返す。 辞書順最小の文字列を作りなさい。(解法) 貪欲に最小なのをとっていく。 文字列がなくなるケースはあまり嬉しくないのを考慮。 …

(問題概要) A_i = 1 for all i A_i = A_[i/p]-x + A_[i/q]-y A_nを求めよ。(n (解法) メモ化再帰。 ただし全部をmap等でメモるとMLEでセグるので、部分的にメモる。 なんかチーター本で見たような気もする。 typedef long long ll; #include <queue> #include <set> #inc</set></queue>…

※この記事はCompetitive Programming Advent Calendar Div2012 の19日目の記事です。競技プログラミングにおいて、時間内に正しい答えを出せる限り手を抜く(簡単なプログラムを書くの意)のが定石。 ということでとある問題を題材に探索っぽくして幾何で手を…

(問題概要) ２つのTAB譜の変換(解法) やるだけ。制限が色々めんどい。 最近なら250〜300で出ても驚かないレベルの内容。 #include <algorithm> #include <cstdio> #define REP(i,n) for(int i=0; i<(int)(n); i++) #include <queue> #include <set> #include <iostream> #include <sstream> using namespace std</sstream></iostream></set></queue></cstdio></algorithm>…

(問題概要) 回 ← みたいなケーキがある(真ん中に穴が空いてる) 縦と横にそれぞれ何回か包丁を入れた時に、最終的に何ピースのケーキが出来るか。(解法) 縦横で近いカットを２つづつ選ぶとそれに囲まれた四角形ができる。 後はその頂点を見て場合分け。 関数…

(問題概要) nバイトのメモリ、kバイトのキャッシュを持ったマシンを考える。 キャッシュにはメモリ上の連続したkバイトを載せることが出来る。 キャッシュを更新するには、更新前に載っていなかったバイト数だけコストがかかる。 アクセスするアドレス(a[0],…

(問題概要) 本物がspheresCount個、偽物がfakeSpheresCount個、全体からspheresCount個選んで全部正しいかを試す。 全通りを何グループかで試すとき、各グループが同じ通り数を試すには、gnomesAvailable以下で最大何グループ選べるか。 (nCk % m == 0 とな…

(問題概要) acyclicなグラフ(|G| 操作： ノードに2つの飴があるとき、ひとつ食べて、ひとつを隣接ノードに移動 という操作が可能。 操作を繰り返して、目的のノードに飴を置くことが"できない"ようにする時に、最大何個飴を置けるか。(解法) 少し考えると、…

(問題概要) 平面上の点(12個以下)を自分が赤、相手が青で自分から交互に塗っていく。 最後に色の違う点の全対に対して、距離の和が得点になる。 相手は得点を最小にするように最適に動く。 最大何点得られるか。(解法) 点の数が少ないので、bitDPすれば良い…

(問題概要) 数値がグリッド上に書かれた紙を折りたたんで行って重なった数値の合計を最大化する。(解法) 縦と横を独立に考えることができる。 縦横は各全探索 #include <algorithm> #include <cstdio> #define REP(i,n) for(int i=0; i<(int)(n); i++) #include <queue> #include <set> #inc</set></queue></cstdio></algorithm>…

(問題概要) 有向グラフが与えられる(ノード数 好きなところからスタートしてi回(i = 1, 2, ...)の移動後最初の地点に戻れるか。 各iに対して戻れるなら1戻れないなら0を並べたものを計算せよ。 ただし結果は以下の一番短くなるフォーマットで 010(110) (意味…

ゲシュタルト崩壊したリアルが忙しすぎるので週末に解く

ムズイので2,3日考えます

(問題概要) A[0] .. A[n - 1] (引数から線形合同法みたいなので構成) に対して、s(i, k) = A[i] + ... + A[i + k - 1] とする。 s(i, k) - s(j, k) (i + k - 1 を最小にするkとその値を求めよ。(解法) kを1ずつ増やしていった時に、s(i, k) (i = 0 .. n-1) …

(問題概要) 4, 7だけで構成された数値をLucky numberとする。 以下を満たす長さlengthの数列は何個あるか ∀i, A[i] is Lucky number ∀i, ∃j, A[i] = numbers[j] ∀i, last digit of A[i] == first digit of A[i + 1] (解法) numbersのうちのLucky numberだけ…

(問題概要) 循環する文字列の連続する'X'を1箇所消して、連続する'.'の数を最大化する (正確には連続する'.'の数の配列を辞書順最大化する)(解法) ただのシミュレーション。おもしろくない・・・ #include <algorithm> #define REP(i,n) for(int i=0; i<(int)(n); i++) </algorithm>…

(問題概要) 省略(直線or点と螺旋の交点)(解法) 直線によって超場合分け。 基本的には円と直線の交点だして、螺旋に乗ってるか判定。 こういう問題苦手。何度も再提出。 #include <cstdio> #include <complex> #include <cstdlib> #include <queue> #include <set> #include <iostream> #include <sstream> using namesp</sstream></iostream></set></queue></cstdlib></complex></cstdio>…

SRM401に繋がらないのだ

競プロもうちょっと上に行きたいモチベあるので、mediumを不定期で解き漁る。 週に２，３問、問題は飛ばさずに全部解く、を目標。 続けるモチベの為にブログに解法乗っけていく。 とりあえず400くらいから順番に解いていくつもり。初回はSRM400 500 ReverseC…