ツバサの備忘録

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

再帰

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通りであり…