ダイクストラ

ABC035-D トレジャーハント atcoder.jp 解いた時のレート：1340 ACコード atcoder.jp ABC035-D トレジャーハント ACコード 考察 正しい考察に至るまでの的外れな考察 最適な経路の考察 事前計算 実装 考察 決まった経路の上でどのような移動が最適かを考えると、1番を出発して1番に戻ってくるまでに通る頂点の内最もの高い頂点に出来るだけ長く留まるのがいいと分かりました。 つまり、1番を出発し1番に戻ってくる経路の長さを、経路に含まれる頂点の内最も高いをとすると、を最大化することが目標になります。 正しい考察に至るまでの的外れな考察 経路に含まれる頂点の内の…

緯度経度などの位置情報を表すデータを含んだデータセットである「地理データ」。この「地理データ」を分析・活用するための前段として、「地理データの分析で何ができそうか」というイメージを掴んでいただけるよう、地理データの基礎的な概念や処理フローを解説したブログです。

開発 進捗なし 競プロ edu102-E ただの拡張ダイクストラだった なぜすぐ見えなかったのか edu102-F ただのフロー? 誤読していた。O(n^2) 辺張るとまずいので節約して張る。 ラテン語 Ritchie’s Fabulae Faciles: 進捗なし Ubi Cāritās 第1段落 - 合唱曲のラテン語翻訳 訳した。 チェス chess.com bullet 1000 (進捗なし) chess.com tactics: 2173 -> 2165 (-8) lichess tactics: 2194 (進捗なし)https://www.chess.com/puzzles/pro…

「なっとく！アルゴリズム」を読みました。 なっとく！アルゴリズム作者:アディティア・Y・バーガバ発売日: 2017/01/31メディア: Kindle版 特に大事だと思われる、基本となるアルゴリズムを丁寧にわかりやすく説明してあります。 簡単な内容一覧は以下の通りです。 ソート 再帰 ハッシュテーブル 幅優先探索 ダイクストラ法 貪欲法 動的計画法 ｋ近傍法 次に学ぶべきアルゴリズム10選 木構造 転置インデックス フーリエ変換 並列アルゴリズム MapReduce プルームフィルタと HyperLogLog SHA アルゴリズム LS ハッシュ ディフィー・ヘルマン鍵交換 線形計画法 正直、…

ゴールが見えると手を抜いてしまう、人間だもの Solved By kkktym Topcoder: 0 Codeforces: 239 AtCoder: 1498 AOJ: 62 yukicoder: 10 library-checker: 0 Sum: 1809 ARC080E - Young Maids 辞書順最小なので先頭から貪欲に小さい要素をとっていけば良い。末尾から足すことになるのでとることができる要素と取り出し方には制限がつく。先頭に持ってこれるのは偶数 index (0-index) のものだけで、2番目は奇数 index のもの、かつ先頭のものより後ろにあるものだけである。これ…

HAL研究所プログラミングコンテスト2020 に参加した。課題や競プロなどによって、3 日ほどしかできなかった。 実装 地形の境界に注目した。境界で、かつ格子点上の点と、巻物、最初のウサギの位置の点すべてを頂点とし、そのなかの任意の 2 つの頂点間の距離を、地形に応じた距離(砂地なら 10/3 倍、池なら 10 倍にする)として計算する。これは、通過するマスを 1 つずつ見ていって計算した。 その後、巻物の点、最初のウサギの位置の点からダイクストラを回し、巻物の点と最初のウサギの位置の点を頂点とする完全グラフを作成する。2 点の距離は、ダイクストラによって得られたパスに沿って実際にウサギが飛ん…

Q.心を持ったパンってな〜んだ？ Solved By kkktym Topcoder: 0 Codeforces: 233 AtCoder: 1479 AOJ: 62 yukicoder: 28->30 library-checker: 0 Sum: 1784->1786 yukicoder contest 277 ゆるっと参加した。AB 2完。Cわからず。 A. No.1329 Square Sqsq (桁数+1)/2 B. No.1330 Multiply or Divide これすき。xを頂点とするダイクストラっぽい感じでやった。Pで割り切れる回数が同じならデカい方がつよいのでそれ以外は…

タイトルの通り、4分野解き終えた！ これを持って、とりあえず精選100問を一周した形となったので、今後はスキップした問題(75問目)や要復習問題(たくさん)を順次見直していきたい。 それから、先日のABCで解けなかった問題があったが、解説を見たらこの100問で学んだ知識で解けるはずの問題だった。(悔しい…！) 実践への応用力がまだまだ身についていないことのあらわれだと思うので、今年はABCやARCの過去問をたくさん解いて、本番で使えるスキルを身につけていきたい。 これからもがんばります！ 大分類 小分類 問題数 全探索 全列挙 4 済 工夫して通り数を減らす全列挙 5 済 ビット全探索 5 済…

タイトルにある4分野を一応解き終えた。 (嘘。正確には、解説を見てもACできなかった75問目をスキップしたので、解き終えていない…) これらの4分野は、私にとってまったく難易度が違って感じられた。 最も難しかったのは逆元で、ACを出せた問題についても理解度が極端に浅い。何も見ずにもう一度解いても、絶対にACできないと思う。(しんどい…) 素数判定やべき乗の高速化は、元の知識が皆無だったのでいろいろなページを読んで学習した。特に素数判定法は、判定対象のNに対して約数を√Nまで数え上げる方法とエラトステネスの篩を使う方法があると知った。一方のべき乗計算は二分累乗法を使うと計算量が抑えられる。この2…

LMOが解けず。Lは解説を見てAC、MOは終了後に解法を見つけてAC。実装力のなさを感じた。 A - ○✕ゲーム/OX Game 珍しく実装が軽くてよい。答えを"draw"で初期化しておいて、3連続を見つけたらその文字に上書き（5マスなのでox両方が3つ並んでいることはない）。 B - 上書き/Overwrite 愚直にやるだけだが、削除は（計算量を無視しても）やりづらいので別のstringを用意してそこへcでない文字を追加していった。（解説を見て）std::remove知らなかった。この問題専用関数か？ C - 三十六進法/Hexatridecimal いつもの。push_backしていって…

テメエの身の程をわきまえろ！とカーペンターは怒り狂った （評価 ７２点） 「要塞警察」というＢ級映画の金字塔的傑作を放ち、批評家、映画野郎から俄然、注目を浴びたジョン・カーペンターが、低予算で高収益が狙えるホラーというジャンルにベクトルを振るのは、至極当然のことだった。そこでカーペンターは「ハロウィン」という金脈を掘り当てる。今なお、不滅のキャラクター、ブギー・マンを見事にブランド化させたカーペンターが、いよいよ手にしたのは予算だった。 とはいえ本作「ニューヨーク１９９７」の予算は、大作映画とは到底、言えない中規模にも満たないもの。それでもカーペンターにとってはやっと掴んだ勲章のような勝利の証…

最短経路問題と最小全域木問題を解き終えた！ この前のDP分野と比べると相当簡単に感じた。特にワーシャルフロイド法は、分かりやすくて本当に好きだな… 調子がいいので、このペースのまま100問完走したい。(たぶん無理) 1問だけヒントをガン見しちゃった問題(67問目)があったので、忘れず復習しようと思う。 大分類 小分類 問題数 全探索 全列挙 4 済 工夫して通り数を減らす全列挙 5 済 ビット全探索 5 済 順列全探索 3 済 探索 二分探索 6 済 深さ優先探索 4 済 幅優先探索 6 済 動的計画法 ナップザックDP 5 済 ナップザックDPまたはその亜種 7 済 区間DP 3 済 bit…