2018-02-01から1ヶ月間の記事一覧
問題(外部リンク) 3268 -- Silver Cow Party 実装の概要 (2/20 下部に追記あり) パーティー会場xまでの往復距離の最大値を求めたいので、それぞれの地点からxまでの最短距離と、xからそれぞれの地点までの最短距離を求める必要があります。 Nアルゴリズ…
問題(外部リンク) 3259 -- Wormholes 実装の概要 今回の問題ではそれぞれのfieldを行き来するのにpathとwormholeを使うことができ、後者では時間を遡ることができます。 つまり、wormholeの移動コストをマイナスとして扱い、負の閉路(移動距離がマイナス…
問題(外部リンク) 2139 -- Six Degrees of Cowvin Bacon 実装の概要 aとbが共演したことがあれば距離1、aとbは共演してはいないがcはaやbと共演したことがあれば距離2、…というようにab間の距離を定義すれば全点対最短路の問題と考えることができます。 n …
問題(外部リンク) Convenient Location | Aizu Online Judge 実装の概要 ある点から他の点までの最短路を全ての点について行う全点対最短路問題なのでワーシャルフロイド法で解くことができます。かかりますが、町の数が最大でも10なので時間は気にしなく…
問題(外部リンク) Marked Ancestor | Aizu Online Judge 実装の概要 それぞれのノードに自分の親のidを記憶させます。今回の問題では下に向かって探索することはないので子のidは不要です。 あとはループで親を次々と巡りながらマークされたノードを探しま…
問題(外部リンク) Hit and Blow | Aizu Online Judge 実装の概要 AとBの数列を比較し、数字がちょうど一致しているか、あるいは一致していなくても数列に含まれているかを判断する問題です。 今回の実装では入力を受け付ける際に「その数がAの数列に含まれ…
問題(外部リンク) Physical Experiments | Aizu Online Judge 実装の概要 問題ページに時刻tにおける速度vと座標yの式が与えられているため、それらを連立してyとvの式を作ることもできます。 ただ、y=avのような形で表すと最終的に階で答える際に階数を繰…