解いた問題

12/18/2012

続・tabbar.elのグループ化機能をせっかくだから使ってみる

当方、elscreenではなくtabbarを使っている少数派です。
以前、tabbar.elのグループ化機能をせっかくだから使ってみるなんて投稿をしました。
しばらく封印していたのですが、修正を加えた上で最近また使っています。バッファの数が増えた時に便利です。
溜まった設定の一部を切り出してgistに投げて見ました。名付けてtabbar+.el。

しかし、以前のコードは見るに耐えない。そしてdash.elが便利。

12/13/2012

SRM563 Div1 Medium

500

DP[どこまで見たか][何枚めくったか] = 最適値
そこまで難しくは無い割に面白い問題でした。

11/23/2012

SRM561 Div1 Medium

550

grundy数を計算する。
木構造にして、赤い点を打った頂点より上を全て削除する。
残った木でも排他的論理和。

11/21/2012

SRM561 Div1 Easy

250

maxAccepted の大きさが15しかないので、2^n通り試して貪欲に割り当てていく。

11/15/2012

SRM527 Div1 Medium

450

辞書順最小は先頭から決める。
1つ以上の答えがあるそうなので、順に0を割り当てて試す。
ある場所に0を割り当ててマトリックスを作れないのならば、そこに1を入れればいい。
マトリックスになるかどうかは、2部マッチングをすればよい。

SRM527 Div1 Easy

275

dp[グラフの頂点数][葉の数]
解いたの忘れて2度目の挑戦。

11/11/2012

LiveArchive4035

4035 - Undetectable Tour

どういう場合に到達不可能になるのかを考える。

センサーのカバーしている領域だけを通って
"領域の上から領域の下まで移動できる"
"領域の上から領域の右まで移動できる"
"領域の左から領域の下まで移動できる"
"領域の左から領域の右まで移動できる"
の4つの条件のうち1つでも満たせば到達不可能になる。

全てのセンサーの位置と各センサー(x, y)から最短で行ける領域の端(x, 0), (0, y), (x, N-1), (N-1, y)の位置を頂点とする様なグラフを作る。
(始点と終点の扱いには注意すること。領域の端を全て頂点にしてしまうとTLEする。)
このグラフ上で4つの条件のどれかを満たす様なパスの最大の辺の重みの最小値がセンサーに捕捉されずに到達可能な距離の上限になる。

やりかたは色々あるだろうけど、条件を満たすまで辺の重み順にUnionFindした。

SRM560 Div1 Easy

250

貪欲。

SRM495 Div1 Easy

275

memo[どこまで見た][最後に使った数] = 最後まで作りきれるかどうか
バックトラックしていたら終わらないので、到達可能かどうかをメモ化する。
到達可能と判断できた瞬間にそれまでのパスをなぞる。

10/04/2012

SRM430 Div1 Medium

500

最大の次数が3なので、ある頂点に関して状態を2ビットで表せる。
DP[4^20]

SRM430 Div1 Easy

250

xの2進数表現で0のビットを下位から埋めていく。

9/29/2012

LiveArchive5848

分割統治。

領域を縦と横に2分割して、4つの領域に分ける。
縦は2種類の点を分ける様なX軸に垂直な直線で分割し、横はそれっぽい直線で分割する。

横方向に隣合う領域同士の近い点か、斜めの領域同士の点から最近点を探す。
互いに斜めな領域同士の点の移動は、分割に使った縦と横の線の交点を通る様な移動を考える。

あとは、点の数が少なくなるまで横の分割を繰り返す。

9/13/2012

SRM555 Div2 Hard

955

DP1[ n ] = n マス連続して泥でないときの行き方が偶数通りか奇数通りか。
DP2[どこまで見た][泥のマスがいくつか][ 偶数通りの行き方がこれまであったか ]

o を乾いたマス、x を泥のマスとした場合、oooxoooo の行き方は"3マス連続して泥でない道の行き方"×"4マス連続して泥でない道の行き方"になる。
つまり、泥のマスで区切ったそれぞれの連続して泥でない道の行き方の中に偶数通りの行き方のある部分があれば、
全体も偶数通りの行き方が存在することになる(偶x偶=偶、偶x奇=偶、奇x奇=奇)。


