ツバサの備忘録

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

全探索

AOJ 1637 色の切り替え

問題 提出コード 解説見たらやっていることが少し違ったのでメモしておきます。 まず、同じ頂点のボタンを2回押すと元に戻るので、それぞれのボタンについては"押す"か、"押さない"かの2通りだけ考えれば良いです。 そして、全ての頂点を1度押すことを考えま…

ARC 095 E - Symmetric Grid

問題 提出コード 解法 それぞれの行に含まれている文字の種類とその個数の状態関係について見てみると、 行をswapしても、列をswapしても、個数自体に変化はないことがわかります。 最終的に点対称になるので、先ほどの状態の一致不一致を使って、行と列それ…

AGC029 D - Grid game

問題 提出コード 解法 高橋君が動かない、という操作を選択した場合、青木君は動かない、という操作を行ってゲームを終了させればよいので、高橋君が駒を動かさない、という選択肢は存在しません。 よって、高橋君が動けなくなるように青木君がうまく動けば…

ABC138 E - Strings of Impurity

問題 提出コード 解法 に含まれ、に含まれない文字が存在する場合、答えは-1になります。逆に、それ以外の場合は、必ず答えを見つけることができます。 の部分列でを作る際、お互いの先頭から順番に、一致する部分を選んでいけばよいです。 作りたい文字列は…

AOJ 1619 - 弁当作り

問題 提出コード 解法 制約にと書いてあります。これがすべてです。 が大きいパターンとが大きいパターンで場合分けをします。 なので、実はが、簡単にビットで情報を持つことができます。 が小さいパターン 全探索をします。 それぞれの材料について、その…

AOJ 1161 - 覆面算

問題 提出コード 解法 愚直に見ていきます。 下の桁から順番に文字を決めていきます。 式が成り立っているかどうかを最後に番目の文字列と比較するとTLEをします(した)が、それぞれの桁についての数字を確定させた時点で、番目の文字列で対応する桁と比較し…

ABC129 D - Lamp

問題 提出コード 解法 が間に合うので、に設置した際に照らすことができるマスの個数がで求まれば、全探索をしつつ最大値を求めることでこの問題に答えることができます。 ということで、前計算をします。 まず、縦に伸びる光と横に伸びる光は無関係のため、…

AOJ 1195 - 暗号化システム

問題 提出コード 解法 最悪ケースを考えると、サンプルにあるような17711通りのパターンになります。 ということで、全部列挙してから文字列をソートし、10個出力するのが十分間に合います。 あとは、全部列挙する方法を考えていけばよいです。 操作終了後の…

ABC128 D - equeue

問題 提出コード 解法 から取り出した宝石をに再び詰めた後、再びその宝石を取り出すのは、ただ操作回数を無駄にしているだけなので、先に取り出す宝石の個数を決めた後、捨てる宝石を全て捨てるのが最適になります。 の左から取り出す宝石の個数を個、の右…

ABC128 C - Switches

問題 提出コード 解法 スイッチと電球の個数がとても少ないので、番目の電球に対して機能するスイッチの情報、およびどのスイッチを押すか、という状態をどちらもbitを利用して、int型の変数1つで持つことができます。 スイッチを押すパターンは通りで、多く…

AOJ 1551 A White Wall

問題 提出コード 解法 制約を見ると、愚直に全探索しても間に合うことがわかるので、ただひたすらに愚直に実装します。 今回は、の幅に塗りますが、これをに塗ると考えれば、に塗ることをに塗る、と表現できるようになり、配列のカウントに落とし込めます。 …

AOJ 2311 - お菓子の魔女

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

AOJ 3053 - Phone Number (RUPC2019 Day2 C)

問題 提出コード 解法 配置方法は9!通りなので、全てに対して探索を行いたいです。 ので、ある配置のときにかかる操作回数の最小値の求め方を探ります。 すると、次のようなことをすればよいことになります。 あらかじめ、文字列について、どの数字からどの…

ABC080 C - Shopping Street

問題 提出コード ぱっと読んだときに、何を言っているのかさっぱりわからずしばらく考えがまとまりませんでした。 解法 結局、曜日と午前午後、5種類と2種類と考えるのではなく、時間帯が10種類と考えてしまうのが楽だと思います。 こうすると、joisinoお姉…

ABC075 D - Axis-Parallel Rectangle

問題 提出コード 解法 まずは、4点を決めます。同じ頂点を選んでも問題ないです。 そうしたら、その4点を含むような長方形のうち最小のものを求めます。 この長方形の座標は、 右、上:それぞれ4点のx座標、y座標のうち最大のもの 左、下:それぞれ4点のx座標…

