ツバサの備忘録

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

考察系

ABC020 D - LCM Rush

問題 提出コード(100点) 提出コード(満点) 100点から満点にもっていくことができず、解説を見ました… 言われれば確かにそうだけど~って感じですね。 解法 まずは100点までです。 の制約が少ないので、について何かをするんだろうな、という気持ちになります…

ABC067 D - Fennec VS. Snuke

問題 提出コード 解説の解法が綺麗すぎますね!! 解法 1とN以外の頂点を、 1から、Nを通らないとたどり着けない頂点 Nから、1を通らないとたどり着けない頂点 1とNどちらも、もう片方の頂点を通らずにたどり着ける頂点 の3種類に分けることができます。図で…

ABC062 D - 3N Numbers

問題 提出コード やること自体は同じだったのですが、想定解がすごい綺麗で感動しました。ここでpriority_queueが使えるのですね~ 解法 この問題は、初期値を(前からNの長さの部分の総和)-(後ろからNの長さの部分の総和)とし、 真ん中のNの長さの部分を、 …

ABC077 D - Small Multiple

問題 提出コード 桁和関連の問題は本当に解ける気がしないです…方針が立ちません。解説を読んでもわからないので、数日寝かせていました。 解法 について、基本的には1を足すと桁和が1増加し(例外があります)、10倍すると桁和は据え置きです。 ということで…

グランディ数の問題の解き方メモ (ARC072 D - Alice&Brown)

あまりに苦手なので、やまさん(@yamasangamasan)に解き方のコツを聞いたのでメモしました。文章だらけなのでかなり読みづらいです... グランディ数を使う問題は、 二人零和有限確定完全情報ゲームです(!) AとBの2人がいて、ある操作行うようなゲームをしま…

ABC050 D - Xor Sum

問題 提出コード 方針がたってから遷移をバグなく求めるまでになんと半日かかりました! 解法 桁DPです。 というのも、2進数になおした2つの数字のペアについて、それぞれの桁についてありうる桁の組み合わせは、 の3種類のみです。 そして、これらの組み合…

codeFlyer (bitFlyer Programming Contest)予選 C - 徒歩圏内

問題 提出コード これを自力で解けなかったのは結構悔しいです…最近思い通りになかなか解けないですね 解法 ,,となるようなの組を探します。 要素が3つ存在するので、まずは真ん中を決め打ちしたときののペアの個数を求めることを考えます。 あるについて、…

codeFlyer (bitFlyer Programming Contest)予選 D - ハンコ

問題 提出コード 解法 基本方針は、いもす法を利用して移動したときに黒くなる部分を求めていくことです。 紙の左上にまずはハンコを合わせます。すると、 マスが黒かったとき、右にマス、下にマスの範囲内がすべて黒く塗られることになります。 ということ…

AGC024 B - Colorful Slimes

問題 提出コード 解法 スライムを好きなタイミングで捕まえることができ、捕まえる、魔法を唱える、捕まえる魔法を唱える…といったような順番で操作を行うことができます。ので、魔法を唱えるを唱える回数をまずは固定してしまって、捕まえるスライムの種類…

ARC077 D - 11

問題 提出コード 解法 ダブっている数字は数列に1つ必ず存在します。 ダブってる数字のうち左側にあるものを,右側にあるものをとしたとき、数列は次のようになっています。 ここで、はそれぞれ0個以上の要素を持っている数列です。 長さの部分列を数え上げる…

ABC113 D - Number of Amidakuji

問題 提出コード DPをします。 まずは、下準備をします。 ある高さについて、幅がのとき(つまり、本の棒があるとき)に、横線の置き方がいくつあるかを計算します。 これをとします。 のとき、横線はおけないのでです。 のとき、横線を置くか置かないかの2通…

ABC044 D - 桁和 / Digit Sum

問題 提出コード これが500点?という感じの難易度でした。苦手意識があり、全く違うベクトルの考察を始めてしまうので解ける気がしません… 解法 のとき、になります。それ以外でになるようなは存在しません。ということで、の場合は、が答えになります。こ…

ABC043 D - アンバランス / Unbalanced

問題 提出コード 解法 アンバランスな文字列tには、ある文字xが過半数以上存在しなければなりません。 これにより、tのうち少なくとも2つに1つ(以上)は文字xが存在しています。 なので、文字列tには、どこかに "xx" "x〇x" の2種類の並びのうちどちらかが存…

