ツバサの備忘録

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

構築

ABC068 D - Decrease (Contestant ver.)

問題 提出コード 解法 操作が2種類あって考えづらいので、操作をひとまとめにします。 答えとなる数列の全ての数字にを足し、1回の操作を行うと、数列の最大値を1つ選びを減らす、というようにすると、回操作を行った後の状態はもともとの条件と同じ数列にな…

ABC055 D - Menagerie

問題 提出コード 構築です。 解法 番目の動物は、と番目の動物が何か判明していれば、自動的に決まります。 これは4通りあり、 番目が〇か×か、そして番目の動物がどっちであるか、です。 番目が〇で羊の場合 番目は番目と同じ動物になります。 番目が〇で狼…

ABC051 C - Back and Forth

問題 提出コード 解法 1週目に黒い矢印を、2週目に緑の矢印を通るように移動させてあげればよいです。矢印の向きや、黒と緑の順番は前後逆でも問題ないです。

Tenka1 Programmer Contest (2018) D - Crossing

問題 提出コード 今のところ、500点の構築問題は自分と相性がいいみたいで全勝中です(数問しかやったことないですが) 解法 の個数を、そしての個数をとすると、 自動的にとなります。自分以外の集合と、ちょうど1つずつ共通部分が存在するからです。また、~…

ARC086 D - Non-decreasing

問題 提出コード 隣り合った要素を比較すると、正負によって4パターンに分けることができます。 前後が正だった場合 前の方が大きいならば、前の値を後ろに足してあげれば、1回の操作で条件を満たします。 前後が負だった場合 前の方が大きいならば、後ろの…

ARC103 E - Tr/ee

問題 提出コード 解法 考察は終わっていましたが実装が間に合いませんでした。 まず、木を作るのに必要な要素は3つあります。 sの最後の文字が0 辺を1つ選んだ時点で、サイズはnより小さくなってしまうので、条件を満たすことができません。 sの最初の文字が…

ARC102 D - All Your Paths are Different Lengths

D - All Your Paths are Different Lengths 提出コード n進数を利用する、というところまではよかったのですがそこから歯が立ちませんでした。 結論から言うと2進数を利用します。 まずは大元となる2進数のグラフを作成します。 となるうちの最大のxを求めま…