前計算で n マス連続して泥でない場合の行き方を計算しておく。
その後、ある2つの泥のマスの間にいくつの乾いたマスを挿入するかというDPを行う。
両端に泥のマスを付け加えるとやりやすかった。

SRM555 Div2 Medium

555

DP[何桁目まで]

SRM555 Div2 Easy

255

やるだけ。

8/23/2012

8/09/2012

SRM437 Div2 Hard

1000

メモ化する。
n の m 乗根を探していけばいい。

解法はすぐに思いつくけど、通すのは難しい気がする。
本番通した人はエスパーに違いない。

SRM437 Div2 Medium

500

メモ化する。
貪欲だと思って撃沈した。

SRM437 Div2 Easy

250

やるだけ。

7/12/2012

Codeforces Round #129 (Div. 2)

ABCDを解いた。

A: やるだけ
B: どういう数列に変化させるのが最適かは簡単に分かる。1ステップでは出来る限り範囲をインクリメントするべき。
C: dp[ n桁目 ][ 最後に使った数字 ][ 小さくなったか ][ 最初の非 0 の数字 ]
D: やるだけ

以下、本番で投げたコード

6/26/2012

SRM547 Div1 Medium

500

式を出して計算するだけ。ちょっとした枝刈りをしないとタイムアウト?

サブテーブルのサイズが横 i 縦 j で、左上が x のとき、そのテーブルの数字の合計は
i * j * ( 2 * x + ( j - 1 ) + width * ( i - 1 ) ) = 2 * S

SRM547 Div1 Easy

250

x と y の差のそれぞれが何パターン出現するかを計算して答えを出す。

6/21/2012

AOJ2403

AOJ2403

2012模擬国内予選E問題

単純な枝刈りで充分
軍事力順でソートして、残りを全て取って現状の最大値を超えられるか見る


以下、本番で提出したコード

UVa11206

UVa11206

普通に塗って試せばいい。

グラフは連結だし、頂点の数も充分に小さいっぽい。

6/19/2012

UVa11229

UVa11229

盤面の状態は 3^9 = 19683 程度。メモ化する。
引き分けの場合は後手番の勝利に含めてしまっていい。

memo[ 盤面の状態 ] = 先手の勝率
先手は勝率を最大化し、後手は勝率を最小化する。

6/18/2012

SRM546 Div1 Medium

500

m 桁目を n より大きくして残りは0で埋める。下の桁で digit1, digit2 の帳尻を合わせる。

6/17/2012

SRM546 Div1 Easy

250

本番では解けなかった。

2進数表現にすると分かりやすい。
奇数なら n-1, 偶数なら n/2 という列に登場するという事は、
最上位が K で始まるということ。

なぜ気が付かなかった・・・。

6/13/2012

UVa548

UVa548

ポストオーダーの最後に登場する頂点でインオーダーを分割する。
このコードより簡単な実装or解法がある気がする。

UVa10128

UVa10128

dp [ 誰を使った ] [ これまでで最も高い身長 ] [ 前から見て何人見えるか ]

最も身長の高い人より後ろに並んでいる人は当然見えない。
つまり、その人の前と後ろで分けて考えることが出来る。

6/12/2012

UVa 12410

UVa12410

memo [ 何桁目まで作ったか ] [ 使った 1 の数 ] [ idealとの違い ] [ mod 3 ] [ mod 7 ] [ smaller or not ]

6/11/2012

SRM545 Div1 Medium

500

ある点を最後にシグナルを発信する位置にする。
その点から原点までの間に整数座標の点がいくつあるかを、GCDで求める。
その中から K - 1 コの点を選ぶ組み合わせだけ、選び方が存在する。

原点のから以外にも同様な線分を引くことができるので、その分を掛け算する。

K == 1 の時だけ別処理。


6/08/2012

SRM545 Div1 Easy

