解いた問題

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 新たな曲を使う