ツバサの備忘録

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

ダイクストラ法

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 提出コード 入力用…