ながめも

競技プログラミングについて

AtCoder

AtCoder Beginner Contest 218 ABC218 参加記

jjjjjjjtgpptmjjさんのAtCoder Beginner Contest 218での成績:2007位パフォーマンス:1136相当レーティング:1428→1402 (-26) :(#AtCoder #ABC218 https://t.co/gykafsug4z :(— naga (@long_ng_cp) September 11, 2021 A - Weather Forecast 解説 実装 B - …

マラソンマッチで気をつけるべきこと

競技プログラミングのマラソンマッチ で気をつけるべきこと。

AtCoder Heuristic Contest 001 AHC001に参加しました

AHC001に参加しました。 結果は、システムテスト前最終118位、489億6千万点でした。簡単にですが、採用したアルゴリズムに関して記します。 AHC001お疲れ様でした!!!上から順に貪欲に面積を割り当てた初期解から山登りをしました。長方形を移動するほかに…

HHKB プログラミングコンテスト 2020 D - Squares

D - Squares 問題へのリンク 解説 X(答え) 重ならないという現象の数え上げは難しいので、重なる(X1)を数えて全体から引く X = X0 - X1 X0 = (N-A+1)2 * (N-B+1)2 X1(重なる) 重なるという現象は、AとBの満たす区間がxでもyでも重なるときで対称性から、 xで…

パナソニックプログラミングコンテスト(AtCoder Beginner Contest 186)E - Throne

E - Throne 拡張ユークリッドの互除法による逆元計算 NとKが互いに素のとき NとKが互いに素でないとき 実装 中国剰余定理 実装 E - Throne 問題へのリンク を満たす最小の整数を求めよ。 拡張ユークリッドの互除法による逆元計算 まず、与式をと変形すること…

AtCoder Regular Contest 106 ARC 106 参加記

A - 106 解説 実装 B - Values 解説 実装 C - Solutions 解説 実装 A - 106 問題へのリンク 解説 オーバーフローしそうなのでpythonで。 実装 N = int(input()) for a in range(60): if a == 0: continue rem = N - pow(3, a) if rem < 0: break for b in ra…

AtCoder HHKB プログラミングコンテスト2020 参加記

ABCE青パフォでした。Dが難しかったですね・・・。 jjjjjjjtgpptmjjさんのHHKB プログラミングコンテスト 2020での成績:571位パフォーマンス:1728相当レーティング:1443→1475 (+32) :)#AtCoder #HHKBプログラミングコンテスト2020 https://t.co/hTuwuCdLL…

AtCoder Library Beginner Contest ABL 参加記

ABC3完でした。Dは冷静になりたかった。。。勉強不足です。 A - Repeat ACL 解説 実装 B - Integer Preference 解説 実装 C - Connect Cities 解説 実装 D - Flat Subsequence 解説 実装 A - Repeat ACL 問題へのリンク 解説 for文を使います。 実装 int mai…

AtCoder Beginner Contest 179 ABC179 参加記

A - Plural Form 解説 実装 B - Go to Jail 解説 実装 C - A x B + C 解説 実装 D - Leaping Tak 解説 実装 E - Sequence Sum 解説 実装 F - Simplified Reversi A - Plural Form 問題へのリンク 解説 末尾を確認します。 実装 int main() { string S; cin >…

ACL Contest 1 参加記

2完青パフォでした。ACLはほとんど対策できてなかったのですが、自分のレート帯なら関係ないだろうと思って考察を頑張りました。Bでコンテスト前にたまたま目にした拡張ユークリッドの互除法が使える問題が出て、運がよかったです。 jjjjjjjtgpptmjjさんのAC…

AtCoder Beginner Contest 178 ABC178 参加記

5完で水パフォでした。青パフォstreakが切れて悲しいですね。 jjjjjjjtgpptmjjさんのAtCoder Beginner Contest 178での成績:864位パフォーマンス:1597相当レーティング:1412→1432 (+20) :)Highestを更新しました!#AtCoder #ABC178 https://t.co/JlM3Zncq…

AtCoder Library 環境構築(macOS & VSCode編)

先日AC Libraryの導入が発表されましたが、皆様いかがお過ごしでしょうか。備忘録として私が環境構築で行ったことを記しておこうと思います。 注意 心配な方は公式ドキュメントに目を通してから環境構築を行ってください。 環境 macOS Catalina Version 10.1…

AtCoder Beginner Contest 177 ABC177 参加記

5完2ペナで青パフォでした。初の青パフォstreak2で嬉しいです。 jjjjjjjtgpptmjjさんのAtCoder Beginner Contest 177での成績:605位パフォーマンス:1732相当レーティング:1371→1412 (+41) :)Highestを更新し、3 級になりました!#AtCoder #ABC177 https:/…

AtCoder Beginner Contest 176 ABC176 参加記

D - Wizard in Maze 解説 実装 E - Bomber 解説 実装 列の最大をとる range max queryのセグ木 F - Brave CHAIN 50分5完で青パフォでした。 そういえば競プロを始めてから2年が経っていました。 D - Wizard in Maze 問題へのリンク 解説 見た瞬間にグリッド…

AtCoder Beginner Contest ABC025 C - 双子と○×ゲーム

C - 双子と○×ゲーム 解説 実装 C - 双子と○×ゲーム 問題へのリンク 解説 まず、置く順番は通りありますが、すべて試していいだろうとわかります。順列の列挙は、簡単に行う場合はnext_permutationを使いますが、今回は順列の生成とともにゲーム木を構成した…