275

先頭から1文字ずつ作る。

ある文字を次に付け足す場合、
(これまでに作った文字列) + (次に付け足す文字) + (残りを降順に並べた文字列)
で出来る文字列がこれ以降で inv の数を最大にでできて、辞書順で最も大きい。

あとは、minInv と minStr の条件を満たせる範囲で最も辞書順で小さい文字を順に付け加えていくだけでいい。


6/01/2012

SRM410 Div2 Hard

1000

memo [ テキストの i 文字目まで作った ][ 正規表現の j 文字目まで使った ] = pair( cost, string )
文字列の辞書順最小パスな問題は逆からやるのが吉だった気がする。

SRM410 Div2 Medium

500

グリッドと連結でない頂点は、最も大きい連結成分との間に辺を作る。

SRM410 Div2 Easy

250

やるだけ

5/21/2012

SRM404 Div2 Hard

1000

同じ高さで到達可能なモノを1つにまとめる。
まとめると、よくあるDPになる。

SRM404 Div2 Medium

500

やるだけ。

SRM404 Div2 Easy

250

やるだけ。問題を理解するまで時間がかかった。

SRM403 Div2 Hard

1000

DPするだけ。

SRM403 Div2 Medium

500

やるだけ

SRM403 Div2 Easy

250

やるだけ

SRM402 Div2 Hand

1000

数字は多くても 8 個しかないので、とりあえずメモしながら全部試す。
+1.0 する必要があることに全然気がつかなかった。


SRM402 Div2 Medium

500

やるだけ

SRM402 Div2 Easy

250

やるだけ

5/20/2012

SRM401 Div2 Hard

1000

お手上げ。解説を読む。

KMP の接頭語関数の最後の要素と文字長の差を見るらしい
接頭辞関数って、最長の接頭辞の長さだよね・・・。


スパソから KMP を拝借してサブミット

SRM401 Div2 Medium

500

図がいまいち理解できなかった。


SRM401 Div2 Easy

250

GCDで解けるらしい。

SRM400 Div2 Hard

1000

上1行と左1列を全通り試す。
個人的にはMidより簡単な気がする。

SRM400 Div2 Medium

500

pow 関数で計算すると誤差で死ぬ。

これを1発で通せる人は凄いと思う。

SRM400 Div2 Easy

250

やるだけ

SRM543 Div1 Easy

250

mod 4 とかいうスマートな解法があるらしい。

unsigned int ならループを回しても間に合うとか間に合わないとか。

5/15/2012

SRM501 Div1 Easy

250

DPして最大値を最小値を探す。
dp[足した回数][掛けた回数]

SRM502 Div1 Easy

250

サフィックスになってるものを削除すればいい。

SRM503 Div1 Easy

250

答えは2, 1, -1の3つしかない。
最後のサンプルを見ると何となく察しがつく。

あとはそれぞれの最小値と最大値を見てそれっぽい解を返せばいい。

SRM504.5 Div1 Easy

250

下1桁だけに注目すればいい。
与えられた数と同じ下1桁を持つ数を4と7から作る。

SRM504 Div1 Easy

250

やるだけ。

AOJ1251

AOJ1231

やるだけ。気合。

5/14/2012

SRM505 Div1 Easy

300

こういう感じの問題って凄く苦戦するんだけど、何かコツとかないのかな。

AOJ1263

AOJ1263

入力として与えられる隣接行列の対角成分以外は2以上なので、必ずスイッチを経由する。
まず頂点のどれかから辺を伸ばして、スイッチを1つ設置して木のルートと見る。
そうすると、ある頂点からある頂点へ移動するときにそのルートを経由する必要があるかどうかが判定できる。
経由しなくても行ける頂点同士には、ルートから新たに辺を伸ばしてスイッチを設置して同様の処理を繰り返す。

5/13/2012

TCO2012 2B

参加記録

華麗に0完

300:
0〜N-1と1〜Nを間違えた。

550:
開いてない

900:
開いてない

5/11/2012

AOJ2033

