競プロ

この記事でやること はじめに（茶番） 注意点 Dinic法の概要 概略 実装例 計算量評価 実用上の高速化ポイント BFSは頂点t に到達した時点で打ち切る 実は頂点s からDFSするより頂点t からDFSした方が速い（らしい？） 二部マッチングにおけるDinic法の計算量 おわりに 参考文献 この記事でやること Dinic法の仕組みの概略解説 一般のグラフに対するDinic法の計算量と、実用上の高速化が期待できる基本的なポイントの考察 二部グラフの最大マッチング問題でのDinic法の計算量の考察 はじめに（茶番） AtCoder Beginner Contest 285 にて、二部グラフのマ…

最大値と最小値を両方O(logN)で見たい、ワガママな人のための優先度付きキュー。要素の追加はO(logN)、要素の存在確認はO(1)。 ただし、heapqを２つ使っているので使うメモリも２倍、計算量も２倍。 import heapq class HeapBiq: def __init__(self,A=[]): self.low = A self.hi = [-1*a for a in A] heapq.heapify(self.low) heapq.heapify(self.hi) self.dic = {} for a in A: if a in self.dic: self.dic[a…

米田 優峻さん（E869120@ICPC2022 (@e869120) / Twitter）の著書「競技プログラミングの鉄則 ~アルゴリズム力と思考力を高める77の技術~」をご恵贈いただきました。その感想です。競技プログラミングの鉄則 (Compass Booksシリーズ)作者:米田 優峻マイナビ出版Amazon素晴らしい内容で競技プログラミング初心者への最初の１冊として最もお勧めできる本です。特に、数学も得意というわけではなくプログラミング自体も初めてという方には、ダントツで一番お勧めできる本です。 本書の良い点 １．図が分かりやすい。 最初の48ページが無料公開されているので、百聞は一見に…

行列の累乗を計算する方法。 実行時間はgoogle colabのGPUなしで計測。Blocks POJ No.3734 (蟻本P182)などで使用できる。①対角化して累乗。数学的な感じ。 #input import numpy as np np.set_printoptions(precision = 0) A = np.array([[2,1,0],[2,2,2],[0,1,2]]) def diagonalization(x): eig = np.linalg.eig(x) e = np.diag(eig[0]) p = eig[1] return e,p e = diagonalizat…

今年からマラソンマッチを本格的に始めました。また、マラソン力強化のためにAtCoderのアルゴにも挑戦してみました。来年以降もしばらく続けてみようと思うので、将来の自分とこれから競プロをやってみようかと思う方々の参考として、これまでのまとめを記録しておきます。 TopCoder Marathon Match(MM) 2022年のMMレーティング 2013年に初めてマラソンマッチに参加して、この時のレーティングが1720だったので、まずはそれを目指しましたがなかなか成績が安定せず、最高でも1625でした。しばらくはギリギリYellow Coderが続きそうです。とはいえ、初参加時の何となく解法と…

スライスを使った修正されたコード クソコード Pythonの基本的な機能であるスライスを使わずに競プロの簡単な問題を解いたら、えらいクソコードを書いてしまった。 AtCoderの問題：B - Echo (atcoder.jp) 言語の基本機能くらい覚えておくべきだと反省。 ちなみにPythonの割り算はfloat型になってしまうようなのでエラーがでた。そのためintにキャストしてある。 スライスを使った修正されたコード Python - 文字列のトリミング（substring、slicing） (codechacha.com) N=int(input()) S=input() def solv…

・x**yを使わないといけないのに、yの制約が「0≦y≦10**9」とかのとき。①"aのn乗"の計算 def reppow(a,n): if n == 0: return 1 if n == 1: return a if n%2 == 1: ret = reppow(a,n-1)*a return ret ret = reppow(a,n//2) ret = ret*ret return ret このままgoogle colabなどで reppow(3,100000) で実行（して、結果を表示）しようとするとValueError: Exceeds the limit (4300) for in…

出社。上層部がバトっているところが目に入るが、目に入る位置でやってくれるようになってくれただけ改善しているらしい。 業務で詰まっているところがずっと解けない。 気分が沈んでいる。 競技プログラミング D - Teleporter なんでこれ解けないんだろ。 手元で大きいケースをデバッグしようとしたらSegmentation Faultで全然ダメだった。しかしこれは提出してみるとACになるコードで、しかもint64_tを`int'に置換すると手元でも動くというものだった。どうも手元のスタックサイズが小さすぎて、という感じのものなんじゃないかと思うが、こんな初歩的なものを手元で踏むの意味不明過ぎる…

はじめに こんにちは、berryと申します。競プロはほぼAtCoderを中心にやっています。 今回はAHC017に参加するにあたって自分用の振り返りメモを残して自分の考え方を客観的に見てみたい＆解説記事を書いてみたいというモチベーションで書いています。あまり人の役に立つ内容にはならないかもしれません。 なお、コンテスト終了時の暫定順位は261位でした。 [2/7 4:00追記] システムテストの結果は260位でした。AHC016のときはシステスでそこそこ順位が落ちてしまったので、今回は1位だけ上がってくれてホッとしました。 1/28(土) 開始前 まだ午前9時です。コンテスト開始まであと3時間…

AtCoder Beginner Contestの過去問から、その提出コードの解答例です。 AtCoderとは、コンテストを通じて、プログラミングやアルゴリズムを学習するサービスです。 atcoder.jp プログラミングコンテストとは、「与えられた問題をいかに素早く、正確に」解くことができるかを競うものです。 「競技プログラミング」を略して、「競プロ」などと呼ばれています。 #A - Many A+B Problems atcoder.jp僕が作成、提出したコードは、以下のとおりです。 /* AtCoder Problems in C++ #A - Many A+B Problems htt…

AtCoder Beginner Contestの過去問から、その提出コードの解答例です。 AtCoderとは、コンテストを通じて、プログラミングやアルゴリズムを学習するサービスです。 atcoder.jp プログラミングコンテストとは、「与えられた問題をいかに素早く、正確に」解くことができるかを競うものです。 「競技プログラミング」を略して、「競プロ」などと呼ばれています。 #B - Qualification Contest atcoder.jp僕が作成、提出したコードは、以下のとおりです。 /* AtCoder Problems in C++ #B - Qualification Con…

AtCoderで青色になりました！わーー！！！ 青色は始めたときからの目標だったので、到達できて一つ区切りがついたな、という手応えでちょっとホッとしています。 ここ最近は手が空くたびにAtCoderのプロフを眺めてはにやにやしています、えへへへ…… 自分の中で一つ区切りがついた、ということもあり、 このタイミングでこれまでどういうことをやったのか、や、思い出をまとめていきたいと思い記事を書くことにしました。 どちらかというと自分なりの整理のための文章のような内容で、 「これをすれば入青できます！」という類のものではないのであしからず。。。 誰？ 入青するまでにやったこと（精進周り） 精進 バチ…

今週の競プロ活動の振り返りを行います。 やったこと ABC参加 2完、519の茶パフォでした。 atcoder.jp 灰diff7問解く Atcoder Problemsのrecommendationから、カテゴリがEasyの問題を7問解きました。 振り返り 灰色と茶色をうろうろする日々が続いています。年内入緑を目指しているのでまずは茶色を安定させなきゃいけないなと。今回はC問題が茶diffで解けなかったのですが茶パフォにはなっているので、 C問題が茶diff以上の場合はAB早解き(WAなし) C問題が灰diffの場合は3完 が安定してできるようになれば茶色下位くらいで一旦落ち着けるのではない…

0.はじめに 1.問題文 2.最初の考察 3.最初の提出 4.うだうだと考える（実装をする気にならない時間） 5.ローカルでのテストケースを実装して5回目の提出をしました 6.たどり着けない頂点がなくなるまで時間いっぱい山登り 7.順位表のトップが50,000,000,000点!? 8.ライバルには負けたくない 9.天啓が降ってきた（と思ってからの暗黒の3日間） 10.コンテスト8日目（最終日前日） 11.コンテスト最終日（2023年2月5日） 12.終わりに（2023年2月7日更新） 13.最終結果（2023年2月7日更新） 0.はじめに はじめまして、もしくはお久しぶりです、競プロ歴約3年…

こんにちはソムニオです。 いよいよ私立大学の受験も始まりました。国立大学の前期試験まで約３週間、どうか体調を崩さず全力で駆け抜けられますように。 参考になればと思ったことを少し書いてみます☺️ 共通テスト後に志願変更しなくてはいけない子がいました。限られた時間の中で過去問を解いて相性を確認したり、配点を調べたりするのは大変。 もし受験が来年以降であれば、親御さんがこっそり事前に志望校以外の配点を調べたり、パンフレットを取り寄せておくのも良さそうです。 調べた情報を使わなければそれが一番ですが、備えておけば万が一の場合、共通テストから前期試験までの貴重な時間を有意義に使えそうです。 あと第一志望…

1/29 『何もしない』第四章を読んだ。普段いろいろなものが視界の中に入っているが、意識しなければそれらが「見える」ことはない。注意を向けることでそれらが見えるようになる。こういったことをBlenderを用いて説明していたのが面白かった。Blenderではオブジェクト、カメラ、照明などがあり、それらをレンダリングすることで一枚の絵になる。レンダリングの方法を変えれば出力される絵も変わる。ぼくたちは実際に存在するものを、脳内でレンダリングすることにより認識している。 絵というのは一瞬を切り取ったものだと思っていたけど、連続する時間を絵で表現しようとする試みがあることを知った。キュビズムもそういっ…

考え方 回答例（UnionFind） 考え方置換になっている組が存在するとダメなことがわかる．変更前と変更後の名前に辺を貼ったグラフで考えれば，閉路があるということ． 閉路検出 - 競プロはじめました アライグマ「D問題は、入力例2みたいに、変えたい名前がループしてるユーザたちがいるときだけNoなのだ。ということは、グラフのサイクル検出ができればよくて、DFS/BFSやUnion-Findで解けるのだ！」 pic.twitter.com/l2aQfsizM5— 競技プログラミングをするフレンズ (@kyopro_friends) January 15, 2023 回答例（UnionFind） …

競プロについての活動記録を毎月とってみようと思います。 これをやる理由は 競プロのモチベーションアップにする 記録しておいたらもしかしたら後で何かの役に立つかもしれない 何か記事を書く癖をつけたい という感じです。 もしかしたら今回しかやらないかもしれません。この記事を書きながら数回前のコンテストについてけっこう覚えてないなと思ったので、当時思っていた感想とは異なるものもあるかもしれません。 AtCoder のレート変化 1658 → 1607 (-51) レートが上がることの多い ARC にだけ Rated 参加したが、すべてレートが下がってしまった。 もう水色に落ちたくないなと思っていたけ…

こんにちは、寒い日が続きますね。 私は温泉が恋しくなって先週は山梨におりました。 温泉宿から解くAtCoderもまた乙なものです。 参加スタイルについて 競プロとしての思考力をつけることに加え、業務で使用しない言語にも触れながら言語機能や標準ライブラリを理解すること、競プロのみならず業務で通用するコードを書くこと（命名など）を心がけてやっていきたいと思います。 当面の目標はAtCoderに慣れること、C問題まで正答することとします。 A - Majority 問題文 ある提案に対し、N 人の人が賛成か反対かを表明しています。なお、N は奇数です。 i(i=1,2,…,N) 番目の人の意見は文字…