abc038.contest.atcoder.jp 当初の方針(WA) ふつうにDPしたらO(N^2)になりそう。きっとO(N log N)解法。ソートして大きいやつから取っていけば良さそう → WASubmission #923373 - AtCoder Beginner Contest 038 | AtCoder 3 1 9999 1 1 2 2 のケースで落ち…
abc038.contest.atcoder.jp A 最後の文字だけみて判定Submission #923339 - AtCoder Beginner Contest 038 | AtCoder B 全探索。頭が回らなくててこずるSubmission #923340 - AtCoder Beginner Contest 038 | AtCoder C ひとつずつ考えないで、増加した部分…
The Secret Number | Aizu Online Judge 解き方 探索をして解く。ただ探索すると考えると深さ優先探索になるが、それだとTLEになってしまう。 あるマスに着目して、そのマスに到着する値の一番大きい経路のものを保存していくと考えると、 W \times H で解け…
はじめに ACM-ICPC 2年連続国内予選突破を目指して朝練を始めました。Virtual Arena: Room 3044 寝坊 IntelliJ Students License更新忘れ A問題なのに解けない の3コンボ。泣きそう。思えば長いこと競プロしてない...。楽しいのになあ。 Unit Fraction Parti…
C : Sibling Rivalry 本戦時にぼくが戦犯してしまった問題。復習の時です。 本戦時 スタート地点から、幅優先探索でa, b, cそれぞれの手数に対して移動先を木に追加して行って、単体ではORを、全体(abc)ではANDを取ろうと考える。重すぎ。幅優先探索を2重…
第26回高専プロコンでは蟻コロニー最適化(ACO)を利用しました。 本番でのスコアはあまり揮いませんでしたが、 みなさんが使うといいスコアに仕上げてくれるものと考えています!arukuka.hatenablog.com こっちは参加記。 前置き ACOはインターネッツで調べるとよく…
豊橋技術科学大学チームとして、高専プロコン競技部門に参加してきました。 結果は準決勝第3試合2問目敗退。無念。自分はチーム代表を務めさせていただきました。チームメンバーは、 @foldori @hysy__ @shadow_jp また、引率として先輩方 @k3_kaimu @tanutar…
AOJ 2151 Brave Princess Revisited 解法 宿と予算が少ない! ということで動的計画法で解こうとしました (トポロジカルソートできていないのでDPじゃない)。 設計メモ dp[現在地][残りの予算] : 最小化された盗賊らの人数 d[出発地][到着地] = 出発地と到…
小生、D言語力足りないのでこのような会に参加すること自体びくびくしていたし、ましてや記事を書こうなぞとおこがましい限りですが、「D言語力足りないマン」の視点から記事を書かせていただきます。 間違いや、いただけない箇所がございましたらお知らせい…
AOJ 0244 Hot Spring Trip 解法 ダイクストラ法とメモ化探索を利用しました。 連続した2区間を保存しておき、メモ化探索しながらその地点から切符で答えを更新できるか伺います。 ゴール地点 nからダイクストラ法を使うことで、切符を利用して着いた地点から…
D言語の初歩的な機能のうちの一つ、言語バインディングを確認することが目的です。 題材として個人的に気になっていたAquesTalk のラッパを行います。 はじめに D言語はCのAPIが呼び出しやすいように設計されているそうです(Cとのインターフェイス)。 試しに…
AOJ 0245 Time Sale 解法 動的計画法で解きました。 dp[x][y][state] = state の状態で(x, y) への最短コスト state はビットで管理して、商品に隣接するセルをIterator で回して幅優先探索をかけ、min をもって更新していきます。state にたどりつけたらans…