AOJ2033

まず強連結成分分解する。
その後、連結成分を圧縮した森でルートとなっている頂点を探す。
その頂点に含まれる本来の頂点のどれかをそれ単体で作成する。

強連結成分分解のコードを描いたのがだいぶ昔なので、描き直したい衝動に駈られている。

5/09/2012

SRM542 Div1 Easy

250

まず、Tを決める。
高さ H 幅 W の四角形を考える。端から端まで使うような経路では T = 2 * (H + W)
中継地点の座標の選び方は (H - 1) * (W - 1) 通り。
その四角形の中から3点を選ぶパターンは、X座標Y座標を3つずつ選んで、
それを組み合わせてできる座標の数。つまり、3!
ex.) X = {0, a, W}, Y = {0, b, H} から作れる座標を組みは3!通り。

それを掛けて足しあわせていけばいい。

分かりやすく説明できないー。

5/07/2012

SRM506 Div1 Easy

250

やるだけ。

SRM507 Div1 Easy

250

やるだけ。

SRM509 Div1 Easy

250

9で割った余りなのが重要。10^nをかけたとしても、あまりに変化がない。
そして、各数字は 2^(文字列の長さ) 回だけ登場する。

小さいケースを手で試していたら気がついた。
簡単だとも思わないけど、Editorials を見る限りでは正答率が低いわけではない。
こういう類を苦手に思わない人たちってのはどういう過程を経て答えに行き着くのか・・・。

SRM510 Div1 Easy

250

全通り試して間に合う。

SRM511 Div1 Easy

250

条件に合うように2つのグループに分ける。
あとは、割り当て方が何通りあるかを計算する。

4/26/2012

SRM512 Div1 Easy

256

何日目まで店に通うかを決め打ちする。

SRM513 Div1 Easy

250

全部試す。

SRM514 Div1 Easy

250

n が奇数の場合は(X + Y)が奇数の場所にしか行けない。
n が偶数の場合はどこへでも行ける。

サンプルの最初2個では、nが2と3。
BFSで行ける場所を出力してみたら気がついた。

近い位置だけBFSで調べた後に(X, Y)から(0, 0)へ山を登ると
X, Yの値の範囲が大きすぎてうまくいかない。

SRM515 Div1 Easy

250

順番に試す。

SRM516 Div1 Easy

250

問題を理解できれば解ける。

4/25/2012

SRM517 Div1 Easy

250

T == N
Tが素数で、Nがその素数で割れる。
TとNが同じ素数の累乗で、Tが2乗以下

以上の3パターンしか Yes の場合はないはず。

SRM518 Div1 Easy

250

辞書順最大の1文字を順に拾っていく。

SRM519 Div1 Easy

250

ビット列で一致しているプレフィックスの部分はいじる必要はなさそう。

4/24/2012

SRM538 Div1 Medium

450

何度も曲がるのは最適でない。
最初に前進を全て使った後、いくらか曲がって後進を使う。

余弦定理が出てこなくて少し焦った。

SRM538 Div1 Easy

250

SRM480 Div1 Medium

450

あるクライアントとあるサーバを直に結ぶケーブルにゲートを設置するかどうかは、
トポロジカル順序でそのクライアントとサーバの間にあるコンピュータのかに、
そのクライアントから到達可能で、そのサーバへ到達可能なコンピュータが1つでもあるかどうかによる。

UVa1172

UVa1172

DPかメモ化する。
memo[片方の岸の街][他方の岸の街]

たぶん同じ名前を持つ街が存在する。
街の名前を map のキーにするようなことは避けたほうがいい。

SRM541 Div1 Easy

250

0.5に注意する。

4/22/2012

TCO2012 2A

参加記録。何も出来なかった。

300 :
2部マッチングして正当性を確かめるまでは思い浮かんだけど
log2 で分類しきれるという所に最後まで気がつかなかった。
もっとシンプルな方法で解いてる人がいるけど、あれは何をやっているのか・・・。

450 :
読んだだけ。

1000 :
開いてない。

4/20/2012

