解いた問題

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 :
ざっと読んだだけ。