競プロ

表彰式＆意見交換会に行ってきました Hitachi Hokudai Lab. & Hokkaido University Contest 2022(日立北大コン)のＢ問題の成績で(ギリギリ)お呼ばれして、参加することができました。 経緯 意見交換会で発表しませんか？ オンラインで視聴できるかなーという程度で考えていたのですが、2月27日になって「意見交換会ご講演依頼」というメールが届きました。表彰式と意見交換会の3月3日まで結構日が迫っている中でのメールということで、「もしかして人がいなくて人数合わせ的な！？」と思ったりもしましたが、せっかくなので発表の機会をいただくことにしました。 最後とか…

2023/02/27初公開 競プロ、python、atcoder緑。2023/08/30までに青になりたいです。atcoderマイページ この記事は自分のためのメモですが似た境遇の方の参考になるかもと思い公開。上から順にこなしていく予定0. 今取り組んでいること・レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【上級編：目指せレッドコーダー！】 - Qiita 1周したので復習 ・Tasks - 競プロ典型 90 問 1周したので復習 ・Educational DP Contest / DP まとめコンテスト - AtCoder 挫折したのでもう一度1. 過去に学んだことがあり…

AHC 018 2/18(土)-2/26(日) 【概要】 水源がいくつかと、家がいくつかある200x200の土地がある。 水路を掘って、全ての家を水源と接続したい。 ただし、地面には隠しステータスとして「硬さ」があって、掘る時にそれに相応する「体力」を必要とする。 消費する「体力」がなるべく少なくなるように、水路を掘ってください。 atcoder.jp 難しそうなので手をつけるかどうか迷う、1日目。 試し掘りでのマッピング戦略。初回提出の2日目。 綺麗なマップ作りは不要かも。3日目。 やっぱりマップをなんとかしたくて迷走。4日目。 Pの値を正確にしていきたい。5日目。 実際に掘りながらPを修正…

C問題 bit全探索で解く問題．2m-1の選び方がある問題だから，bit全探索で解く問題だとは思ったが，部分集合を足し合わせた集合に1~Nが全て含まれているかどうかを判別するアルゴリズムが思いつかなかった． 解答を見て納得した．std::setというライブラリを使ってそこに値をinsertで格納していくことでそれを実現している．std::setというライブラリは，そこに格納された値は自動的にソートされ，さらに重複した値は新しく格納されないという特徴を持っている（multisetというライブラリなら重複を許容する）．つまり，部分集合に含まれる値を全てset配列に格納していき，その配列の長さがNに…