UVa1228

UVa1228

メモ化する。
memo[ 使った 0 の数 ][ 使った 1 の数 ]

0 と 1 はそれぞれ先頭から使う。つまり、入れ替わりが発生するのは同じ数同士ではない。
与えられた遅延の値を見ていけば答えは出せる。

4/18/2012

4/16/2012

AOJ2391

AOJ2391
JAGの春コンテストのC問題

両側からBFSする。
答えが45を超えるような入力は存在しないという制約があるので、
22ステップだけ両側から探索する。

とはいっても、N<=4のときはただのBFSで事足りる。

この実装だど、メモリがぎりぎり。
キューに入れる前に終了や打ち切りの条件を確かめる必要がある。キューから取り出したモノでやるとMELする。
どちらかでも23ステップやるとMLEする。


4/12/2012

AOJ1163

AOJ1163

解くのは初めてではないんだけど、何となくフローを描いてみたくなったのでやってみた。

UVa1215

UVa1215

文字列の 0 番目から i 番目までに各文字がどれくらいあるかを前もって数えておく。

UVa1235

UVa1235
MSTを求めるだけ。

SRM540 Div1 Easy

250

1次式にして値の範囲を決める。
数式だけ見ると簡単なんだけど、Div1が阿鼻叫喚になるような問題だった。

4/11/2012

SRM531 Div1 Medium

500
行列累乗で挑んだけど、どうにも通らない。
行列やシミュレーションのようなアプローチだと mod が悪さをするらしく、複数の mod で試す必要があるらしい。
素直にグラフにしてやった。

path[ 0 ][ i ] == true
path[ i ][ i ] == true
out_degree[ i ] > 1
を満たす頂点が存在したら無限に増える。

4/10/2012

SRM533 Div1 Medium

500
行と列を頂点にすると、オイラーパスの問題になる。
連結かどうか調べる必要があるのを最後まで忘れていた。

4/09/2012

SRM527 Div1 Easy

275
メモ化する。
memo[まだ使ってない頂点][片側だけ使っている辺][どちらも空いている辺]

SRM526 Div1 Easy

250
集める場所を決めて、端から順に移動させる。

4/08/2012

TCO2012 1B

参加記録。通過したけど、残念な結果。

250 :
やるだけ。やるだけにも関わらずFailedSystemTest。

500 :
メモ化した。memo[区間の先端][区間の終端][今何匹か]
貪欲とか2分探索みたいな解法の人もいた。

1000 :
読んでない。


4/06/2012

4/05/2012

UVa1238

UVa1238

DPする。
dp[どこまで見た][閉じていない開き括弧の数][これまでの和]
+ に括弧を付けても意味がないので、- のところに括弧を付ける。
- ( ... - ( ... - ( ) ... ) ... - ( ) ... ) みたいになるとして、
閉じられていない括弧の数が偶数か奇数かどうかで、今見ている数の符号が反転するかどうか分かる。

4/02/2012

SRM492 Div1 Easy

250
2つの木を切らずに使う様な場合を考える。何故それで正しいかはよく分からない。勘。
計算の順序によっては精度がアレ。サンプルが親切なので、気付かないってことはない。

UVa1255

UVa1255
ある時間からある時間までにどれくらいスタックに入れられるかメモ化orDP
memo[begin][end] = max{ 1 + memo[A][B] + memo[B][end] }

4/01/2012

UVa1247

UVa1247
ワーシャルフロイドする。

TCO2012 1A

参加記録。惨敗

250 :
全部試す。
ソートを忘れて再提出。

500 :
AとBが等しくなる場合はたぶん無い。素数を分母か分子に振り分けるパターン数 / 2。
__builtin_popcountにlong long int を使ってシステムテストで落ちる。

1000 :
ざっと読んだだけ。

3/28/2012

UVa1263

UVa1263
グラフにする。
強連結成分分解して、頂点の入次数を見る。
強連結成分分解のコードは省略。だいたいスパソと同じ。

3/25/2012

ClojureでLispインタプリタ