AtCoder Grand Contest AGC005 B - Minimum Sum

B - Minimum Sum 解説 実装 B - Minimum Sum 問題へのリンク 解説 区間がたくさん与えられるので、その中のある値の和を求めよという問題は多くありますが、基本的に区間をすべて列挙して解くことはできません。今回も例によってそのパターンで、ある値が、…

AtCoder Beginner Contest 174 ABC174 参加記

Eまでノーペナ30分だったのにF既出を検索できずにしょっぱいパフォを取ってしまいました。もったいなかったです。 jjjjjjjtgpptmjjさんのAtCoder Beginner Contest 174での成績:1161位パフォーマンス:1476相当レーティング:1307→1325 (+18) :)#AtCoder #A…

AtCoder Beginner Contest ABC023 C - 収集王

C - 収集王 解説 実装 C - 収集王 問題へのリンク 解説 行にある点の個数が個のとき、列が個のとき和がになりそうなところから考察を進める。 ここで、列が個の列の個数を追加すれば良さそうだが、ここに罠がある。その列に点があるときはその列は、点がない…

AtCoder Grand Contest AGC025 B - RGB Coloring

B - RGB Coloring 解説 実装 B - RGB Coloring 問題へのリンク 解説 各マスの状態が4種類ある 無 デフォルトを無だと考えて、そこに得点を割り振っていくと考えると、にするかしないかを独立に決めて、重なったらにすると考えればよいことがわかる。 よって…

エイシング プログラミング コンテスト 2020 E - Camel Train

コンテスト参加記はこちら coonevo.hatenablog.com 解説 実装 問題へのリンク 解説 どう置いても必ず得られるベース得点がある ベース得点を先に考慮すると、あるラクダについて左右の好みと得点という2つのパラメータのみを考えるだけでよくなる 左右の好み…

エイシング プログラミング コンテスト 2020 参加記

A - Number of Multiples 解説 実装 B - An Odd Problem 解説 実装 C - XYZ Triplets 解説 実装 D - Anything Goes to Zero 解説 実装 E - Camel Train 記事を分けました F - Two Snuke まだ見てません。 A - Number of Multiples 問題へのリンク 解説 愚直…

AtCoder Beginner Contest 173 ABC173 F - Intervals on Tree

問題へのリンク 解説 まず、「閉路のない無向グラフにおいて、連結成分数 = 頂点数 - 辺数」が成り立つことを使います。 すると、問題は以下のように言い換えられます。 頂点数は の計算でで求められます。は区間の長さです。 辺数に関しては、について考え…

AtCoder Beginner Contest 173 ABC173 参加記

24分4完水パフォでした。少しhighestを更新しましたが、Eの実装で凡ミスしていて悲しくなりました。 A - Payment 解説 実装 B - Judge Status Summary 解説 実装 C - H and V 解説 実装 D - Chat in a Circle 解説 実装 E - Multiplication 4 記事を分けまし…

AtCoder Beginner Contest 173 ABC173 E - Multiplication 4

問題へのリンク 解説 まずの場合は調整しようがないのでやります。負の数が奇数個あったら負にします。 以降はとします。 が奇数の場合、正の数が存在するならその最大値をまず使うことにします。 すると、以降に選ぶ数が偶数個になります。 正の数が存在し…

AtCoder Beginner Contest 058 ABC058 D - 井井井

解説 問題の言い換え 面積Sの計算 登場回数Cの数え上げ ~ xとyは独立 ~ シグマの計算 実装 問題へのリンク 解説 問題の言い換え 数え上げの典型として、「問われている対象を別のものの数え上げで考える」という方針があります。今回もその例に漏れず、出て…

AtCoder Beginner Contest 172 ABC172 参加記

72分5完2ペナで青パフォでした。数え上げを少し練習してたのがよかったんだと思います。 C - Tsundoku 解説 実装 D - Sum of Divisors 解説 実装 E - NEQ F - Unfair Nim C - Tsundoku 解説 令和ABC-Cなのでとで小さい方を取っていく貪欲解を考えますが、す…

AtCoder Beginner Contest 170 ABC170 参加記

3完で緑パフォでした。Dでvectorやmapを使うのをやめたら通ったので泣きそうです。 -> 追記:vectorは問題なくて、mapのlogがTLEの原因でした。 提出へのリンク C - Fobidden List D - Not Divisible C - Fobidden List 0 ~ 1000くらいまで、確認します。に…

第三回 アルゴリズム実技検定 参加記

第三回アルゴリズム実技検定(PAST)を通常受験(not リアルタイム)しました。結果は中級(76点)でした。 まだ解いていない人はここから解いてみましょう! atcoder.jp アルゴリズム実技検定の公式対策本が発売されました。 アルゴリズム実技検定 公式テキ…

AtCoder Beginner Contest 106 D - AtCoder Express 2

atcoder.jp 区間を二次元座標とみなし、二次元累積和で。 一方、クエリ先読みして区間を終端ソートすると、終端が前の区間から順に確認していくことで問題を解くことができる。終端の順番を固定し、始端の分布をBITでもち、和をで得ることができ、計算量はと…

AtCoder Grand Contest 011 AGC011 A - Airport Bus

atcoder.jp 左端を固定して、条件を満たすように右に伸ばしていくのを貪欲に行う。実装は尺取り法が楽になる。 int main() { ll N, C, K; cin >> N >> C >> K; vector<ll> T(N); rep(i,N)cin >> T[i]; sort(all(T)); int r = 0; int ans = 0; for(int l = 0; l <</ll>…