ABC074 C - Sugar Water

問題 提出コード 解法 全探索が間に合わないので、ある1箇所だけを探索せずに計算でぱっと求めるパターンです。 操作1~3を探索し、操作4はある1~3のパターンに対する最善手を計算によって求めます。 操作1をx回、2をy回、3をz回行ったとします。 このとき、…

ABC073 D - joisino's travel

問題 提出コード 典型+久々につかう知識問題。 解法 まずは、頂点数が200しかないので、が間に合います。ので、とりあえずワーシャルフロイド法を適用し、それぞれの頂点間の距離の最小値を求めておきます。 そして、通りたい頂点数は8しかないので、全探索…

ABC043 C - いっしょ / Be Together

問題 提出コード 解法 制約がめちゃくちゃ少ないので、愚直にやっていきます。 そろえる数字yを固定し、ひたすら数列すべてについてのコストの和を求めていきます。 1つのyに対し、コスト計算は数列の長さ分だけ時間がかかり、yの選び方は-100~100の200通り…

Tenka1 Programmer Contest (2017) C - 4/N

問題 提出コード 解法 について全探索をすると間に合わないです。ので、について全探索をして、そのときのを求めればよいです。 全てが以上以下になる解が存在するという保証があるので、はこの範囲で全探索をします。 を、となるような式にうまく変形します…

ARC087 C - Good Sequence

問題 提出コード 解法 xは数列の中にちょうどx個存在しないといけないのですが、今回数字を増やす操作ができないので、xの個数がx未満であったら、全て取り除かなければなりません。 ここで制約をみると、数列の長さは以下なので、この時点でこれを超える大…

ABC087 C - Candies

問題 提出コード 問題の制限をきちんと見れば、全探索で間に合うということがわかります。 が、特に何も考えていなかったので累積和をとりました。 この問題では、下に1回、右に回移動する操作を行うだけなので、回右に移動して下に移動、そして最後に残りの…

AOJ 2900 - 凸凹数列

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

AOJ 2889 - Aizu Competitive Programming Camp 2018 Day 3 A IPアドレス (Internet Protocol Address)

問題 解法 分ける点が3つのみなので、for文の3重ループで点をうつ場所を決めてから、それぞれが条件を満たしているかどうかチェックすることになります。 開始位置と終了位置、そして細かい条件のどれかでミスが生じると、デバッグが大変になるので気を付け…

AOJ 2898 - Aizu Competitive Programming Camp 2018 Day 1 C 素数

問題 解法 まずはエラトステネスの篩を適用して範囲内の素数をすべて求めます。 次にpとqのペアですが、素数同士の和が素数になるには、奇数と奇数の素数の和が偶数になる関係上、片方は2で固定されてしまいます。 ということで、片方を2に固定して、もう片…

ABC013 C - 節制

C - 節制 提出コード 数学に強い系か、実装のほうができる系によって解き方がかわる面白い問題です(これに限らず時々おこりますが...) 素直に全探索について考えてみます。 普通の食事をi日、質素な食事をj日、食べない日をk日として3重ループすると、間に合…

ABC007 C - Candles

C - Candles 提出コード 連続するk本のろうそくに火をつけたいです。 正の座標にあるろうそくと、負の座標にあるろうそく両方に火をつける場合、どちらか一方は折り返して原点に戻ってくる必要があります。 ですので、片方のろうそくをi本、もう片方はk-i本…

ABC011 D - 大ジャンプ

D - 大ジャンプ 提出コード まずはゴールにいくために最低何回、上下左右に移動するかを調べる必要があります。 この問題では上下、左右は反転しても何ら問題がないので、X、Yの入力は最初の時点で正に直してしまって問題ありません。 ということで、上下、…

ABC005 D - おいしいたこ焼きの焼き方

D - おいしいたこ焼きの焼き方 提出コード mp[i][j] = からまでの、長方形の部分の美味しさの総和 (ただし、添え字が0以下のときは0) として、入力と同時に累積和をとっていきます。 すると、ある長方形をl,r,u,d(それぞれ長方形の左、右、上、下の辺の番号)…

ABC004 C - 入れ替え,D - マーブル

C - 入れ替え 提出コード これは実験をある程度すると法則性が見えてきます。 重要なのはNを5で割った数と、そのあまりです。 この操作は5回で1セットになっていて、1セット完全に行うことで、当時先頭にいた数字が一番後ろまで移動します。 このセットが完…

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

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