ツバサの備忘録

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

AtCoder Petrozavodsk Contest 001 D - Forest

問題 提出コード 解法 まずは、全ての木を連結にするには、それぞれの木について、頂点を少なくとも1つ選んで連結にする必要があるので、それぞれの木から、最もコストが小さい点を1つずつ選んでおきます。 また、コストを最も少なくして全てを連結にするに…

AtCoder Petrozavodsk Contest 001 C - Vacant Seat

問題 提出コード 解法 インタラクティブ問題なので、二分探索を考えていきます。 まずは、どこか1つの席の情報がわかっていないと何も始まらないので、番の席を特定します。 ここが空席ならばその時点で終了、女性だったならば、男性だった場合と真逆のこと…

AtCoder Petrozavodsk Contest 001 B - Two Arrays

問題 提出コード 解法 とを同じ数字にそろえる場合に、3パターンの選択の方法があります。 を選び、以外を選ぶパターン はになり、は据え置きです。 この方法だと、かつが偶数の場合にそろえることができます。 とを選ぶパターン ,になります。ので、の場合…

ABC102 D - Equal Cut

問題 提出コード 解法 パッと見とっつきにくい問題。 まずは、3つのうち、どこか1つの仕切りを固定して考えるとして、どの仕切りを固定すると見通しがよくなるかを調べます。 まず、右端の仕切りを固定することと、左端の仕切りを固定することによる見通しの…

AOJ 1156 - ちょろちょろロボット

問題 提出コード 解法 マス目を移動するコストが移動方法によって異なる迷路問題なので、ダイクストラをします。 マスで、を向いているような行き方の中でのコストの最小値 とします。あとは、現在のマス、方向、コストを1まとめにし、ダイクストラ法を利用…

AOJ 1155 - 如何に汝を満足せしめむ? いざ数え上げむ…

問題 提出コード1 提出コード2 解法 構文解析です。 変数がP,Q,Rの3種類しかないので、それぞれについて、値が0,1,2だったパターンの通りを調べればよいです。 構文解析の処理を1つの関数にまとめて再帰をしている方法が提出コード1、それぞれの役割に分担し…

AOJ 2885 - 分割統治

