ダイクストラ

■51:C - 掛け算 ある程度まで揃えてから、 全てに同じ数を掛ける■52:C - 高橋くんと不思議な道★★★ 難しかった。 枝刈りダイクストラ。 O(N^2)だとTLEするので、なにかの工夫が必要 まず特定の頂点に到達するまでにタイプBの辺を最低でも何回使う必要があるかを調べる。 すると、それをneedBとでも置くと needB[v](needB[v] + 1 )/2 + N 以下にコストが収まることがわかる。 なので実際に使うタイプBの辺の回数は needB + 150程度もあれば十分だとわかる。(150は√2 * N＋余裕) 以上の情報を持ってダイクストラを行う。■53:C - 魔法使…

https://atcoder.jp/contests/past202010-open/tasks/past202010_j 前提知識 ダイクストラ 解説 https://atcoder.jp/contests/past202010-open/submissions/21472629 ダイクストラをするが、特殊なグラフ形成をする必要がある。 ダイクストラをよく知らずにこの問題を解くのは難しいので、先にダイクストラをマスターすることをお勧めする。 ワープが無ければ 普通にダイクストラするだけ。 これでまずはグラフを作る。 ワープをどうするか 真面目にワープの辺を貼ると、タイプAの全ての頂点からタ…

マスタリングTCP/IP 入門編（第6版） Kindle版を購入した kindle価格、他の電子書籍プラットフォームの価格より400円ほど安くね？ マスタリングTCP/IPはネットワークの定番書 勉強したくなったので購入した 1週間ぐらいで一通り読みたい ルーティングプロトコルOSPFがダイクストラ法を用いているのが競プロ関係ある 本は読み捨てる本でなければ電子書籍でいいなというお気持ちになった 物理本は邪魔 まだ途中だが分厚さに反して説明はわかりやすい RFCの話とかいる？

終了ギリギリで5完。滑り込めたのは嬉しかった。1482パフォってしょっぱいね。まあでも水復帰したからOK。 A問題 Rotate うし B問題 Visibility びーと C問題 ORXOR 一瞬マジでびっくりしたけどで安堵。ちょっと実装にもたついたがWAなしで通ったのでよし。 D問題 Opposite 本当にカス。どうすればいいのか全然分からず一旦Eに行った。その後重心から回転させればいいんじゃね？ということに気づき、重心を原点に移して回転させて戻すコードを適当にぴゃぴゃっと書いたら20秒前に通った。嬉しいよりも先に驚きが来た。嬉しいです。 E問題 Traveler 一瞬貪欲に見えて困惑し…

はじめに 「【転職エントリ】Googleに入社します｜Lillian｜note」という、医師から未経験で Google のソフトウェアエンジニアになった記事があります。 note.com 私は、この記事に出てくる「とある元 Google のソフトウェアエンジニア」で、面接の対策を立てました。 記事が出た当初から大反響で、私もそれなりの反応を見まして、いろいろと誤解されているなあ、と思う一方、アドバイザーはあくまでもアドバイザーだから、アドバイザーとして知りえた情報については、口をつぐむべきだと思っていました。 ただ、あまりにも誤解されており、悪影響が大きく、犠牲者も多くなってきたと思ったので、…

二分ヒープを書きました 二分ヒープ is 何 平たく言えば std::priority_queue みたいなやつ 次の操作がいい感じの計算量でできる top() 最大値を取得する $O(1)$ pop() 最大値を削除する $O(\log N)$ push(value) 値を追加する $O(\log N)$ 構造 二分木を持つ．各ノード（葉以外も）が値を持っていて，セグ木と同じ要領で 1-indexed である． ヒープは，次の条件をつねに満たす． あるノードの親のもつ値は，子のもつ値以上である． これを満たすようにクエリに対応する．なお，ノードの追加自体は，ヒープを持っている可変長配列に p…

自己紹介 精進 コンテスト 勉強していたこと 紙に考察を書くこと レーティングを気にすること マラソンの影響 最後に AtCoder Beginner Contest 197（Sponsored by Panasonic）にて、AtCoder青色になりました。 競技プログラミング界隈の風習にならい、色変記事を書きます。 naga on Twitter: "初参加から2年半、やっと青コーダーになりました！！！！！！！！… " 水色の記事はこちら。 coonevo.hatenablog.com 自己紹介 21卒の大学院生で、来る4月からエンジニア職として働き始めます。専攻は生物で、研究で必要になり…

今週のタイムライン エネルギーを与えた出来事（幸せになった・安心した） 仲間の送別会をした（火曜日） MaxSATの勉強をした（火曜日） 経路探索アルゴリズムに興味が出た（木曜日） Search Inside Yourselfを読み始めた（木曜日） スクラムイベントの順番を変えてみた（木曜日） エネルギーを奪った出来事（悲しくなった・不幸になったなど） 低気圧がすごかった（日曜日） 感情によって自分の行動が変わってしまっていること（水曜日） 戸惑った出来事や疑問に思った出来事 Doneにならない前提でプランニング時にアイテムを取ることはどうなんだろうか？（木曜日） 話したいこと 感情によって自…

要約 "Hello, World!" から広義1年で AtCoder 橙 / IOI 日本代表 になるまでの記録 橙コーダーと、申しますyuto1115さんのAtCoder Regular Contest 114での成績：18位パフォーマンス：3133相当レーティング：2387→2488 (+101) :)Highestを更新し、三段になりました！#AtCoder #ARC114 pic.twitter.com/DyU8WQDXdL— yuto (@yuto1115_cp) 2021年3月14日 日本代表になりました— yuto (@yuto1115_cp) 2021年3月23日 JOI 春合…

JOI 2020/2021の春合宿(合宿ではない)に参加してきました。これで最後です。 競技は結構うまくいったと思っています。以下参加記です。 競技前日まで 🦊のマスコットを買った、かわいい。後輩からもらったえびちゃんの上に乗せると更にかわいい。 2日前くらいに原因不明の興奮で4時まで眠れなかったりして大変でした。多分春合宿とは関係ないけど特に心当たりもないので謎。 前日はABCの準備をしてました。最後にNTTとかLCTの実装とかの覚えなきゃいけないものを見直して準備完了。 この夜はよく眠れた Day 1 行きの電車はJupiterとか春よ来いとか聞いてました。いつ聞いてもいい曲。 参加者の半…

JOI '21 春合宿に参加しました。 ~Day -1 (3/18) 2/27~3/18 にかけて JOI '20 春合宿のバチャを走る。Day 3 までかなりひどかったが、Day 4 の Capital City と Treatment Project がどちらも得意な問題で、満点。Legendary Dango Maker でも必死に点数を稼ぎ、なんとか代表ボーダーを超える。 JOI '20 春合宿 バチャBuilding 4: 100Hamburg Steak: 9Sweeping: 22Chameleon's Love: 4Making Friends on Joitter is Fu…