思いつきでやってみた。意外と面白かった。
ちゃんと動くかは自信がない。
関数を定義するときに [ ] を使わないといけないのは気にしない。

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秒。
ラディックスソートとか使えばもっと早くなるかも?

3/23/2012

SRM537 Div2 Hard

925
とりあえず、グラフにする。
あるトーストを学ぶために食べるトーストの枚数は最小で1、最大でルートまでの距離
全ての頂点に関して試す。

点数も1000より低いし、本番でも40人以上が通してるけど、そんなに簡単とは思えなかった。

SRM503 Div2 Hard

900
MST

SRM502 Div2 Hard

1000
DPする。
DP[何匹目まで見た mod 2][数字の合計 mod N][何匹が逃げた];

この実装だと、実行時間がそうとうギリギリ。
テーブルの半分を毎回初期化するのはもちろん、剰余算を少し余計にやっただけでアウト。

3/22/2012

SRM501 Div2 Hard

1000
メモ化する。
memo[長さ][これまでの合計][最後に使った数][何連続で減少しているか];

SRM536 Div2 Hard

1000
ソートしてDPする。意外と時間がかかった。

SRM520 Div2 Hard

1000
メモ化する。直前の1行を覚えておけばいい。

3/21/2012

SRM526 Div2 Hard

1000
メモ化する。
memo[桁数][4の数][7の数][まだ一致しているか]

SRM534 Div2 Hard

1000
lg 10000 が充分小さいことに着目して、メモ化する。
メモを long long int で持つとメモリで落ちた。

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

3/19/2012

SRM523 Div1 Medium

500
メモ化する。
memo[h][w]=ベースの幅がwのブロックに高さhまでブロックを置くときのパターン数
ある幅を長さK以下のブロックで埋めようとしたとき、どれくらいのパターンがあるかを前もって計算しておく。

SRM523 Div1 Easy

250
やるだけ。

SRM524 Div1 Medium

500
与えられた条件を満たすような数列で、ある区間の和とある区間の和の間に不等式が成り立つ。
長さを2分探索しながら、その関係に矛盾がないかを調べる。

SRM524 Div1 Easy

250
与えられた範囲で、連続している素数は2と3だけということは想像がつく。
それ以外は、素数でなければ1回で済むし、素数であれば-1して素数でなくす。

3/18/2012

SRM537 Div1 Medium

500
DP[K日][部屋N][Bビット] = K日が経過した部屋NのBビット目が1になっている確率。

tabbar.elのグループ化機能をせっかくだから使ってみる

ググッて調べてみても、グループ化しているブログの記事をあまり見ない。もちろん、自分でも使っていない。
でも、せっかくだから使ってみる。

デフォだとメジャーモードでタブをグループ化する様になっている。
私感ではこれが使いやすいとは思えないので、自分でグループ化する機能を描いてみる。
まだ使い込んだわけではないので、バグの1つもあると思うけど、そこはご愛嬌。

もう tabbar をいじるのに飽きてきた。

SRM537 Div1 Easy

275
XとYに何かを掛けてAとBが作れるかを試す。Xだけでどちらも作れるのなら、Yの候補は無限個。

3/11/2012

SRM491 Div1 Easy

250
向かい合った数の合計を決める。その合計を実現できる数字の組みの数を数える。そこから3つ選ぶ。
数字の組み3つから2種類のサイコロが作れるらしい。

こんな感じで出るだろ。 =>> お?全部1/2だ。 =>> 2種類作れるのか?とりあえず2倍しとけ。
みないな推測。場合によってはとても危険な方法だけど。

SRM490 Div1 Easy

250
これが一瞬で浮かぶ数学力を持ち合わせていない。頑張って紙に書いて計算した。

SRM536 Div1 Easy

250
ソートして頭から2つずつマージしていけば良いらしい。

3/06/2012

tabbar.elのタブを閉じる。

現在のタブから右側もしくは左側のタブを全て閉じるelisp。
tabbar.elのタブが増えたとき、一部だけ閉じるのが面倒だった。
ほとんど閉じないバッファ(howmとかeshell)を一番左に寄せる習慣があるので、面倒が解消するかも?

