atcoder
atcoder.jp 二通りの方法で通した。 優先度付キュー Binary indexed tree + 二分探索 始め思いついたのは2つ目の方法。 これには座標圧縮なども必要になり大変だった。 1つ目の方法は公式pdfを参考にしたもの。 共通して必要な考察 |x-ai| + bi を順に足して…
全完できて黄色パフォでした!嬉しい! 全方位木をあまり理解していなかったためFが遅くなってしまいましたが、方針自体はすぐたったのでまだ上を目指せそうです。 E Red and Green Apples 貪欲で解けます。 時間がかかった人も割といたようですが早く解けま…
青diff下位に設定されていて比較的昔のコンテストだったので解けるだろうと思ったが苦戦した。 結局わからず解説AC。典型ということだがこのdiffだと初見でも解けた人が多そう。 公式解説pdfがわかりやすい。 しかし、「vからS−{v}へ向かう有向辺がない」を…
ABCDを解きました。水色パフォでした。今週はコドフォも含めて全体的にいつもより順位が低めでした。練習の仕方に問題があるのかも。 D String Formation 後ろから解きました。Dequeと使うのが簡単なようですが私は最終的な文字列の長さ分リストを用意してお…
ABCDEを解きました。青パフォ上位なのは嬉しいですがF解けなかったのが悔しい。 D Bouquet combination(n, a)のnが大きくaは小さいのでn(n-1)...(n-a+1)とa!を求めないと計算できないです。 E Payment はじめ各部屋の人数がk以下の個数を数えようとして時間…
ABCEを解きました。今回難しかったようでこれでも青パフォでした。 D Pairs 割とABC149EのHandshakeに近いです。今回はゼロとマイナスの要素があるので複雑度が大きくなっています。 本番ではゼロを分けないといけないことに気づかず解けませんでした。終了…
また、久しぶりにcodeforcesに出てみました。4つ解けたけど自信ないです。 終わってみると簡単だったような気もしてくるから不思議です。Dで結構たくさん迷ったんですが。 C Obtain The String なんか簡単そうなのに時間がかかりました。 s, tは後ろからみま…
A~Eまで解きました。水色パフォ。良いパフォーマンスを出すのが辛くなってきている気がします。 一年前でこれくらいの難易度を解ければ余裕で青パフォ以上あったような、、、 それとA~Cも遅いですね。同レート帯の人見てると倍くらい早い人が多い。 D MazeMa…
新ABCで初めてDが解けなかったです。出た回数がそもそもそんなに多くないですが... D SemiCommonMultiple タイトルの通り公倍数の半分が回答になりそうで、証明が面倒なのでsubmit → WA 手元で計算すると2で割れる回数が全て同じでないとダメという条件が得…
AtCoder 令和ABC(?)F問題も全部解いたのでコメントを残す。とても本番中には解けなさそうな問題が増えてきた。 コメントはだいぶ手抜きだが後で拡充したい。 歯が立たないということはなくじっくり考えれば解ける問題も多い。 解法自体はすぐわかることもま…
令和ABC(?)E問題を全部解いた。解いた順番は適当だがコメントは開催順になっている。 Eレベルはセグ木・グラフアルゴリズム・文字列アルゴリズムなど知識を求められるものが多い印象。蟻本などは未履修なので辛かった。勉強してライブラリを作っていきたい。…
令和ABC(?)D問題を全部解いた。解いた順番は適当だがコメントは開催順になっている。 Dレベルだと解法がわかるのに5分以上かかったのはあまりなかった気がする。 例外処理・実装が主な詰まりポイント。実装で苦手なのは二分探索や尺取り法や優先度つきキュー…
atcoder.jp どの行、列も1*2の畳の数が同じになるようなものを探さないといけない。 解説通りN=4,5,6,7で数が3になるものを探せば、N>=4に対して構成可能だが、N=7を見つけるのが難しかった。 以下はN=7の例 .bc.a.. .bc.a.. ..aabba aab...a x.baa.. x..b.…
atcoder.jp ABC148に出た。全完だったが簡単だったようでパフォーマンスは大したことなかった。 木の上で高橋くん(以下T)と青木くん(以下A)が鬼ごっこする問題、高橋くんから順に互いに1ずつ移動する。Aが鬼。最も長く移動した場合のAの移動距離を求める。 …
ABC-Fは自分にとっては難しいことが多いのですがこれは簡単でした。しかし、実装に苦労したため本番時間内では無理そうです。 atcoder.jp ググったら解法記事がたくさんあった上にはるかにわかりやすいので解法は省略 AtCoder ABC 130 F - Minimum Bounding …
atcoder.jp 気楽に書くことに決めたので連続更新、競技プログラミング以外をやるべき状況だが、、、 今回は旧ABCのC問題。Cの中では最難関級っぽいのでどうせ実装系だろうと思いコーディングの練習にしようと思って解いた。 長さA,B,Cの竹を3~8本の竹を組み…
k=A-Bを固定すれば大丈夫そうだったのですが、なぜかサンプルが合わず愚直解を書いてみる。一応出すも当然TLE。 N, = map(int, input().split()) xs = list(map(int, input().split())) r = 0 for a in range(1, N-1): for b in range(1, N-2): if a <= b: c…
最近、AtCoderをやっているのですが解いた感想などを置く場所としてこのブログを再利用することにしました。どうせ複数のブログなどを持っても管理できないし。 ABC143-Fを解いていたのですが詰まってしまって苦労したのですが、解説とも違った解き方だった…