ABC042 D - いろはちゃんとマス目 / Iroha and a Grid

問題 提出コード 解法 modとコンビネーションが出てくるので、例によって逆元の知識を使用します。 例によってけんちょんさんの記事を載せておきます。 qiita.com 問題の条件を図で表すと次のようになります。 Sがスタートの位置、Gがゴールの位置で、黒く塗…

Tenka1 Programmer Contest (2018) C - Align

問題 提出コード 時間内に解きたかったですね… 解法 解説に詳しい証明が載っているのですが、並べた後の数列が凸凹になっていると、効率がよりよくなります。 みたいな感じです(逆もあり得ます)。 このとき、以下のような図で表現できます。上にある頂点は隣…

Tenka1 Programmer Contest (2018) D - Crossing

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

AOJ 2709 - 真っ暗な部屋

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

Tenka1 Programmer Contest (2017) D - IntegerotS

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

AOJ 2233 - Carrot Tour

問題 提出コード 解法 これ自力で解ききれなかったの悔しいですね… dp[i][j][k] = k回目の移動でiからjに移動するときの、それまでの移動距離の合計の最小値 とします。こうすることで、持っているにんじんの個数は自動的にkになります。 そして、 dis[i][j]…

AOJ 2600 - Koto Distance

問題 提出コード 解法 サンプルの図がわかりやすいのですが、ある座標(x,y)から距離w以内に効果がある場合、 (x-w,p)~(x+w,p)および(p,y-w)~(p,y+w)の範囲に効果があることになります。ここで、pは任意の数字になります。これは、横についてx-w~x+wの範囲を…

AGC027 B - Garbage Collector

問題 提出コード 解法 ゴミを回収しに行く回数(=ゴミを捨てる回数)を回と決め打ちし、そのときの最小値を求めます。 そして、最後にについて全探索して答えを求めることを考えます。 回ゴミを回収しに行くとき、ゴミを拾う回数は回、捨てる回数は回なので、…

ARC085 D - ABS

問題 提出コード 解法 シミュレーションをします。まず、前提として、どちらかはかならずを最後にもっています。 次にXのターンだとします。 このとき、Xはをとってゲームを終わらせることができます。このときの答えをpとしておきます(これは、現在のYの手…

ARC085 E - MUL

問題 提出コード 解法 燃やす埋める問題の応用です。 燃やす埋める問題についてはこちらを参考にするといいかと思います。 最小カットを使って「燃やす埋める問題」を解く 今回は、燃やす→売る、埋める→売らない、というようにして帰着させます。 s,tという2…

ARC085 C - HSI

問題 提出コード この問題すごく難しかったです(解説を見ています、以下の文章はほぼ解説そのまんまです) 解法 答えをとします。 1回の試行にかかる時間はです。これをとします。 このとき、回目の試行でACする確率pは、iに関係なく一定で、です。 また、回…

AOJ 2899 - 遭難

問題 提出コード 夏休みの宿題です。 この問題は、会津合宿で既読だけつけていたので、そのときにちらっと解説を聞いてしまっています。 くコ:彡 解法 解き方は2パターンあり、どちらも右手法を使用します。簡単に説明すると、迷路などで、右手を壁に当て続…

AGC028 B - Removing Blocks

問題 提出コード 解法 サンプル2がすごい実験に使いやすいのでこれを利用していくことで解けました。 まず、は、番目が足される回数に最後に掛け合わせるだけでいいので、これ以降は無視をします。 ということで、番目の数字が何回足されるか、を調べます。 …

AGC028 A - Two Abbreviations

問題 提出コード 解法 long longの制約になっているかどうかしっかり確認しましょう(n回目) まず、Lの最小値としてありうるのは、NとMの最公倍数になります。 よって、L全体としてありうるのは、Lの倍数になります。 ですが、実はLのp倍の長さの文字列がこの…

ARC086 D - Non-decreasing

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

ABC112 D - Partition

問題 提出コード の公約数をとします。 このとき、はで割り切れるので、もで割り切ることができます。 ということで、まず解の候補がの約数であることがわかります。これは、までを全探索して、それをで割ったときのあまりが0かどうかで判断すればよいです。…

AOJ 2707 - 監獄

問題 提出コード 解法 まず、答えが仮にxであったとします。そのとき、xは1回目の操作でどこにいくか、ということを考えてみると、 x - 1 - x/k となります。k、2k、3k…の人が処刑されるので、その人数分引けばいい、ということです。 次に、後ろから考えま…