動作確認は、これから使いながら済ませる。

3/04/2012

SRM535 Div1 Easy

250
LCM / GCD を素因数分解する。
あとは、各素数の累乗をどちらの数字に割り当てるかを全通り試す。
最初の素数20個の積がgoogle先生曰く5.5794083 × 10^26らしい。
問題の制約上、これで充分間に合う。

本番では、オーバーフローのことを考えていなかった。ツラい。

2/29/2012

SRM521 Div2 Hard

1000
それっぽい位置を正方形の角と決めて、各点が含まれるか調べる。
文字列で記憶するのが少し不安だったけど、問題なかった。

SRM523 Div2 Hard

1000
頑張ってメモ化する。

SRM524 Div2 Hard

1000
少し前に解いた問題と似た雰囲気があるからどうにかなった。
[最後に使った数字][これまでの余り]を状態にしたBFSで計算できる。筆算を思い浮かべる。
こういう問題は面白いと感じる。

2/26/2012

SRM529 Div2 Hard

1000
ここを見る

SRM532 Div2 Hard

950
メモ化する。
memo[何行目][n番目のマスの状態]
マスの状態は3進数表現で "自身が1で下に1が必要" or "自身が1で下に0が必要" or "自身が0"

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))
華麗に間違ったから反省

2/22/2012

AOJ0570

AOJ0570
memo[桁数][最後に使った数][ここまでの余り][増加or減少][与えられた数より小さくなったかどうか]
筆算をする。
[与えられた数より小さくなったかどうか]はつまり、ここまで作った数字のプレフィックスが一致しているかどうか。
D桁目まで一致しているのであれば、次の数字は与えられた数NのD+1桁目以下でなければならない。
この制約があることで、ある数N以下で条件を満たす個数が分かる。
既に一致していない場合は、D+1桁目より大きな数を選んでもよい。

 (y - x + mod) % mod を忘れると答えが負になることがある。これで相当悩んだ。

UVa11391

UVa11391
メモ化する。
memo[BIT]で挑むとTLE喰らう。memo[C][R][BIT]にしよう。
テストデータが意地悪すぎる。何か面倒だった。

2/19/2012

SRM489 Div1 Easy

300
結合法則を調べる。

SRM533 Div1 Easy

250
順に取り除いていくのではなく、挿入していくことを考える。
そうすれば、挿入位置の左右にうまく分割して考えられる。
memo[左端][右端] = 間のどれかを挿入したときの最大値

取り除いていってもDPになりそうにないなー =>> あれ?何か皆やたら提出が早い =>> 貪欲か!?
結果、惨敗

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) みないになるから式を変形。

カッコを付け忘れた、+と*を間違えた、再帰はしてたけどメモ化してなかった。
散々だった。

2/14/2012

SRM486 Div1 Easy

300
+と*しか使う必要がない。
1とsからBFS

mapを避けて配列を使う癖があることを発見した。UVaならそれで良かったんだけど・・・。

SRM485 Div1 Easy

250
最初の2つを決め打ちする。

SRM484 Div1 Easy

250
解法が思いつかないので、小さい数を試す。
0, 1, 2, 3 以外の数字をどこかの桁に含む数は対象にならないらしい。
とりあえず、4進数にして順に試す。
0〜3なのは2乗して桁上がりが発生するとまずいから?

2/12/2012

k7script.elでもぞもぞ動かす

killer7というゲームソフトがあります。過去にプレイした中でもかなり気に入ってる部類です。
難解なストーリーと変にお洒落な雰囲気が何ともいえません。
このゲームはセリフが英語なので画面下に字幕が出るんですが、少し変わっています。
1. 文字の位置が微妙に動く。
2. 背景に陰影ができる。
3. 特定の文字の形が変化する。
といった謎の挙動。

少しだけ真似てみましょう。emacsで。

2/10/2012

SRM532 Div1 Medium

