ツバサの備忘録

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

2018-09-04から1日間の記事一覧

ABC012 D - バスと避けられない運命

D - バスと避けられない運命 提出コード ワーシャル-フロイド法を利用して、バス停iからバス停jに行くための最短時間をですべて記録します。 終わったら、バス停iについて、そこからバス停jに行くまでの最悪時間を、jで全探索してiごとに記録します。 あとは…

ABC012 C - 九九足し算

C - 九九足し算 提出コード forの2重ループを回し、1×1から9×9までの和を求めます。もちろん、問題の制限から和が2025であることを見抜いても問題ないです。 forの2重ループを回し、i×jが2025とNの差であったならば、答えとして出力します。

ABC011 C - 123引き算

C - 123引き算 提出コード 何故かハマってしまいまったく歯が立たなかった問題になります。 100回”以内”でゴール(0にする)すればいいので、とりあえず3をどんどん引いて行ってしまうのが最善の手になります。 もし3引いたときにNG数字にひっかかってしまうよ…

ARC102 D - All Your Paths are Different Lengths

D - All Your Paths are Different Lengths 提出コード n進数を利用する、というところまではよかったのですがそこから歯が立ちませんでした。 結論から言うと2進数を利用します。 まずは大元となる2進数のグラフを作成します。 となるうちの最大のxを求めま…

ABC009 D - 浮気予防

D - 浮気予防 提出コード 最小カットの問題に初めて触れました。 まずは、女の子と高橋君を頂点、友人関係を辺としたグラフを作成します。 そして、頂点0からへ繋がるパスが存在しなくなるような辺の切り方を考えることになります。 ここで、複数のゴールが…

ABC107 D - Median of Medians

D - Median of Medians 提出コード 初めてBITを使った問題です。 この問題では、中央値となる条件をうまく言い換えていき、最終的に転倒数を求める問題に帰着させます。転倒数を求める段階で、BITを利用します。蟻本をみたらそこにも載っていた問題になりま…

ABC007 C - Candles

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

ABC006 C - スフィンクスのなぞなぞ

C - スフィンクスのなぞなぞ 提出コード つるかめ算の3つバージョンですね。 まず初めに、全て2本にしても余る(n×2>m)の場合と、全て4本にしても足りない場合(n×4<m)の場合は、答えが-1のパターンとなります。 次に、真ん中、つまり足が3本の老人に注目します。 とりあえず全員が老人だと仮定したときに、目標となるmとのずれを調べます。 もちろん、全て老人だった場合にmと一致する場合は、それが答えとなります。 n×3>mの場合 足を減らす必要があります。差の分だけ、老人を大人に置き換えてあげると、うまくいき</m)の場合は、答えが-1のパターンとなります。>…

ABC002 C - 直訴

C - 直訴 提出コード 問題のページにヒントが書いてあるので、それをもとに計算すればいいです。 ある一点を原点に移動するように、ほかの2点も移動させてから、公式に当てはめましょう。

ABC011 D - 大ジャンプ

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