1000
それっぽい位置を正方形の角と決めて、各点が含まれるか調べる。
文字列で記憶するのが少し不安だったけど、問題なかった。
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
登録:
投稿
(
Atom
)