当方、elscreenではなくtabbarを使っている少数派です。
以前、tabbar.elのグループ化機能をせっかくだから使ってみるなんて投稿をしました。
しばらく封印していたのですが、修正を加えた上で最近また使っています。バッファの数が増えた時に便利です。
溜まった設定の一部を切り出してgistに投げて見ました。名付けてtabbar+.el。
しかし、以前のコードは見るに耐えない。そしてdash.elが便利。
12/18/2012
12/13/2012
12/09/2012
12/02/2012
12/01/2012
11/23/2012
11/21/2012
11/15/2012
SRM527 Div1 Medium
450
辞書順最小は先頭から決める。
1つ以上の答えがあるそうなので、順に0を割り当てて試す。
ある場所に0を割り当ててマトリックスを作れないのならば、そこに1を入れればいい。
マトリックスになるかどうかは、2部マッチングをすればよい。
辞書順最小は先頭から決める。
1つ以上の答えがあるそうなので、順に0を割り当てて試す。
ある場所に0を割り当ててマトリックスを作れないのならば、そこに1を入れればいい。
マトリックスになるかどうかは、2部マッチングをすればよい。
ラベル: SRM
11/11/2012
LiveArchive4035
4035 - Undetectable Tour
どういう場合に到達不可能になるのかを考える。
センサーのカバーしている領域だけを通って
"領域の上から領域の下まで移動できる"
"領域の上から領域の右まで移動できる"
"領域の左から領域の下まで移動できる"
"領域の左から領域の右まで移動できる"
の4つの条件のうち1つでも満たせば到達不可能になる。
全てのセンサーの位置と各センサー(x, y)から最短で行ける領域の端(x, 0), (0, y), (x, N-1), (N-1, y)の位置を頂点とする様なグラフを作る。
(始点と終点の扱いには注意すること。領域の端を全て頂点にしてしまうとTLEする。)
このグラフ上で4つの条件のどれかを満たす様なパスの最大の辺の重みの最小値がセンサーに捕捉されずに到達可能な距離の上限になる。
やりかたは色々あるだろうけど、条件を満たすまで辺の重み順にUnionFindした。
どういう場合に到達不可能になるのかを考える。
センサーのカバーしている領域だけを通って
"領域の上から領域の下まで移動できる"
"領域の上から領域の右まで移動できる"
"領域の左から領域の下まで移動できる"
"領域の左から領域の右まで移動できる"
の4つの条件のうち1つでも満たせば到達不可能になる。
全てのセンサーの位置と各センサー(x, y)から最短で行ける領域の端(x, 0), (0, y), (x, N-1), (N-1, y)の位置を頂点とする様なグラフを作る。
(始点と終点の扱いには注意すること。領域の端を全て頂点にしてしまうとTLEする。)
このグラフ上で4つの条件のどれかを満たす様なパスの最大の辺の重みの最小値がセンサーに捕捉されずに到達可能な距離の上限になる。
やりかたは色々あるだろうけど、条件を満たすまで辺の重み順にUnionFindした。
ラベル: LiveArchive
SRM495 Div1 Easy
275
memo[どこまで見た][最後に使った数] = 最後まで作りきれるかどうか
バックトラックしていたら終わらないので、到達可能かどうかをメモ化する。
到達可能と判断できた瞬間にそれまでのパスをなぞる。
memo[どこまで見た][最後に使った数] = 最後まで作りきれるかどうか
バックトラックしていたら終わらないので、到達可能かどうかをメモ化する。
到達可能と判断できた瞬間にそれまでのパスをなぞる。
ラベル: SRM
11/02/2012
10/04/2012
9/29/2012
LiveArchive5848
分割統治。
領域を縦と横に2分割して、4つの領域に分ける。
縦は2種類の点を分ける様なX軸に垂直な直線で分割し、横はそれっぽい直線で分割する。
横方向に隣合う領域同士の近い点か、斜めの領域同士の点から最近点を探す。
互いに斜めな領域同士の点の移動は、分割に使った縦と横の線の交点を通る様な移動を考える。
あとは、点の数が少なくなるまで横の分割を繰り返す。
領域を縦と横に2分割して、4つの領域に分ける。
縦は2種類の点を分ける様なX軸に垂直な直線で分割し、横はそれっぽい直線で分割する。
横方向に隣合う領域同士の近い点か、斜めの領域同士の点から最近点を探す。
互いに斜めな領域同士の点の移動は、分割に使った縦と横の線の交点を通る様な移動を考える。
あとは、点の数が少なくなるまで横の分割を繰り返す。
ラベル: LiveArchive
9/21/2012
9/14/2012
9/13/2012
SRM555 Div2 Hard
955
DP1[ n ] = n マス連続して泥でないときの行き方が偶数通りか奇数通りか。
DP2[どこまで見た][泥のマスがいくつか][ 偶数通りの行き方がこれまであったか ]
o を乾いたマス、x を泥のマスとした場合、oooxoooo の行き方は"3マス連続して泥でない道の行き方"×"4マス連続して泥でない道の行き方"になる。
つまり、泥のマスで区切ったそれぞれの連続して泥でない道の行き方の中に偶数通りの行き方のある部分があれば、
全体も偶数通りの行き方が存在することになる(偶x偶=偶、偶x奇=偶、奇x奇=奇)。
前計算で n マス連続して泥でない場合の行き方を計算しておく。
その後、ある2つの泥のマスの間にいくつの乾いたマスを挿入するかというDPを行う。
両端に泥のマスを付け加えるとやりやすかった。
DP1[ n ] = n マス連続して泥でないときの行き方が偶数通りか奇数通りか。
DP2[どこまで見た][泥のマスがいくつか][ 偶数通りの行き方がこれまであったか ]
o を乾いたマス、x を泥のマスとした場合、oooxoooo の行き方は"3マス連続して泥でない道の行き方"×"4マス連続して泥でない道の行き方"になる。
つまり、泥のマスで区切ったそれぞれの連続して泥でない道の行き方の中に偶数通りの行き方のある部分があれば、
全体も偶数通りの行き方が存在することになる(偶x偶=偶、偶x奇=偶、奇x奇=奇)。
前計算で n マス連続して泥でない場合の行き方を計算しておく。
その後、ある2つの泥のマスの間にいくつの乾いたマスを挿入するかというDPを行う。
両端に泥のマスを付け加えるとやりやすかった。
ラベル: SRM
8/24/2012
8/23/2012
SRM436 Div2 Hard
1000
x[i] != y[i] なインデックスを見つけて、それ以下を x[i], y[i] と逆の大小関係になるようにする。
自前のBigIntは略。
x[i] != y[i] なインデックスを見つけて、それ以下を x[i], y[i] と逆の大小関係になるようにする。
自前のBigIntは略。
ラベル: SRM
8/09/2012
SRM437 Div2 Hard
1000
メモ化する。
n の m 乗根を探していけばいい。
解法はすぐに思いつくけど、通すのは難しい気がする。
本番通した人はエスパーに違いない。
メモ化する。
n の m 乗根を探していけばいい。
解法はすぐに思いつくけど、通すのは難しい気がする。
本番通した人はエスパーに違いない。
ラベル: SRM
8/05/2012
7/22/2012
7/19/2012
7/13/2012
7/12/2012
Codeforces Round #129 (Div. 2)
ABCDを解いた。
A: やるだけ
B: どういう数列に変化させるのが最適かは簡単に分かる。1ステップでは出来る限り範囲をインクリメントするべき。
C: dp[ n桁目 ][ 最後に使った数字 ][ 小さくなったか ][ 最初の非 0 の数字 ]
D: やるだけ
以下、本番で投げたコード
A: やるだけ
B: どういう数列に変化させるのが最適かは簡単に分かる。1ステップでは出来る限り範囲をインクリメントするべき。
C: dp[ n桁目 ][ 最後に使った数字 ][ 小さくなったか ][ 最初の非 0 の数字 ]
D: やるだけ
以下、本番で投げたコード
ラベル: codeforces
7/09/2012
7/03/2012
6/29/2012
6/26/2012
SRM547 Div1 Medium
500
式を出して計算するだけ。ちょっとした枝刈りをしないとタイムアウト?
サブテーブルのサイズが横 i 縦 j で、左上が x のとき、そのテーブルの数字の合計は
i * j * ( 2 * x + ( j - 1 ) + width * ( i - 1 ) ) = 2 * S
式を出して計算するだけ。ちょっとした枝刈りをしないとタイムアウト?
サブテーブルのサイズが横 i 縦 j で、左上が x のとき、そのテーブルの数字の合計は
i * j * ( 2 * x + ( j - 1 ) + width * ( i - 1 ) ) = 2 * S
ラベル: SRM
6/25/2012
6/21/2012
6/19/2012
6/18/2012
6/17/2012
SRM546 Div1 Easy
250
本番では解けなかった。
2進数表現にすると分かりやすい。
奇数なら n-1, 偶数なら n/2 という列に登場するという事は、
最上位が K で始まるということ。
なぜ気が付かなかった・・・。
本番では解けなかった。
2進数表現にすると分かりやすい。
奇数なら n-1, 偶数なら n/2 という列に登場するという事は、
最上位が K で始まるということ。
なぜ気が付かなかった・・・。
ラベル: SRM
6/13/2012
6/12/2012
6/11/2012
SRM545 Div1 Medium
500
ある点を最後にシグナルを発信する位置にする。
その点から原点までの間に整数座標の点がいくつあるかを、GCDで求める。
その中から K - 1 コの点を選ぶ組み合わせだけ、選び方が存在する。
原点のから以外にも同様な線分を引くことができるので、その分を掛け算する。
K == 1 の時だけ別処理。
ある点を最後にシグナルを発信する位置にする。
その点から原点までの間に整数座標の点がいくつあるかを、GCDで求める。
その中から K - 1 コの点を選ぶ組み合わせだけ、選び方が存在する。
原点のから以外にも同様な線分を引くことができるので、その分を掛け算する。
K == 1 の時だけ別処理。
ラベル: SRM
6/08/2012
SRM545 Div1 Easy
275
先頭から1文字ずつ作る。
ある文字を次に付け足す場合、
(これまでに作った文字列) + (次に付け足す文字) + (残りを降順に並べた文字列)
で出来る文字列がこれ以降で inv の数を最大にでできて、辞書順で最も大きい。
あとは、minInv と minStr の条件を満たせる範囲で最も辞書順で小さい文字を順に付け加えていくだけでいい。
先頭から1文字ずつ作る。
ある文字を次に付け足す場合、
(これまでに作った文字列) + (次に付け足す文字) + (残りを降順に並べた文字列)
で出来る文字列がこれ以降で inv の数を最大にでできて、辞書順で最も大きい。
あとは、minInv と minStr の条件を満たせる範囲で最も辞書順で小さい文字を順に付け加えていくだけでいい。
ラベル: SRM
6/01/2012
SRM410 Div2 Hard
1000
memo [ テキストの i 文字目まで作った ][ 正規表現の j 文字目まで使った ] = pair( cost, string )
文字列の辞書順最小パスな問題は逆からやるのが吉だった気がする。
memo [ テキストの i 文字目まで作った ][ 正規表現の j 文字目まで使った ] = pair( cost, string )
文字列の辞書順最小パスな問題は逆からやるのが吉だった気がする。
ラベル: SRM
5/31/2012
5/30/2012
5/28/2012
SRM408 Div2 Hard
1000
memo[ 4000 + 1 ][ 4000 + 1 ] だとメモリでアウト
赤を数千回連続で引く確率は十分小さいので、
memo[ 1000 + 1 ][ 4000 + 1 ] くらいでやればいい。
memo[ 4000 + 1 ][ 4000 + 1 ] だとメモリでアウト
赤を数千回連続で引く確率は十分小さいので、
memo[ 1000 + 1 ][ 4000 + 1 ] くらいでやればいい。
ラベル: SRM
5/27/2012
5/23/2012
5/22/2012
5/21/2012
5/20/2012
SRM401 Div2 Hard
1000
お手上げ。解説を読む。
KMP の接頭語関数の最後の要素と文字長の差を見るらしい
接頭辞関数って、最長の接頭辞の長さだよね・・・。
スパソから KMP を拝借してサブミット
お手上げ。解説を読む。
KMP の接頭語関数の最後の要素と文字長の差を見るらしい
接頭辞関数って、最長の接頭辞の長さだよね・・・。
スパソから KMP を拝借してサブミット
ラベル: SRM
5/18/2012
5/15/2012
SRM503 Div1 Easy
250
答えは2, 1, -1の3つしかない。
最後のサンプルを見ると何となく察しがつく。
あとはそれぞれの最小値と最大値を見てそれっぽい解を返せばいい。
答えは2, 1, -1の3つしかない。
最後のサンプルを見ると何となく察しがつく。
あとはそれぞれの最小値と最大値を見てそれっぽい解を返せばいい。
ラベル: SRM
5/14/2012
5/13/2012
5/11/2012
5/09/2012
SRM542 Div1 Easy
250
まず、Tを決める。
高さ H 幅 W の四角形を考える。端から端まで使うような経路では T = 2 * (H + W)
中継地点の座標の選び方は (H - 1) * (W - 1) 通り。
その四角形の中から3点を選ぶパターンは、X座標Y座標を３つずつ選んで、
それを組み合わせてできる座標の数。つまり、3!
ex.) X = {0, a, W}, Y = {0, b, H} から作れる座標を組みは3!通り。
それを掛けて足しあわせていけばいい。
分かりやすく説明できないー。
まず、Tを決める。
高さ H 幅 W の四角形を考える。端から端まで使うような経路では T = 2 * (H + W)
中継地点の座標の選び方は (H - 1) * (W - 1) 通り。
その四角形の中から3点を選ぶパターンは、X座標Y座標を３つずつ選んで、
それを組み合わせてできる座標の数。つまり、3!
ex.) X = {0, a, W}, Y = {0, b, H} から作れる座標を組みは3!通り。
それを掛けて足しあわせていけばいい。
分かりやすく説明できないー。
ラベル: SRM
5/07/2012
SRM509 Div1 Easy
250
9で割った余りなのが重要。10^nをかけたとしても、あまりに変化がない。
そして、各数字は 2^(文字列の長さ) 回だけ登場する。
小さいケースを手で試していたら気がついた。
簡単だとも思わないけど、Editorials を見る限りでは正答率が低いわけではない。
こういう類を苦手に思わない人たちってのはどういう過程を経て答えに行き着くのか・・・。
9で割った余りなのが重要。10^nをかけたとしても、あまりに変化がない。
そして、各数字は 2^(文字列の長さ) 回だけ登場する。
小さいケースを手で試していたら気がついた。
簡単だとも思わないけど、Editorials を見る限りでは正答率が低いわけではない。
こういう類を苦手に思わない人たちってのはどういう過程を経て答えに行き着くのか・・・。
ラベル: SRM
4/26/2012
SRM514 Div1 Easy
250
n が奇数の場合は(X + Y)が奇数の場所にしか行けない。
n が偶数の場合はどこへでも行ける。
サンプルの最初2個では、nが2と3。
BFSで行ける場所を出力してみたら気がついた。
近い位置だけBFSで調べた後に(X, Y)から(0, 0)へ山を登ると
X, Yの値の範囲が大きすぎてうまくいかない。
n が奇数の場合は(X + Y)が奇数の場所にしか行けない。
n が偶数の場合はどこへでも行ける。
サンプルの最初2個では、nが2と3。
BFSで行ける場所を出力してみたら気がついた。
近い位置だけBFSで調べた後に(X, Y)から(0, 0)へ山を登ると
X, Yの値の範囲が大きすぎてうまくいかない。
ラベル: SRM
4/25/2012
4/24/2012
SRM480 Div1 Medium
450
あるクライアントとあるサーバを直に結ぶケーブルにゲートを設置するかどうかは、
トポロジカル順序でそのクライアントとサーバの間にあるコンピュータのかに、
そのクライアントから到達可能で、そのサーバへ到達可能なコンピュータが１つでもあるかどうかによる。
あるクライアントとあるサーバを直に結ぶケーブルにゲートを設置するかどうかは、
トポロジカル順序でそのクライアントとサーバの間にあるコンピュータのかに、
そのクライアントから到達可能で、そのサーバへ到達可能なコンピュータが１つでもあるかどうかによる。
ラベル: SRM
4/22/2012
TCO2012 2A
参加記録。何も出来なかった。
300 :
2部マッチングして正当性を確かめるまでは思い浮かんだけど
log2 で分類しきれるという所に最後まで気がつかなかった。
もっとシンプルな方法で解いてる人がいるけど、あれは何をやっているのか・・・。
450 :
読んだだけ。
1000 :
開いてない。
300 :
2部マッチングして正当性を確かめるまでは思い浮かんだけど
log2 で分類しきれるという所に最後まで気がつかなかった。
もっとシンプルな方法で解いてる人がいるけど、あれは何をやっているのか・・・。
450 :
読んだだけ。
1000 :
開いてない。
4/21/2012
4/20/2012
4/16/2012
4/12/2012
4/11/2012
SRM531 Div1 Medium
500
行列累乗で挑んだけど、どうにも通らない。
行列やシミュレーションのようなアプローチだと mod が悪さをするらしく、複数の mod で試す必要があるらしい。
素直にグラフにしてやった。
path[ 0 ][ i ] == true
path[ i ][ i ] == true
out_degree[ i ] > 1
を満たす頂点が存在したら無限に増える。
行列累乗で挑んだけど、どうにも通らない。
行列やシミュレーションのようなアプローチだと mod が悪さをするらしく、複数の mod で試す必要があるらしい。
素直にグラフにしてやった。
path[ 0 ][ i ] == true
path[ i ][ i ] == true
out_degree[ i ] > 1
を満たす頂点が存在したら無限に増える。
ラベル: SRM
4/10/2012
4/09/2012
4/08/2012
TCO2012 1B
参加記録。通過したけど、残念な結果。
250 :
やるだけ。やるだけにも関わらずFailedSystemTest。
500 :
メモ化した。memo[区間の先端][区間の終端][今何匹か]
貪欲とか2分探索みたいな解法の人もいた。
1000 :
読んでない。
250 :
やるだけ。やるだけにも関わらずFailedSystemTest。
500 :
メモ化した。memo[区間の先端][区間の終端][今何匹か]
貪欲とか2分探索みたいな解法の人もいた。
1000 :
読んでない。
4/06/2012
4/05/2012
4/02/2012
4/01/2012
3/25/2012
ClojureでLispインタプリタ
思いつきでやってみた。意外と面白かった。
ちゃんと動くかは自信がない。
関数を定義するときに [ ] を使わないといけないのは気にしない。
ちゃんと動くかは自信がない。
関数を定義するときに [ ] を使わないといけないのは気にしない。
ラベル: Clojure
3/24/2012
UVa12338
UVa12238
接尾辞配列ライクなことをやる。
与えられた文字列をソートし、となりあう文字列の一致する最長のプレフィックス (LCP) を求める。
それに RMQ を使ってクエリーを処理する。
A[i] と A[i+1] のプレフィックスが n 文字目まで一致していて、
A[i+1] と A[i+2] のプレフィックスが m 文字目まで一致していれば、
A[i] と A[i+2] は min(n, m) 文字目までのプレフィックスが一致していることになる。
A[j]とA[k]のプレフィックスはRMQ(j, k)文字目まで一致することになる。
このアプローチで実行時間が3秒強。タイムリミットが5秒。
ラディックスソートとか使えばもっと早くなるかも？
ラベル: UVa
3/23/2012
SRM537 Div2 Hard
925
とりあえず、グラフにする。
あるトーストを学ぶために食べるトーストの枚数は最小で１、最大でルートまでの距離
全ての頂点に関して試す。
点数も1000より低いし、本番でも40人以上が通してるけど、そんなに簡単とは思えなかった。
とりあえず、グラフにする。
あるトーストを学ぶために食べるトーストの枚数は最小で１、最大でルートまでの距離
全ての頂点に関して試す。
点数も1000より低いし、本番でも40人以上が通してるけど、そんなに簡単とは思えなかった。
ラベル: SRM
SRM502 Div2 Hard
1000
DPする。
DP[何匹目まで見た mod 2][数字の合計 mod N][何匹が逃げた];
この実装だと、実行時間がそうとうギリギリ。
テーブルの半分を毎回初期化するのはもちろん、剰余算を少し余計にやっただけでアウト。
DPする。
DP[何匹目まで見た mod 2][数字の合計 mod N][何匹が逃げた];
この実装だと、実行時間がそうとうギリギリ。
テーブルの半分を毎回初期化するのはもちろん、剰余算を少し余計にやっただけでアウト。
ラベル: SRM
3/22/2012
3/21/2012
SRM Div2 まとめ
300代あたりは後でマージするかも？
SRM400 Easy Medium Hard
SRM401 Easy Medium Hard
SRM402 Easy Medium Hard
SRM403 Easy Medium Hard
SRM404 Easy Medium Hard
SRM405 Easy Medium Hard
SRM406 Easy Medium Hard
SRM407 Easy Medium Hard
SRM408 Easy Medium Hard
SRM409 Easy Medium Hard
SRM410 Easy Medium Hard
SRM411 Easy Medium Hard
SRM412 Easy Medium
SRM413 Easy Medium Hard
SRM435 Easy Medium Hard
SRM436 Easy Medium Hard
SRM437 Easy Medium Hard
SRM439 Easy Medium Hard
SRM440 Easy Medium Hard
SRM501 Hard
SRM502 Hard
SRM503 Hard
SRM520 Hard
SRM521 Hard
SRM523 Hard
SRM524 Hard
SRM526 Hard
SRM526.5 Hard
SRM527 Hard
SRM528 Hard
SRM529 Hard
SRM531 Hard
SRM532 Hard
SRM533 Hard
SRM534 Hard
SRM536 Hard
SRM537 Hard
SRM544 Easy Medium
SRM549 Easy Medium
SRM550 Easy Medium Hard
SRM551 Easy Medium Hard
SRM551 Easy Medium Hard
SRM400 Easy Medium Hard
SRM401 Easy Medium Hard
SRM402 Easy Medium Hard
SRM403 Easy Medium Hard
SRM404 Easy Medium Hard
SRM405 Easy Medium Hard
SRM406 Easy Medium Hard
SRM407 Easy Medium Hard
SRM408 Easy Medium Hard
SRM409 Easy Medium Hard
SRM410 Easy Medium Hard
SRM411 Easy Medium Hard
SRM412 Easy Medium
SRM413 Easy Medium Hard
SRM435 Easy Medium Hard
SRM436 Easy Medium Hard
SRM437 Easy Medium Hard
SRM439 Easy Medium Hard
SRM440 Easy Medium Hard
SRM501 Hard
SRM502 Hard
SRM503 Hard
SRM520 Hard
SRM521 Hard
SRM523 Hard
SRM524 Hard
SRM526 Hard
SRM526.5 Hard
SRM527 Hard
SRM528 Hard
SRM529 Hard
SRM531 Hard
SRM532 Hard
SRM533 Hard
SRM534 Hard
SRM536 Hard
SRM537 Hard
SRM544 Easy Medium
SRM549 Easy Medium
SRM550 Easy Medium Hard
SRM551 Easy Medium Hard
SRM551 Easy Medium Hard
3/20/2012
3/19/2012
SRM523 Div1 Medium
500
メモ化する。
memo[h][w]=ベースの幅がwのブロックに高さhまでブロックを置くときのパターン数
ある幅を長さK以下のブロックで埋めようとしたとき、どれくらいのパターンがあるかを前もって計算しておく。
メモ化する。
memo[h][w]=ベースの幅がwのブロックに高さhまでブロックを置くときのパターン数
ある幅を長さK以下のブロックで埋めようとしたとき、どれくらいのパターンがあるかを前もって計算しておく。
ラベル: SRM
SRM524 Div1 Medium
500
与えられた条件を満たすような数列で、ある区間の和とある区間の和の間に不等式が成り立つ。
長さを2分探索しながら、その関係に矛盾がないかを調べる。
与えられた条件を満たすような数列で、ある区間の和とある区間の和の間に不等式が成り立つ。
長さを2分探索しながら、その関係に矛盾がないかを調べる。
ラベル: SRM
SRM524 Div1 Easy
250
与えられた範囲で、連続している素数は２と３だけということは想像がつく。
それ以外は、素数でなければ１回で済むし、素数であれば-1して素数でなくす。
与えられた範囲で、連続している素数は２と３だけということは想像がつく。
それ以外は、素数でなければ１回で済むし、素数であれば-1して素数でなくす。
ラベル: SRM
3/18/2012
tabbar.elのグループ化機能をせっかくだから使ってみる
ググッて調べてみても、グループ化しているブログの記事をあまり見ない。もちろん、自分でも使っていない。
でも、せっかくだから使ってみる。
デフォだとメジャーモードでタブをグループ化する様になっている。
私感ではこれが使いやすいとは思えないので、自分でグループ化する機能を描いてみる。
まだ使い込んだわけではないので、バグの１つもあると思うけど、そこはご愛嬌。
もう tabbar をいじるのに飽きてきた。
でも、せっかくだから使ってみる。
デフォだとメジャーモードでタブをグループ化する様になっている。
私感ではこれが使いやすいとは思えないので、自分でグループ化する機能を描いてみる。
まだ使い込んだわけではないので、バグの１つもあると思うけど、そこはご愛嬌。
もう tabbar をいじるのに飽きてきた。
ラベル: Emacs
3/11/2012
SRM491 Div1 Easy
250
向かい合った数の合計を決める。その合計を実現できる数字の組みの数を数える。そこから３つ選ぶ。
数字の組み３つから２種類のサイコロが作れるらしい。
こんな感じで出るだろ。 =>> お？全部1/2だ。 =>> ２種類作れるのか？とりあえず２倍しとけ。
みないな推測。場合によってはとても危険な方法だけど。
向かい合った数の合計を決める。その合計を実現できる数字の組みの数を数える。そこから３つ選ぶ。
数字の組み３つから２種類のサイコロが作れるらしい。
こんな感じで出るだろ。 =>> お？全部1/2だ。 =>> ２種類作れるのか？とりあえず２倍しとけ。
みないな推測。場合によってはとても危険な方法だけど。
ラベル: SRM
3/06/2012
tabbar.elのタブを閉じる。
現在のタブから右側もしくは左側のタブを全て閉じるelisp。
tabbar.elのタブが増えたとき、一部だけ閉じるのが面倒だった。
ほとんど閉じないバッファ(howmとかeshell)を一番左に寄せる習慣があるので、面倒が解消するかも？
動作確認は、これから使いながら済ませる。
tabbar.elのタブが増えたとき、一部だけ閉じるのが面倒だった。
ほとんど閉じないバッファ(howmとかeshell)を一番左に寄せる習慣があるので、面倒が解消するかも？
動作確認は、これから使いながら済ませる。
ラベル: Emacs
3/04/2012
SRM535 Div1 Easy
250
LCM / GCD を素因数分解する。
あとは、各素数の累乗をどちらの数字に割り当てるかを全通り試す。
最初の素数20個の積がgoogle先生曰く5.5794083 × 10^26らしい。
問題の制約上、これで充分間に合う。
本番では、オーバーフローのことを考えていなかった。ツラい。
LCM / GCD を素因数分解する。
あとは、各素数の累乗をどちらの数字に割り当てるかを全通り試す。
最初の素数20個の積がgoogle先生曰く5.5794083 × 10^26らしい。
問題の制約上、これで充分間に合う。
本番では、オーバーフローのことを考えていなかった。ツラい。
ラベル: SRM
2/29/2012
2/28/2012
2/26/2012
SRM532 Div2 Hard
950
メモ化する。
memo[何行目][n番目のマスの状態]
マスの状態は3進数表現で "自身が1で下に1が必要" or "自身が1で下に0が必要" or "自身が0"
メモ化する。
memo[何行目][n番目のマスの状態]
マスの状態は3進数表現で "自身が1で下に1が必要" or "自身が1で下に0が必要" or "自身が0"
ラベル: SRM
2/25/2012
2/24/2012
SRM534 Div1 Easy
250
メモ化する。
この程度の問題を本番で間違うとか人権がない。
自分は if ( !bool ) の代わりに if ( bool^1 ) とすることがある。
!を使えば if ( int ) でも同じ目的で使えるけど、^1 はそんなことない。
思わず、(bit & (1 << n)) ^ 1 なんてやってしまった。正しくは、(bit & (1 << n)) ^ (1 << n) もしくは !(bit & (1 << n))
華麗に間違ったから反省
メモ化する。
この程度の問題を本番で間違うとか人権がない。
自分は if ( !bool ) の代わりに if ( bool^1 ) とすることがある。
!を使えば if ( int ) でも同じ目的で使えるけど、^1 はそんなことない。
思わず、(bit & (1 << n)) ^ 1 なんてやってしまった。正しくは、(bit & (1 << n)) ^ (1 << n) もしくは !(bit & (1 << n))
華麗に間違ったから反省
ラベル: SRM
2/22/2012
AOJ0570
AOJ0570
memo[桁数][最後に使った数][ここまでの余り][増加or減少][与えられた数より小さくなったかどうか]
筆算をする。
[与えられた数より小さくなったかどうか]はつまり、ここまで作った数字のプレフィックスが一致しているかどうか。
D桁目まで一致しているのであれば、次の数字は与えられた数NのD+1桁目以下でなければならない。
この制約があることで、ある数N以下で条件を満たす個数が分かる。
既に一致していない場合は、D+1桁目より大きな数を選んでもよい。
(y - x + mod) % mod を忘れると答えが負になることがある。これで相当悩んだ。
memo[桁数][最後に使った数][ここまでの余り][増加or減少][与えられた数より小さくなったかどうか]
筆算をする。
[与えられた数より小さくなったかどうか]はつまり、ここまで作った数字のプレフィックスが一致しているかどうか。
D桁目まで一致しているのであれば、次の数字は与えられた数NのD+1桁目以下でなければならない。
この制約があることで、ある数N以下で条件を満たす個数が分かる。
既に一致していない場合は、D+1桁目より大きな数を選んでもよい。
(y - x + mod) % mod を忘れると答えが負になることがある。これで相当悩んだ。
ラベル: AOJ
2/21/2012
2/20/2012
2/19/2012
SRM533 Div1 Easy
250
順に取り除いていくのではなく、挿入していくことを考える。
そうすれば、挿入位置の左右にうまく分割して考えられる。
memo[左端][右端] = 間のどれかを挿入したときの最大値
取り除いていってもDPになりそうにないなー =>> あれ？何か皆やたら提出が早い =>> 貪欲か!?
結果、惨敗
順に取り除いていくのではなく、挿入していくことを考える。
そうすれば、挿入位置の左右にうまく分割して考えられる。
memo[左端][右端] = 間のどれかを挿入したときの最大値
取り除いていってもDPになりそうにないなー =>> あれ？何か皆やたら提出が早い =>> 貪欲か!?
結果、惨敗
ラベル: SRM
2/17/2012
SRM488 Div1 Easy
250
E(n, m) = p0 * E(n, m) + p1 * E(n + 1, m - 1) + p2 * E(n + 2, m - 2) みないになるから式を変形。
カッコを付け忘れた、+と*を間違えた、再帰はしてたけどメモ化してなかった。
散々だった。
E(n, m) = p0 * E(n, m) + p1 * E(n + 1, m - 1) + p2 * E(n + 2, m - 2) みないになるから式を変形。
カッコを付け忘れた、+と*を間違えた、再帰はしてたけどメモ化してなかった。
散々だった。
ラベル: SRM
2/15/2012
2/14/2012
SRM484 Div1 Easy
250
解法が思いつかないので、小さい数を試す。
0, 1, 2, 3 以外の数字をどこかの桁に含む数は対象にならないらしい。
とりあえず、4進数にして順に試す。
0〜3なのは2乗して桁上がりが発生するとまずいから?
解法が思いつかないので、小さい数を試す。
0, 1, 2, 3 以外の数字をどこかの桁に含む数は対象にならないらしい。
とりあえず、4進数にして順に試す。
0〜3なのは2乗して桁上がりが発生するとまずいから?
ラベル: SRM
2/12/2012
k7script.elでもぞもぞ動かす
killer7というゲームソフトがあります。過去にプレイした中でもかなり気に入ってる部類です。
難解なストーリーと変にお洒落な雰囲気が何ともいえません。
このゲームはセリフが英語なので画面下に字幕が出るんですが、少し変わっています。
1. 文字の位置が微妙に動く。
2. 背景に陰影ができる。
3. 特定の文字の形が変化する。
といった謎の挙動。
少しだけ真似てみましょう。emacsで。
難解なストーリーと変にお洒落な雰囲気が何ともいえません。
このゲームはセリフが英語なので画面下に字幕が出るんですが、少し変わっています。
1. 文字の位置が微妙に動く。
2. 背景に陰影ができる。
3. 特定の文字の形が変化する。
といった謎の挙動。
少しだけ真似てみましょう。emacsで。
ラベル: Emacs
2/10/2012
SRM532 Div1 Medium
450
とりあえずメモ化する。
memo[着目してる頂点][Kコ前までの頂点の状態][何コ前と辺を付けるか][残りの辺]
Kコ前の頂点たちは、次数が偶数か奇数がを覚えておけばいい。k <= 8 なので、ビットで持つ。
"K前の頂点のどれかと辺をいくつか付ける" or "次の頂点に進む"
とりあえずメモ化する。
memo[着目してる頂点][Kコ前までの頂点の状態][何コ前と辺を付けるか][残りの辺]
Kコ前の頂点たちは、次数が偶数か奇数がを覚えておけばいい。k <= 8 なので、ビットで持つ。
"K前の頂点のどれかと辺をいくつか付ける" or "次の頂点に進む"
ラベル: SRM
SRM532 Div1 Easy
300
３つ全てがアルファベットのモノは必ず使った方がよいのは明らか。
どれを端に付け加えるべきかを全部試す。
本番では、多くの人が落ちていた。自分も落とした。
３つ全てがアルファベットのモノは必ず使った方がよいのは明らか。
どれを端に付け加えるべきかを全部試す。
本番では、多くの人が落ちていた。自分も落とした。
ラベル: SRM
2/09/2012
2/08/2012
2/05/2012
SRM450 Div1 Easy
250
その場面で注目している山の石の個数が複数であれば、その山に最初に手を付けられるプレイヤーが "石を全て取る" or "1つだけ残す" の選択をすることで、次の山に手を付けるプレイヤーを決定できる。
つまり、全ての山の石が複数なら、先手必勝になる。
しかし、石の数が1つの場合はどうしてもプレイヤーがいれ変わる。
なので、最初に複数個の石からなる山に手を付けたプレイヤーの必勝。
山の石が1だけの場合は例外で、山の個数を見て判断する。
その場面で注目している山の石の個数が複数であれば、その山に最初に手を付けられるプレイヤーが "石を全て取る" or "1つだけ残す" の選択をすることで、次の山に手を付けるプレイヤーを決定できる。
つまり、全ての山の石が複数なら、先手必勝になる。
しかし、石の数が1つの場合はどうしてもプレイヤーがいれ変わる。
なので、最初に複数個の石からなる山に手を付けたプレイヤーの必勝。
山の石が1だけの場合は例外で、山の個数を見て判断する。
ラベル: SRM
2/04/2012
SRM475 Div1 Easy
300
全部試す。
シュミレーションで挑んで泣きたくなった。
でも、よく考えたらそうでもなかった。
うさぎがはみ出ることがない以上、偶数インデックスと奇数インデックスのそれぞれに1匹残るかどうかになる。
全部試す。
シュミレーションで挑んで泣きたくなった。
でも、よく考えたらそうでもなかった。
うさぎがはみ出ることがない以上、偶数インデックスと奇数インデックスのそれぞれに1匹残るかどうかになる。
ラベル: SRM
2/01/2012
SRM467 Div1 Medium
500
小さいケースを試すと、(n+k)C(k+1)に見える
上手く計算する知恵が咄嗟に浮かばなかった、とりあえず多倍長整数(自前)を利用。
使わない解も後でやっておこう。
小さいケースを試すと、(n+k)C(k+1)に見える
上手く計算する知恵が咄嗟に浮かばなかった、とりあえず多倍長整数(自前)を利用。
使わない解も後でやっておこう。
ラベル: SRM
1/31/2012
SRM468 Div1 Medium
500
DP[街][フライトの回数][最後に利用した交通手段]
移動のパターンは、road -> road, flight -> flight, road -> flight, flight -> road の 4 つ
[街]をNまで確保すると死ぬ。手元だと確保できるから気付かずにサブミットしてしまった。
直前のだけ覚えておけば答えは出せる。
DP[街][フライトの回数][最後に利用した交通手段]
移動のパターンは、road -> road, flight -> flight, road -> flight, flight -> road の 4 つ
[街]をNまで確保すると死ぬ。手元だと確保できるから気付かずにサブミットしてしまった。
直前のだけ覚えておけば答えは出せる。
ラベル: SRM
1/29/2012
SRM471 Div1 Medium
500
最短経路。
足して13で割れるかどうかさえ記憶しておけば充分なので、ビットに押し込んで覚えておく。
(辺の重み%13)だけ左シフトし、(辺の重み%13)をORていけば記憶できる。
はみ出た分は下位ビットへ循環。
最短経路。
足して13で割れるかどうかさえ記憶しておけば充分なので、ビットに押し込んで覚えておく。
(辺の重み%13)だけ左シフトし、(辺の重み%13)をORていけば記憶できる。
はみ出た分は下位ビットへ循環。
ラベル: SRM
1/27/2012
1/03/2012
登録:
投稿
(
Atom
)