問題 提出コード 解法 まず、問題の条件を満たすようなパターンについて整理します。1つめのサンプルを見てみると、例えば下のようなパターンがあり得ます。 青が太郎、黄色が次郎、緑が花子さんの統治している国になります。 結局のところ、 太郎君(花子さ…

AOJ 2825 - クイズ

問題 提出コード 解法 最終問に必要な得点が最大になるとき、の中で少なくとも1人は、その人が答えることができる問題に全て答えています。 同様に、少なくとも1人は、その人しか答えられない問題以外は全て答えられません。 ということで、それぞれの人につ…

AOJ 2153 Mirror Cave

問題 提出コード 解法 普段のグリッドに対するBFSが2次元ならば、今回は4次元です。 Len君が、Ren君がにいるときに、そこから行くことができる4通りの方向に進みます。 そして、に行くことができるかどうかを調べていき、それぞれがゴールのマスに同時にたど…

AOJ 2021 - お姫様の危機

問題 提出コード 解法 町の数が少ないので、まずは任意の2つの町を結ぶ最短経路を求めます。これは、ワーシャルフロイドを利用すれば簡単に求めることができます。 あとは、スタート地点から、今いる地点から分以内で行ける、冷凍施設のある町のみを経由して…

AOJ 2002 - X-Ray Screening System

問題 解法 解法 まずは、それぞれの文字が、隠れている部分を含めて長方形になり得るかを調べます。そして、その後で、重なっている部分が矛盾していないかどうかのチェックをします。 ということで、まずは長方形になりうるかどうかのチェックをします。い…

ABC124 D - Handstand

問題 提出コード(1) 提出コード(2) 解法 1...(または0...)が連続しているとき、連続している部分は1つにまとめてしまいたいので、ランレングス圧縮のように、連続して何個続いているか、という情報に置き換えておきます。 今回の問題の場合、0...が続いてい…

AOJ 2741 - インビジブル

問題 提出コード 解法 ゲーム系で、ぱっと貪欲な解法がなさそうだったので、メモ化再帰をすることにしました。6次元DPです。 とし、それぞれの添え字が 先手が次にスタックにカードを置くとき上から何枚目のカードを置くか 後手が次にスタックにカードを置く…

AGC024 B - Backfront

問題 提出コード 問題 まず、最悪手でソートすることができます。これは、から順番に、一番左側に移動していけばよいです。 ということで、さらに効率的な方法を探ります。 今回の操作では、両端に数字を移動させることはできますが、逆に真ん中に数字を挿入…

第5回 ドワンゴからの挑戦状 本選 A - Taro vs. Jiro

問題 提出コード 解法 まずは、が奇数の場合について考えます。 太郎目線で考えると、"初手で行ける範囲内に青いマスが存在していれば必ず勝利できる"となります。 何故かというと、青いマスが最初のマスに隣接していた場合、初回の行動で太郎君はその青いマ…

第3回 ドワンゴからの挑戦状 予選 C - スキーリフトの相乗り

問題 提出コード 解法 まず、順番は全く関係なく、できるだけ多くの4人グループを作成していくことだけを考えればよいです。 先にグループを決めてしまえば、決めたグループの中の誰かが先頭に来た時点で、他の人達と相乗りをすればよいです。 ということで…

ABC097 D - Equals

問題 提出コード 解法 と、およびとが交換可能な場合、とは2回の操作で交換可能になります。 このようなことが全てのペアについて言えるので、結局は 入力で与えられるを辺とみなして頂点辺のグラフを作成したときに、最終的に連結な頂点同士はスワップ可能 …

九州大学プログラミングコンテスト2018 F - Team Making

問題 提出コード 解法 制約にbitDPをしてくださいと書いてあります。 ので、実際にbitDPを考えてみます。 今チームを組み終わっている人の状態がであるときの、これ以降のチームの組み方 とすると、まだチームを組めていない人の中で組めるようなチームの集…

九州大学プログラミングコンテスト2018 E - Treeone

問題 提出コード 解法 まず、を変える、としたとき、どんな数字に変えればよいか、ということを考えてみます。 このとき、部分列の総和に影響がでるのは、もちろんを部分列に含むものについてのみで、含まないものは総和が変化することはありません。 さて、…

九州大学プログラミングコンテスト2018 D - Novelist

問題 提出コード 解法 王都から都市へ移動する依頼をうけるとき、その後に王都からへ移動する依頼を受けるには、一旦から王都へ戻る依頼を受ける必要があります。 ということで、王都を出て、また王都へ戻る期間を、金貨が2枚もらえる1つの区間と見て、期間…

九州大学プログラミングコンテスト2018 C - Ito Campus

問題 提出コード 解法 何も考えずにうしくんのゴールへの行き方をBFSで求めようとすると、マス目を移動するたびに安全なマスかどうか調べるため、時間内に解くことができません。 しかし、この問題ではイノシシが移動することはないため、安全なマスであるか…

AOJ 2311 - お菓子の魔女

問題 提出コード 解法 あんまり書くことはないです。 たかだか64ターン、そのときにクッキーを置く候補がたかだか64マス、 1つの候補について、置き換わるクッキーの個数や場所を調べるのに、縦横斜めの8方向を調べればよく、多くても20マス前後です。 とい…

AOJ 2254 - 最短ルート

問題 提出コード 解法 制約を見ればbitDPと書いてあるのでbitDPをすることにします。 まず、番のステージをクリアした後に、再び番目のステージを行くことは考えなくていいです。2回以上同じステージに行くことで得をすることはありません。 ということで、…

AtCoderで青色になりました

ということで、色が変わると自分語りの記事が書ける(要出典)ので、書いていきたいと思います。この手の記事は初めてなので、今までの推移をまとめて書きます。 青に…なりました!!! pic.twitter.com/QU44J6NerW— ツバサ (@emtsu_ba) 2019年3月30日 目次 目…

エクサウィザーズ 2019 D - Modulo Operations

問題 提出コード 解法 (現在黒板に書かれている数字に影響があるような数字を取り除くことをここでは”使う”、ないような数字を取り除くことを”使わない”と表現します) まず、回目に取り除いた数字よりも大きい数字を、回目以降で取り除いても、黒板に書かれ…

エクサウィザーズ 2019 C - Snuke the Wizard

問題 提出コード 解法 後ろから見ると見通しがよくなるパターンの問題です。 ”消滅しないロボットの左端"をとします。これを、で求めていきます。同様に右端をとし、最後にその区間に含まれるロボットの数、つまりを求めれば答えとなります。 左端と右端は、…

ABC122 D - We Like AGC

問題 提出コード 解法 4次元DPをします。 問題の条件を満たす文字列が存在したときに、新しく最後尾に1文字加えてなお問題の条件を満たすのがどういう場合かを考えています。 追加する文字が'A'または'T'のとき がどうなっていても問題の条件を満たします。 …

AGC032 A - Limited Insertion

問題 提出コード 解法 操作を逆順で見ていき、数字を取り除いていくことを考えます。今現在の数列をで表すと、となった場合に番目の数字を取り除くことができます。 この操作を行った場合、番目以降の数字は順番が一つ前になります。 ですが、番目より手前の…

AOJ 2014 - 土地囲い

問題 提出コード 解法 黒の杭と拡大隣接してるマスは、幅優先探索を用いて行うことができます。白も同様です。 ということで、それぞれの色について、拡大隣接しているマスをすべて洗い出します。 その処理が終わったら、片方の色についてのみ拡大隣接してい…

AOJ1626 - 超高層ビル「みなとハルカス」

問題 提出コード 解法 解の候補について、フロアのうち最下層の階数を、フロアの総数をとします。すると、の階を借りることになるので、料金は次のようになります。 これがと一致するので、結局 という条件が成り立つことになります。 を1つ固定すると、は式…