ツバサの備忘録

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

再帰

AOJ 1176 - 輪番停電計画

問題 提出コード 解法 はじめに、2次元累積和を用いて、ある長方形の範囲の需要の合計をで求めることができるようにしておきます。 ここから、DPを行います。 長方形の左上が,右下がとなるような範囲のグループの分け方の最適解 とします。最適解、なのでグ…

WUPC2019のお話(解法編)

ということで、今回は各問題についての簡単な解法と、その感想です。 まだ解けていない問題もいくつかあるので、ご容赦ください… 運営側としてどんなことをしたか、についてはこちらの記事をご覧ください。 emtubasa.hateblo.jp 各問題の方針と感想 A - WAse…

Educational DP Contest / DP まとめコンテスト P - Independent Set

問題 提出コード 解法 を色としたとき(1:白、0:黒)の、根とする部分木の色の決め方 とします。 全体の根はで固定します。 の子をとします。 すると、を黒で塗るには、の子はすべて白でなければならないこと、を白で塗る場合は、の色は何色でもよいことを考え…

ABC115 D - Christmas

問題 提出コード まずは、レベルバーガーをすべて食べたときの、食べる全体の枚数および食べるパティの枚数を求めます。 食べる全体の枚数をとすると、 となります。 食べるパティの枚数をとすると、 となります。 初期値は、です。 答えは、再帰によって求…

ABC114 C - 755

問題 提出コード C問題で再帰を書くの、バグらせるのが怖くないですか…? 解法 最終的な答えがそこまで多くないので、全てのパターンを列挙していきます。 再帰を用いて解きます。 引数を2つ用意し、今上から何桁決定したか、という変数とx、今どんな値にな…

ABC018 D - バレンタインデー

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

AOJ 1174 - 同色パネル結合

問題 提出コード i回目に色xを選ぶ、とすると6種類の色を5回選ぶので、全体でパターンあります。 現在、左上に結合しているパネルの位置の情報がわかれば、i回目に色xを選んだ際に新しく結合する部分は深さ優先探索で求めることができます。 あとは、i回目に…

ARC087 E - Prefix-free Game

問題 提出コード 解法 グランディ数の問題かつ、二分木が関係していて…と割と惜しいとこまではいけた(つもり)なのですが、最後がうまくまとまらなかったので解説を見てACしました。 完全二分木を組み立て、そこに今回の文字列をうまく落とし込むと、現在選…

AOJ 2891 - な◯りカット (Namo.. Cut)

問題 提出コード 解法 再帰を書いていたらバグが取れなかったのでグーグル先生を使ったところ、このような記事が見つかったのでこちらの橋検出の考え方を参考にさせていただきました。 ノードを見た順番に番号を振っていきます。これを再帰的に繰り返し、一…

AOJ 2900 - 凸凹数列

問題 提出コード 解法 半分ぐらい貪欲です。 前から貪欲に、凹凸がズレていたら操作、ということを行うだけで条件を満たす数列を作成できます。 なので、最大でも数字の個数分の回数しか操作を行うことはありません。 ということで、基本的には貪欲に操作を…

京都大学プログラミングコンテスト(KUPC)2013

競プロの練習会で、こちらのセットを使用したバチャコンをチームで行ったので解いた問題についてのメモをしていきます。 チームメイトはICPC出場時と同じくやまさん(@yamasangamasan)、べるくん(@dora_marutation)でした。加えて、相手チームがICPC本戦出場…

AOJ 1133 - Water Tank

Water Tank | Aizu Online Judge 提出コード そのまま実装するとかなり重くなりそうなので、なにかいい手がないかを調べます。 初見で解けなかったときに、こちらのブログ( Water Tank (AOJ1133) - sigma425のブログ )に一度目を通していたため、トップダウ…

AGC26

二回目のAGCでした。 A - Colorful Slimes 2 提出コード まず入力時に、どの色のスライムがいるかを調べます。前から順番にスライムをチェックしていって、一個前のスライムと色が同じだったらその都度色を現時点で使ってない色に変えていけば、最短手数で合…

SoundHound Inc. Programming Contest 2018 -Masters Tournament-

コンテスト開始2分前ぐらいまでアイスを食べていて、乗り遅れそうになりました。 A - F 提出コード if文を使って、aとbの足し算、掛け算が15になるかどうかを調べます。どちらでもなければその時用の出力をして終わりです。 B - Acrostic 提出コード 入力用…

ICPC国内予選2018に参加してきました

というわけでとりあえず参加だけしてきました。 べるくんとやまさんの三人チームで出場しました。基本的にやまさんが考察をし、僕が実装して、困ったらべるくんがデバッグやほかの問題の実装をするというスタイルでいきました。 A問題 所得格差 提出コード …

AOJ 1197 - サイコロ職人

サイコロ職人の朝は早い。 サイコロ職人 | Aizu Online Judge 提出コード さて、立方体を転がしてある面が下になった回数をカウントしたときに、指定された6つの数字のグループと一致するように転がせ、という問題です。 転がす方向は東西南北の4通りであり…