AHC017 最終50位(暫定49位: 40.3G / 50.0G)の解法 THIRDプログラミングコンテスト2022(AHC017)の解法と，約一週間のコンテスト期間のアプローチについて解説(というか記録)しておきます．ヒューリスティック系コンテストの初心者・中級者や未来の自分の役に少しでも役立てばと思います． 問題の概要 N地点と，各地点を結ぶM個の道があります．この道のいくつかを補修工事するのに通行止めする必要がありますが，そうなると移動が不便になり，不満度が上がります．不満度はある地点から他の地点を移動する際の移動距離が増えるほど大きくなります．工事を行う日数Dと，一日に工事できる(通…

AHC017 1/28(土)-2/5(日) 概要： N個の地点とそれぞれの地点を結ぶM本の道路があり、それをD日間ですべて1回（1日）ずつ工事したい。工事できるマンパワーは1日あたり道路K本まで。 工事中の道路は通れないので、各地点にいる人たちは別の地点に行くために迂回する必要が出てくる。N*(N-1)通りの地点同士の組み合わせそれぞれでの、迂回しなくてはいけなくなった距離の合計値（というか期待値）が不満度として毎日加算される。 不満度ができるだけ低くなるような工事計画を考えよ。 制約 500 <= N <= 1000 500 <= M <= 3000 5 <= D <= 30 ceil(M/…

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

競技プログラミングを開始して4年半、青になってからは2年半でようやく黄色になることが出来ました。 本当は次のARCで青落ちしてまた戻ってこれたらこの記事を書こうと思っていたのですが、時間が経過するごとに色々書きたいことを忘れそうなので忘れないうちに書くことにしました。 青〜黄になるまでにやったこと 大体時系列順に並んでいると思います。 CF バチャ 記憶が正しければ青になりたての頃に CF div2, ECR バチャをそこそこ高頻度でやっていました。 結論から言うと実力向上には間違いなく役に立ったのですが、upsolveをしっかりしないまま次のバチャを始めたりしていて効率の悪い精進になってしま…

問題 atcoder.jp 問題概要 括弧を含む四則演算の式が与えられるので、答えを整数で出力する。ただし、式は画像で与えられる。 式の画像は、Courier Primeというフォントの各文字に対して回転、縦横の拡大（縮小）、せん断変形、平行移動を行って生成される。さらに、確率で画素を反転させるノイズが生成される。 3*3-4（問題ページより引用） この問題について 2014年2月に開催されたJAPLJさんのお誕生日コンテストで出題された問題。 AtCoderで開催されるお誕生日コンテストではいわゆるギャグ寄りの問題が出題される傾向にある（というよりこのコンテストが原点？）が、この問題はその中…

初めましての方は初めまして。 あれ、何か見たことあるタイトルだぞ？って方はお久しぶりです。 概ねタイトル通りの25歳、社会人です。名前は仮で付けましたがどーぞよろしく。 色々な名義で色々なことをしてきましたが続かないものが多かった人生だったので、 ここらで一旦ブログでも始めて備忘録として残しておこうという魂胆です。 で、年度初めだとブログを始める人が多い読みでこのタイミングです。 （それとは別に文章について指摘されることが多いのでその練習も兼ねて） ※色々なこと…小説やブログの執筆、ボイロ実況動画の投稿、Twitchでのゲーム配信、YouTuberもどき、レスバや界隈荒らしに近い行為、競プロへ…

流れで書いてみた 予選 着くまで コンテスト 昼食 パネルディスカッション rngからの挑戦状 雑談 Slovenia おまけ 予選 さすがに通る 着くまで 時間がバカすぎてなかなか寝られずに終了 腹痛を予想して早めに家を出たら大正解 前回のオンサイトとは違うんや(会場までダッシュして到着即コンテスト開始) コンテスト 賞金ノーチャンだからやる気がとかの意見を見てイライラしながら俺はコンテストのために来ているんだと奮い立たせる コンテスト中のこと書くの地味に初めてかもしれん、記憶なし A とりあえず4重ループを紙に書いて実装してサンプルが合うことを確認する 昔はどこをばらせるかでこんがらがって…

atcoder.jp ↑問題文へのリンク タイトルを見て，あの幾何のやばいやつの続編か，いやだな～と思っていたのですがそれは D - Water Bottle でした． 考察はほぼ一瞬で終わって実装で手間取ったのですが，twitterを見ると考察が難しいと言っている人が多くてびっくりしていました． それぞれはそんなに難しくない（茶～緑diffくらい？）典型的な要素がいくつか組み合わさって難易度が青diffまで上がっている地力ゲーという印象があって，こういうのを安定して早く解けるかどうかで実力出そうだな～と思っていました．ということで振り返り兼自省としてこの問題の解説を書きます． 問題文 高橋君…

はじめに 単体テスト前に技術について整理→コード修正・追加→単体テストの三段構えで行きます。 いつもそのつもりで書いておりますが、完全に日記です。右往左往した苦しい時間もみっちり記録しております。 理解に乏しい部分が多々あります。 ブログ訪問者が0人なのでないとは思いますが、もし、この記事を読まれた方いらっしゃいましたら、ぜひ教えてください。 お願い致します。 内容 事前知識整理(※分からない事があったら戻る専用） とりあえず、WebSocketとSTOMPの違いから What is the difference between WebSocket and STOMP protocols? -…

最近知ったTipsを共有します。競プロのためだけに理解の浅いC++を使っている私ですが、最近になってmap, setで最小値、最大値を一発で取得する方法があることを知りました。というか、そもそもこれらにデータを入れると勝手にソートしてくれてるので、最小値、最大値が取れないとおかしいとは思ってたんですけどね。 その名は begin(), rbegin() mapでもsetでも共通です。最小値を取得するときは begin() 、最大値を取得するときは rbegin() を使います。以下、サンプルコードです。 #include <bits/stdc++.h> using namespace std;…

最近、会社のSlackにある競プロチャンネルにジョインしたのもあって、久しぶりに競プロ熱が戻ってきたので参加している。 昨日行われたABC294に参加したのでその感想とか。 なお、問題の意図や解き方を解説するものではなく個人の感想です。またABC294のネタバレになるのでこれから挑戦される方は注意。 A - Filter / B - ASCII Art A - Filter B - ASCII Art 簡単なので特になし。 ACした回答 問題A 提出 #39849428 - AtCoder Beginner Contest 294 問題B 提出 #39854564 - AtCoder Begi…

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

参加してきました。 えびちゃんです pic.twitter.com/thrbw3oZYB— えびちゃん🍑🍝🦃 (@rsk0315_h4x) 2023年3月18日 「参加記に載せる用の画像を載せておくと、参加記に載せるのが楽になる」というのを思い出したので撮っていました。 予選 B で G を解いていい感じの順位になってしまい、参加する運びとなりました。 今までの AtCoder 主催のオンサイトは、DDCC や CodeFlyer などで就活優遇枠での参加だったり、学生コンや最強コンなどでの決勝イベントのみの参加だったりは経験があるのですが、一般枠のような形での通過は初めてだったのでうれしかっ…

3/12 2時就寝、12時起床。 家族と外出した。 ツイートAI分析というサービスがあったので試してみた。 このアカウントの発信者は、競技プログラミングが好きで、自己流の学習法に自信を持っている。沢山のアルゴリズムに興味があり、教えることに喜びを感じている。一方で、自分に厳しく、挫折を乗り越えるために日々努力している様子がうかがえる。 自分に激甘なので、違います…。 競プロ界隈が荒れてるという話を聞くけれど、ぼくがフォローしている範囲ではそうは感じられない。ところがこれを「Twitterのおすすめタブ」にすると一気に荒れる。おすすめタブを見るのをやめたい。 今の競プロ界隈に思うところもあったり…

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