ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

bit

ABC129 E - Sum Equals Xor

問題 提出コード 解法 制約を見ると明らかに桁DPのような匂いがするので桁DPをしました。 の上から桁目をとします。 となるが存在した場合、をすると繰り上がりが発生するので、となります。逆に、それ以外のはどれを使用してても問題の条件を満たします。 …

ABC128 C - Switches

問題 提出コード 解法 スイッチと電球の個数がとても少ないので、番目の電球に対して機能するスイッチの情報、およびどのスイッチを押すか、という状態をどちらもbitを利用して、int型の変数1つで持つことができます。 スイッチを押すパターンは通りで、多く…

CPSCO2019 Session3 E - Enumerate Xor Sum

問題 提出コード 解法 のときの答えを求めてみます。 については、の累積xorをとっておくことでで求めることができるので割愛します。 とのxorを取った値をとすると、xorの定義から、それぞれの桁について、の立ってるビットの個数が1ならばのその桁は1、そ…

ABC121 D - XOR World

問題 提出コード 解法 についてxorを取るとき、についてxorを取った結果と、についてxorを取った結果の2つの数字について、改めてxorを取ればよいです。ということで、の区間の数字についてxorを取った結果を求めていく方法を探ります。 これは、それぞれの…

ABC119 C - Synthetic Kadomatsu

bit

問題 提出コード 解法 全探索をすればよいです。 Aに使う竹、Bに使う竹、Cに使う竹の3種類にまず分けます。 これは、bitで竹を表現して全探索するとやりやすいかと思います。 ビットの部分集合を列挙する方法はこちらをご覧ください。 techtipshoge.blogspot…

ABC080 C - Shopping Street

問題 提出コード ぱっと読んだときに、何を言っているのかさっぱりわからずしばらく考えがまとまりませんでした。 解法 結局、曜日と午前午後、5種類と2種類と考えるのではなく、時間帯が10種類と考えてしまうのが楽だと思います。 こうすると、joisinoお姉…

ABC018 D - バレンタインデー

問題 提出コード 解法 部分点が、どうせ男女の組み合わせについてすべてのパターンを試すんだろうなぁ、という感じがしたので、どうせ男子か女子どちらかのみを探索すると答えを求めるようにすることで高速化をするのかなぁ、という気持ちになります。 とい…

第5回 ドワンゴからの挑戦状 予選 B - Sum AND Subarrays

bit

問題 提出コード 解法 たかだか1000個の数字しかないので、まずはあり得る部分列の和をすべて書き出します。 その後、一番大きい数字を2進数に直したときの、一番左側のビットから順番に、使用できるかどうかを判定していきます。 左側から順番に使用すると…

AOJ 2709 - 真っ暗な部屋

問題 提出コード 解法 真っ暗な部屋が多くて16個しかないので、真っ暗な部屋に関する何かしらの情報をbitで持つことができます。 基本的な考え方は、幅優先探索です。 例えば回指示を出すとしたとき、指示列の選び方は種類になります。全ての部屋に対して、…

Tenka1 Programmer Contest (2017) D - IntegerotS

問題 提出コード (こちらは手直しを加えたコードになります、最初に通したコードはこちらです) 手直しを加えた理由が、当初がなぜかlong long型に収まらないと勘違いしていたため、unsigned long long型で計算をしているため、いろいろ複雑になってしまって…

AOJ 1175 - そして,いくつになった?

問題 提出コード 個人的にICPCの中でも結構好きな部類の問題です。 解法 今回もc言語です。 メモ化再帰をしていきます。 円盤の枚数はたかだか24で、状態としては”残っている”か、”取り去られている”の2通りです。なので、全体で種類の状態が存在しますが、…

AOJ 1138 - Traveling by Stagecoach

問題 提出コード 解法 単一始点最短路問題なので、なんとなくダイクストラ法が使いたいなぁ、という気持ちになりました。 その後、馬車券の枚数を見ると、制約が8ととても少なく、都市の数自体も30以下とかなりすくないことから、馬車券を使ったかどうかbit…

ARC087 D - FT Robot

問題 提出コード 解法 やることはこちらの記事の問題と同じです。 まず初めに、縦と横の移動はそれぞれ独立なので、縦の移動と横の移動に分解をして、それぞれが目的の座標にいけるかどうかを判定します。 次に、移動してたどり着くことができる場所について…

AOJ 2894 - Aizu Competitive Programming Camp 2018 Day 3 F 01 文字列と窓 (Binary String with Slit

問題 解法 サンプルの最後のケースで実験をすると、なんとなく見えてきます。 まず、移動の手段をすべて書くと、 01 → 10 10 → 01 10 → 11 11 → 10 の4通りしか存在しません。 そして、SとTが一致していない、一番左側の部分を一致させるには、それより右側…

SnackDown 2016 - Jealous Numbers

問題 与えられた集合から、任意の2つの元が互いに素になっているような部分集合をつくり、最大となる要素数を出力する、というものです。 これをT回繰り返します。 解法 まずはじめに、1はすべて部分集合にいれることができるので、1が入力された回数だけ別…

SnackDown 2016 - Robot Walk

問題 ロボットに2×N+1回の命令が与えられます。 奇数回目:数字が与えられるので、ロボットは指定された数字だけ、今向いている方向に移動します。 偶数回目:LまたはRの文字が与えられるので、ロボットは指定された方向に90度回転します。 これを、原点からス…

ABC041

バチャコン3回目です。初めてbitDPの問題に触れました。 A - 添字 提出コード 今回のA~Cはかなりシンプルでした。 A問題は、素直に文字列sのi番目の文字を出力すれば良いです。配列の最初が0になっていることだけ気を付ければ大丈夫です。 B - 直方体 提出コ…