450
とりあえずメモ化する。
memo[着目してる頂点][Kコ前までの頂点の状態][何コ前と辺を付けるか][残りの辺]
Kコ前の頂点たちは、次数が偶数か奇数がを覚えておけばいい。k <= 8 なので、ビットで持つ。
"K前の頂点のどれかと辺をいくつか付ける" or "次の頂点に進む"

SRM532 Div1 Easy

300
3つ全てがアルファベットのモノは必ず使った方がよいのは明らか。
どれを端に付け加えるべきかを全部試す。
本番では、多くの人が落ちていた。自分も落とした。

2/08/2012

SRM481 Div1 Easy

250
嘘を吐かれた上で嘘を吐いている人数を決めて確認していく。

2/05/2012

SRM480 Div1 Easy

250
何も考えずに実装する。やるだけ。

SRM450 Div1 Easy

250
その場面で注目している山の石の個数が複数であれば、その山に最初に手を付けられるプレイヤーが "石を全て取る" or "1つだけ残す" の選択をすることで、次の山に手を付けるプレイヤーを決定できる。
つまり、全ての山の石が複数なら、先手必勝になる。
しかし、石の数が1つの場合はどうしてもプレイヤーがいれ変わる。
なので、最初に複数個の石からなる山に手を付けたプレイヤーの必勝。
山の石が1だけの場合は例外で、山の個数を見て判断する。

SRM451 Div1 Easy

250
11...11 * A = X
みたいな式になる。順に試す。

SRM452 Div1 Easy

250
試しに石を置いて数える。計算もで出せるみたい。
小さい場合を手で描いてみると分かりやすい。

SRM453 Div1 Easy

250
全部試す。

2/04/2012

SRM479 Div1 Easy

250
後ろから配るだけ。vector<int>だとかint配列を使うと死ぬ。

SRM478 Div1 Easy

250
ただのBFS

SRM477 Div1 Easy

250
描くだけ。

SRM476 Div1 Easy

250
全部試す。

SRM475 Div1 Easy

300
全部試す。

シュミレーションで挑んで泣きたくなった。
でも、よく考えたらそうでもなかった。
うさぎがはみ出ることがない以上、偶数インデックスと奇数インデックスのそれぞれに1匹残るかどうかになる。

SRM474 Div1 Easy

250
愚直に試す。Nの大きさに比べて、Cの長さが少ないことに気付ければ簡単。

SRM473 Div1 Easy

250
充分な回数繰り返す。

2/01/2012

SRM467 Div1 Medium

500
小さいケースを試すと、(n+k)C(k+1)に見える
上手く計算する知恵が咄嗟に浮かばなかった、とりあえず多倍長整数(自前)を利用。
使わない解も後でやっておこう。

SRM531 Div1 Easy

300
DPする。
DP[どこまで使ったたか][どこまで作ったか]
今まで使った曲をまた使う or 新たな曲を使う

1/31/2012

SRM468 Div1 Medium

500
DP[街][フライトの回数][最後に利用した交通手段]
移動のパターンは、road -> road, flight -> flight, road -> flight, flight -> road の 4 つ
[街]をNまで確保すると死ぬ。手元だと確保できるから気付かずにサブミットしてしまった。
直前のだけ覚えておけば答えは出せる。

1/29/2012

SRM471 Div1 Medium

500
最短経路。
足して13で割れるかどうかさえ記憶しておけば充分なので、ビットに押し込んで覚えておく。
(辺の重み%13)だけ左シフトし、(辺の重み%13)をORていけば記憶できる。
はみ出た分は下位ビットへ循環。

SRM469 Div1 Medium

500
メモ化して復元

1/27/2012

tabbarのタブを左右に移動させる

tabbar.elのカレントタブを移動させる。

ググったら既に誰かがやっていたみたい。
しかし、自分でもやる。
動作確認はなおざり。

1/03/2012

EmacsからAOJにサブミットする

Emacs Lisp 初挑戦。
Emacs から Aizu Online Judge (AOJ) にサブミットする Emacs Lispを描いてみた。