Cがぱっと見難しそうでDがいけそうだったのでずっとDを解いていた．結局Dが解けずに2完．しかし，コンテスト終了後，＋3WAの＋20分くらいでCが解けたのでDにこだわらずCを解いておけば良かった……．Dは未知のアルゴリズムを理解する必要があったので後日しっ…

hirohirohirohiros.hatenablog.com 概要 アルゴリズムの概要 併合，判定 rank pythonコード 概要 Union Findはグループ分けを管理するデータ構造です．要素aと要素bが同じグループに属しているかそうでないか判別することが出来ます． また，複数のグループ…

バーチャルで参加しました(221位)．Union Findはいつかちゃんと実装しないとなと思っていたので今回これを使う問題が出てきて良かったです． A - Water Pressure【AC】 言われたことをそのまま実装するだけです． D = int(input()) print(D/100) B - Electio…

土日連続でABCが開催された19，20日．あいにくこの二日間ちょうどインターンと重なってしまったのでRated参加できずバーチャルで参加しました．(239:87位, 240:82位) A - Horizon【AC】 そのまま実装します． x = int(input()) print((x*(12800000+x))**(0.5…

バーチャルで参加しました（196位）．Cに手こずりましたが，滅多に使わない隣接行列を使うと簡単だと気付いたらすぐに解けました． A - QQ solver【AC】 pythonは文字列と数字の変換が簡単で助かる． s = input() print(int(s[0])*int(s[2])) B - Caesar Cip…

発端 問題内容 速さ比べ まとめ 発端 Atcoder235では実装したアルゴリズムが解説コードとほぼ同じなのに，TLEになってしまう事態が起きました．解説コードは約100msだったので20倍以上速度に差があることになります．使ったアルゴリズムは同じなので計算量は…

バーチャルで参加しました．Dが結局解説を見ないと解けませんでしたがアルゴリズムの根幹は時間内に出来ていたので成長しているとします． A - Rotate【AC】 Pythonは文字列の数字とint型の数字を簡単に変換出来るのですぐ実装可能です． a = input() print(…

競プロでは値を無限大（とにかく大きな値）にしておいて，更新するときに書き換えるという処理をすることが結構あります． いつだったかのAtcoder ABCで無限大の書き方を変えるだけでTLEがACになったのが衝撃的だったので記事に纏めます． 始めに float("inf…

バーチャルで参加しました． A - chukodai【AC】 文字列をlist関数に入れると一文字ずつ要素になったリストが返ってきます．また，a,b = b,aとすると簡単に値を入れ替えることができます． S = list(input()) a, b = map(int, input().split()) S[a-1], S[b-…

hirohirohirohiros.hatenablog.com 概要 アルゴリズムの内容 pythonコード 概要 ベルマンフォード法はダイクストラ法と同じ最短路を求めるアルゴリズムです．ダイクストラ法と違い，負辺が存在しても正しく動きます．また，負の閉路を検出することも出来ます…

Bがぱっと見解けなさそうだったので先にCDを取り組んだ．Cは30分で解けたがDが解けそうで解けずに結局2完となった．BCD全体的に難しい……難しくない……？ A - Exponential or Quadratic【AC】 Pythonならそのまま書けばいい． N = int(input()) if 2**N > N**2…

hirohirohirohiros.hatenablog.com 概要 アルゴリズムの内容 pythonコード 概要 ダイクストラ法はグラフの最短路を求めるアルゴリズムです．グラフの2頂点が与えられたとき，その2頂点を始点終点としたときのルートで最もコストが小さいものを最短路と言いま…

概要 一覧 ダイクストラ法 ベルマンフォード法 Union Find 素因数分解，エラトステネスの篩 トポロジカルソート docstring 概要 名前の付いたアルゴリズムについて，毎回その場で調べて実装を繰り返していましたが，さすがに面倒くさい，時間が掛かって不利…

概要 導入 機能 概要 昔書いた関数を見返してこれ何をやってるんだ？となることが私はよくあります……それを無くす解決策としてDocstirngなるものを知り，見よう見まねで書いていたんですが面倒くさい……今回VSCodeでDocstirngのテンプレートを自動で補完して…