AtCoder Beginner Contest 129参加メモ

Q.進捗どうですか？
A.友軍待ちです…

E5-2ラストの状態ですが。1出撃2000以上減っていくのやばい。掘りも0だしまずい…。友軍くるまで消費の少ない石垣掘り。

結果

A,B,C,DはAC。Eは後日自力AC。Fは解説見てもわけわかんない。

C - Typical Stairs

とりあえず壊れた床はないとして図を描いてみると方向性が決まりました。

段目には段目と段目からほいっと移動することができますので。

壊れてる床があるとすると、

段目は使えないので。壊れた床が2段続くと移動できないので0．

提出時は条件何個も書いたけど、床が壊れてるとこはとするだけでいいですね。

余談

DPだ！！DPだろう！？なあDPだろうおまえ
首おいてけ
なあ！！

段数1の時を考えてなかったためREいただきました。

D - Lamp

1マスごとに上下左右捜査して照らせるマスを考えてたらとても間に合いません。どうにか計算量減らせないかなーととりあえず図を描いたり縦横別々に考えてみると、障害物間では照らせるマスは同じだからこれを利用する方針に決めました。

上図のように縦横それぞれで照らせるマスのマップを作って足し合わせれば楽。障害物の位置を記録しておけば照らせるマスはで計算できるため、障害物の数とマップへの書き込み数を考えればよくてまあでいけるなということでいけました。

余談

初4完！うれしいうれしい。うれしくて3秒くらい踊りました。座った状態で。不思議な踊りにMPを吸われたため5完はならず。踊ってさえいなければ…！

E - Sum Equals Xor

bitごとに考えます。

a,bの組は(0,0)、(0,1)、(1,0)、(1,1)の4つありますが、(1,1)なら桁上がりでの条件を満たさず死亡なので(1,1)を除いた3通りとなります。

についてですが、

1. 
2. <

で場合を分けて考えます。

1.の場合

Lが1なら(0,0)、(0,1)、(1,0)の3通りとなります。(0,0)を使うと<になることに注意。
Lが0なら(0,0)のみとなります。

2.の場合

1でも0でも(0,0)、(0,1)、(1,0)の3通り使えます。

まとめると、上位桁から順に見ていって

if(L[i]=='1')
{
    dp[i + 1, 1] = dp[i, 1] * 2;    //(0,1),(1,0)
    dp[i + 1, 0] = dp[i, 1];        //(0,0)
    dp[i + 1, 0] += dp[i, 0] * 3;   //(0,0),(0,1),(1,0)
}
else
{
    dp[i + 1, 1] = dp[i, 1];        //(0,0)
    dp[i + 1, 0] = dp[i, 0] * 3;    //(0,0),(0,1),(1,0)
}

みたいな感じになります。
※dp[i,0]は2.の場合、dp[i,1]は1.の場合

余談

寝て起きたらあっさり方針が決まりました。寝てる時の私は起きてる時の私より優秀なようです。起きてる時も出て来い寝てる時の私。起きてる時の私は寝てていいよ。

1000までの値で1が出てくる数を求めよとかいう問題に似てると思った。

所感

初4完だやったぜこれ緑色すっとばして水色になるんじゃね？ と思ったら茶色のままだった。現実は厳しい。

安定して4完が今後の目標。そろそろ螺旋本や蟻本に手を出したほうがよさそうな予感。