勉強した。snuke.hatenablog.com ikatakos.com 難しいしよく理解できてない気がするので考えたことのメモ。上の記事のS→Tのフロー、s→Tのフロー、S→tのフローをできるだけ流した後のことを考えるとイメージがついた。 この状態で超頂点S,Tを作る逆の処理をす…
最近、コドフォに復帰しつつある。 エデュフォはpython のメモリエラーに苦しめられて散々だった。 A:全部1の時以外できる。B:文章が長いC:ソートしてan-1-anのgcd、an+1=an-k*gcdでできるだけ大きく取る。E: トライ木でやるとメモリエラーに。versionをpypy…
久々の更新です。Codeforces Round #669 (div2) に参加しました。 codeforces.com A~Cの3完でレートは少し下がりました。Eがギリギリ間に合わなかった（1分遅れ...）のが悔しいです... A Ahahahahahahahaha 1と0のみからなるリスト（リスト長は偶数）からn/2…
WikiExtractor Wikipediaが持つ大規模なテキスト情報を利用すれば様々なサービスやツールを開発できると思われますが、WikiExtractorはWikipediaのテキスト部分だけを抽出することができるツールです。 以下から最新版を入手できます。 github.com 下準備 : …
atcoder.jp 二通りの方法で通した。 優先度付キュー Binary indexed tree + 二分探索 始め思いついたのは2つ目の方法。 これには座標圧縮なども必要になり大変だった。 1つ目の方法は公式pdfを参考にしたもの。 共通して必要な考察 |x-ai| + bi を順に足して…
全完できて黄色パフォでした！嬉しい！ 全方位木をあまり理解していなかったためFが遅くなってしまいましたが、方針自体はすぐたったのでまだ上を目指せそうです。 E Red and Green Apples 貪欲で解けます。 時間がかかった人も割といたようですが早く解けま…
青diff下位に設定されていて比較的昔のコンテストだったので解けるだろうと思ったが苦戦した。 結局わからず解説AC。典型ということだがこのdiffだと初見でも解けた人が多そう。 公式解説pdfがわかりやすい。 しかし、「vからS−{v}へ向かう有向辺がない」を…
「† 注意力 † コンテスト」バチャの問題 Problem - B - Codeforces n, a, bが与えられるa'>=a, b'>=b, a'b' >= 6nを満たす最小のa'b'とそのときにa', b'を求める問題 まず、a<bとすると、明らかにa'<b'とできる。(aで小さい方、bで大きい方を作ってそれぞれa', b'とする) この後、a<b、a'<b'とする。 ai2< 6nとなる範囲でaiを探索する。aiに対して、bi=Max(b, ceil(6n/ai))としてあげればaiを固定したときに6n以上のaibiの最小値になる。 ai2>=6nのとき、明らかにaibi>=6nなの…</bとすると、明らかにa'<b'とできる。(aで小さい方、bで大きい方を作ってそれぞれa',>
Dまで4完でした。Eは解法もあっていたのですがつまらないバグを残してしまいダメでした（泣）。 A Two Regular Polygons N%Mが0かどうか。 B Bogosort リストを並び替えてi-aiがすべて異なるようにすればいいです。 aiを降順に並べればi-aiは狭義単調増加に…
ABCDを解きました。水色パフォでした。今週はコドフォも含めて全体的にいつもより順位が低めでした。練習の仕方に問題があるのかも。 D String Formation 後ろから解きました。Dequeと使うのが簡単なようですが私は最終的な文字列の長さ分リストを用意してお…
解説ACした 絶対思いつかない天才解法だったのでメモ ngtkana.hatenablog.com これ通りに書いただけ。丁寧な説明なのに結構実装にも手間取った。 以下は実装。O(N3)の計算量。6.4*107でpypyでは厳しいのでは？と思ったが余裕で通った。 こういうの本番では不…
1日に２つあると大変ですね。疲れました。 # 621 (div2)はA, B, C1の３つ解けたつもりがC1がシステムテストで落ちました。 一行間違えて消していて直すと通りました（泣） ちゃんと確認しましょう！ #622 (div2)はA, B, C, Dまで解けたつもりですが現在シス…
ABCDEを解きました。青パフォ上位なのは嬉しいですがF解けなかったのが悔しい。 D Bouquet combination(n, a)のnが大きくaは小さいのでn(n-1)...(n-a+1)とa!を求めないと計算できないです。 E Payment はじめ各部屋の人数がk以下の個数を数えようとして時間…
A, B, Dの３つ解けました。遅かったのでレートは下がりました。(1752 -> 1716) A Cow and Haybales 苦手系です。割算を頑張りましょう。 こういう割算の算数系はそれほど難しくない割に時間がかかって本当に苦手です。 B Cow and Friend ちょうどのものがあ…
ABCEを解きました。今回難しかったようでこれでも青パフォでした。 D Pairs 割とABC149EのHandshakeに近いです。今回はゼロとマイナスの要素があるので複雑度が大きくなっています。 本番ではゼロを分けないといけないことに気づかず解けませんでした。終了…
以下にわかりやすい記事があった。うまく理解できず苦戦した。今もわかっていないが今後のために行間として考えたことをメモ competitive12.blogspot.com GCD(Ai, Aj) = xであるような全てのAi, AjについてAi * Aj の和を求めることができれば解が求まること…
A, B, Cの3完でしたが、ムーブが最悪だった感じでちょっと悲しかったです。 C通った後に速度が不安になってC#で書き直して20分消費した後、Dが数分間に合わなかったので... が、何はともあれ青色になれました。次は紫目指します。 A Even But Not Even ２つ…
AtCoder のEducational DP contest-Z Frogを 解いていて必要だったので整備しました。 自分の実装 : Submission #9866424 - Educational DP Contest CHTについてはググればたくさんの記事がある。以下の２つの関数がある。 insert 関数 : ax+bを追加する。単…
先日のEducational Codeforces Contest でE問題が遅延セグメントツリーを利用する必要があったのですがpypyでは通らなかったのでC#で書き直してACを得ました。 せっかくなので実装を残しておきます。 非再帰版の遅延評価セグメント木の実装メモ - 日々ｄｒｄ…
また、久しぶりにcodeforcesに出てみました。4つ解けたけど自信ないです。 終わってみると簡単だったような気もしてくるから不思議です。Dで結構たくさん迷ったんですが。 C Obtain The String なんか簡単そうなのに時間がかかりました。 s, tは後ろからみま…
全然わからなかったし、今もわかっていない（主に遅延セグ木）ので復習用に簡単にメモ atcoder.jp まず、方針からわからないけどググれば解りやすい解説がたくさん出てくる。 以下が解りやすかった。 Educational DP Contest : W - Intervals - kmjp's blog …
atcoder.jp 最近のABCに似た問題があったためにすぐ解けて嬉しかったのでメモ FFFTFTFFみたいなのが与えられて、Fは直進、Tは90度回転を表す。回転は左右どちらでもいい。初めは(1,0)方向に進んでいる。また、座標（X,Y）も同時に与えられるのでその地点に到…
やってしまった！Eから解いてWAが出たので茶パフォでした！ しかし、Eの方針に間違いはなくコンテスト後通せました！ レートは大きく下がりましたが変な解き方をしているのが悪いですね。 よく後ろから解くのですが、これは後ろの問題にどうしても惹かれてし…
A~Eまで解きました。水色パフォ。良いパフォーマンスを出すのが辛くなってきている気がします。 一年前でこれくらいの難易度を解ければ余裕で青パフォ以上あったような、、、 それとA~Cも遅いですね。同レート帯の人見てると倍くらい早い人が多い。 D MazeMa…
新ABCで初めてDが解けなかったです。出た回数がそもそもそんなに多くないですが... D SemiCommonMultiple タイトルの通り公倍数の半分が回答になりそうで、証明が面倒なのでsubmit → WA 手元で計算すると2で割れる回数が全て同じでないとダメという条件が得…
よくWEBから情報抽出するのですがHTMLをパースする時にはpython のBeautifulsoupライブラリ(BS4)を利用しています。 BS4は公式の解説がわかりやすいですし、有名ライブラリなので日本語記事もたくさん見つかります。 www.crummy.com qiita.com BS4ではfind('…
年末年始休みだったのでcodeforcesに手を出してみましたがBでMLE,TLEを出し続け撃沈しました。pythonのような遅い言語には厳しいという噂は聞いていましたが本当のようです。（あとnumpy使えないのも提出してから知った...） https://codeforces.com/contest…
AtCoder 令和ABC(?)F問題も全部解いたのでコメントを残す。とても本番中には解けなさそうな問題が増えてきた。 コメントはだいぶ手抜きだが後で拡充したい。 歯が立たないということはなくじっくり考えれば解ける問題も多い。 解法自体はすぐわかることもま…
令和ABC(?)E問題を全部解いた。解いた順番は適当だがコメントは開催順になっている。 Eレベルはセグ木・グラフアルゴリズム・文字列アルゴリズムなど知識を求められるものが多い印象。蟻本などは未履修なので辛かった。勉強してライブラリを作っていきたい。…
令和ABC(?)D問題を全部解いた。解いた順番は適当だがコメントは開催順になっている。 Dレベルだと解法がわかるのに5分以上かかったのはあまりなかった気がする。 例外処理・実装が主な詰まりポイント。実装で苦手なのは二分探索や尺取り法や優先度つきキュー…
