ツバサの備忘録

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

ダイクストラ法

Waseda Orientation Programming Contest 2020 J - トレジャーハンター

問題概要 解法 Med Large 1つめ:01ナップサックに帰着 2つめ:個数制限なしナップサック 3つめ:ダイクストラ法 おまけ(Med解以外の想定TLE,MLE解法) コード 問題概要 種類のはしごがあり、番目のはしごの長さはです。 以上以下の値で、以下の条件を満たさない…

AOJ 2334 - 街を駆ける道

問題 提出コード 解法 明らかに、線分とが交差しない場合は、それぞれの街を直接結ぶのが一番距離が短くて済みます。 つまり、今回考えるべきなのは、とが交差する場合になります。 このとき、仮にの経路を、と交差しないように迂回して作成したとすると、ど…

AOJ 2585 - 一日乗車券

問題 提出コード 解法 1日乗り放題になる路線をビットで表したものがとなるようにする際の、1Dayパスポートの合計金額の最小値 をまず求めます。 これは、配るDPを用いて、を繰り返し計算していけばよいです。で求まります。 では、乗り放題の路線を決め打ち…

AOJ 2402 - 天の川

問題 提出コード 解法 任意の五芒星から別の五芒星に向かう際に通る最短距離さえ計算できれば、あとはベガからアルタイルに向けてダイクストラ法で最短経路を計算すればよいです。 五芒星は5本の線分でできています。ということで、2つの五芒星の最短距離を…

ARC064 E - Cosmic Rays

問題 提出コード 解法 あるバリア内は好きな座標に移動できます。 ので、あるバリアから、別のバリアへと移動することを考えます。 そのとき、2つのバリアについて重複する箇所が存在すれば、そのバリア同士は自由に行き来することができます。そうでないと…

AOJ 1169 - 最強の呪文

問題 提出コード 解法 それぞれの頂点にたどり着くときに文字数がになっているような呪文の中では、最強の文字列が常に一意に決まります。 ループをしない場合、文字数は最大でも240文字程度にしかなりません(頂点数が40、辺に与えられた文字列の長さは最長…

AOJ 1162 - 離散的速度

問題 提出コード 解法 都市から都市に速度で移動してきたときにかかる時間の最小値 とすると、現在の都市、1つ前の都市、現在の速度、現在経過した時間をひとまとめにしつつダイクストラをすればこの配列を埋めることができます。 キューから取り出した要素…

AOJ 2151 - 勇敢なお姫様またも現る

問題 提出コード 解法 頂点を増やします。 都市に着いた段階で予算のうちだけ消費するような経路の中で、襲われる人数の最小値 とすると、今いる都市、消費した予算、襲われる人数を一緒に持った状態でダイクストラ法を適用すれば良いです。 次の都市に遷移…

ABC126 D - Even Relation

問題 提出コード 解法 木、とは書かれているのですが辺に重みがあるのでダイクストラをしてしまいました。 ある頂点と別の頂点の距離が奇数の場合、その部分は確実に色が異なります。 これを繰り返すと、結局はある頂点を一つ決めた際に、そこからの距離の偶…

AOJ 1553 Manhattan Warp Machine 1

問題 提出コード 解法 ある地点からは、ボタンを押すと正負2つの向きに進むことができてしまうので、単純なDPを行うことができません。 ので、代わりにダイクストラ法で始点から進んでいくと、うまく計算することができます。 コストを辺の重みとみなし、そ…

AOJ 1150 - 崖登り

問題 提出コード 解法 面倒くさそうに見えますがダイクストラをします。 マス目が少ないので、左のマス目、右のマス目、どちらの足を動かす番か、という情報を全て持ちながらダイクストラができます。 足を動かす際は、動かさない方の足を基準にして、距離と…

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

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

AOJ 2021 - お姫様の危機

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

AOJ 3055 - こたつがめを燃やさないで (RUPC2019 Day2 E)

問題 提出コード 解法 マス目を移動する際のコストを辺とみなしながらダイクストラ法を用いていくとよいです。 遷移の種類はいくつかあり、 コストで、塀でない上下左右の隣接したマスに移動する コストで、上下左右の隣接したマスに移動する コストで、右上…

ゆるふわ競プロオンサイト参加記

2/9に東京で行われました、@matsu7874さん主催の競プロオンサイトイベント、に参加してきました! コンテスト自体は全8問で、2時間のセットでした。自分は、ABCDEGの6完でした! B式A+B 集合写真 線香 最短経路は何本ありますか ガソリンスタンド 射的 感想 …

ABC022 C - Blue Bird

問題 提出コード1 提出コード2 解法 まずは想定解です。 頂点1から出るときの辺と、頂点1に帰るときの辺は違うものでなくてはなりません。 そのときの頂点をとすると、からは純粋な最短経路問題に置き換えることができます。 この問題では、頂点の個数が300…

ABC070 D - Transit Tree Path

問題 提出コード 解法 最短経路を求める問題で、頂点数があるので、各クエリごとにダイクストラ法を適用していたのでは間に合いそうにありません。 そこで、経由する点がで固定であり、この木が無向グラフであることに注目すると、から各頂点への最短距離を…

AOJ 1138 - Traveling by Stagecoach

問題 提出コード 解法 単一始点最短路問題なので、なんとなくダイクストラ法が使いたいなぁ、という気持ちになりました。 その後、馬車券の枚数を見ると、制約が8ととても少なく、都市の数自体も30以下とかなりすくないことから、馬車券を使ったかどうかbit…

Benelux Algorithm Programming Contest 2016 E Charles in Charge

問題 N個の頂点と、M個の重み付きの辺があるグラフが与えられます。 頂点1から頂点Nに行く最短経路に、X%加えた新しい距離以内で、頂点1から頂点Nにたどる道の中で辺の重みの最大値が、最も小さくなるときの、辺の重みの最大値を求めなさい、というものです…

AOJ 2332 - 時空のスゴロク・ロード

時空のスゴロク・ロード 提出コード すごろく問題です。 すごろく問題なので、ゴールからダイクストラ法を利用してスタート地点に戻りましょう。 まずは下準備をします。 最初に、ある地点からサイコロの目がi(1~6のどれかです)だったときにどこに進むことが…

AOJ 0601 - フクロモモンガ(JOI2013本戦4)

フクロモモンガ | Aizu Online Judge 提出コード けんちょんさんのブログに載っていたため解いたのですが、DP!と思って問題を読んでみたらむしろダイクストラ法の問題だな、という感想でした。条件がそこそこ複雑だったので、配列の要素を変数でいちいち置…

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

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

Mujin Programming Challenge 2018

目標は200位でした。レート順400位ぐらいだったので運次第、と思ってました A - コンテスト名 提出コード 頭が真っ白になったので素直に全部書き出しました。与えられる文字の長さがそもそも5に満たない場合の条件を途中まですっかり書き忘れていたので危な…

SoundHound Inc. Programming Contest 2018 -Masters Tournament-

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