tooh’s diary

半角全角、常体敬体が入り乱れるカオス

3/27 AtCoder(-2進法)

こんばんは。しばらく更新しなかったのはチュウニズムの方ばかりコミットしていたためです。とーです。(AtCoderのstreak自体は地味に続いています)

AtCoder


ABC105C

与えられた数字を-2進数で表す問題 2進数とかではなくて負の数で与えられているのが何ともやり辛いところ


考え方は、例えば普通の2進数がどのようになっているかを参考にすると見えてくる

9(10進法)を2進数で表すことを考える これは1001になるが、まず右から一桁目は0もしくは1を表せることを考えれば、ここのビットが立っていれば(つまり1であれば)奇数、立っていなければ(0であれば)偶数を表すことは明らか なぜならそれよりも後ろ(二桁目以降)は2で割ったあまりに対して何の影響も及ぼさないから

というわけで、ここは1を立てておく
ここで1を消費したため、残りの桁では8を表せばよいと分かる

さて、二桁目より後ろを考えるとき、ここから後ろは2**1,2**2......と、必ず二の倍数を表すので、これを二で割って2**0(つまり1)、2**1......としたものを、8を二で割った数、つまり4を表すにはどうすればよいかを考えるのは同じことである

4は2で割り切れるので、一桁目(9を表すときには右から二桁目にある数字)は0でよい

そして、全く同じ要領で、4(から0を除いた数字、実質4)を2で割った数字2を、また二進法で表すことを考える
2は2で割り切れるので、一桁目(9を表すときには右から三桁目にある数字)は0でよい

また2を2で割ると、今度は1が出てきて、これは2で割り切れないので、二進法で表したときの一桁目(9を表すときには右から4桁目にある数字)は1にする

そして、1を消費したので、1から1を引いて0になった ここで終了する
その結果として、9の二進法表示として1001が得られた




今説明したやり方は、-2進法表記でも全く同様に使うことができる。つまり
①:Nが-2(2でもよい)で割り切れるなら、0を並べて-2で割る
②:Nが-2で割り切れないなら、1を並べて、ここで1を消費したのでNから1を除いて、除いた結果0でないなら-2で割る
③:②の結果が0になったならそこで終了する

という感じ(基本的にこのやり方は任意のn進法で使える)
注意として、2進法の時もそうだけど、下の桁から決定していっているので、ビットは前に前にとくっつけていくことを忘れないようにする





ABC110C

文字列を操作するやつ(きらい)

文字列SとTで、文字が一対一対応になっていればYes、そうでなければNoを出せばよい
例えばazzelとappleならば、
a:a
z:p
l:e
e:l
となっているので良いが、
chokudaiとredcoderでは、
c:r
h:e
o:d
k:c
u:o
d:d
a:e
i:r
と、cとiのどちらに対してもrが対応してしまうので(o,dも同様)、例えばc→rと変更したら、rhokudaiとなるが、その後でiをrに変更しようと思うとrとiの間で相互の変換が起こるので、ihokudarになってしまう
これが起こらず、かつちゃんと入れ替えができるのは文字が上と下で一対一に対応してることが必要条件になる これをコードに起こせばよい