競プロ

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

2023/02/27初公開 競プロ、python、atcoder緑。2023/08/30までに青になりたいです。atcoderマイページ この記事は自分のためのメモですが似た境遇の方の参考になるかもと思い公開。上から順にこなしていく予定0. 今取り組んでいること〆レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【上級編：目指せレッドコーダー！】 - Qiita 1周したので復習(2/28~3/15) ・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 にて、二部グラフのマ…

iwillblog ってやつなのでふりかえってみる。 PHPerKaigiではPHPerチャレンジを楽しんでいたので、その感想を書きます。 （久々にこういうのをやっていたので楽しかったっすね） 逆にセッションは記憶があいまいになってしまったので、ゆっくりタイムシフトで見ます…。 PHPerチャレンジ編 サイボウズ https://blog.cybozu.io/entry/phperkaigi2023-sponser 解説セッションはこちら https://fortee.jp/phperkaigi-2023/proposal/07411094-2fc1-4abd-904f-9470454531e…

こんにちは、年度末に向けて忙しくてご無沙汰しております。 参加スタイルについて 競プロとしての思考力をつけることに加え、業務で使用しない言語にも触れながら言語機能や標準ライブラリを理解すること、競プロのみならず業務で通用するコードを書くこと（命名など）を心がけてやっていきたいと思います。 当面の目標はAtCoderに慣れること、C問題まで正答することとします。 A - camel Case 問題文 英大文字および英小文字からなる文字列Sが与えられます。 ここで、Sのうちちょうど1文字だけが英大文字であり、それ以外は全て英小文字です。 大文字がSの先頭から何文字目に登場するか出力してください。 …

問題 yukicoder.me

yukicoder で noya2 さんと合同でコンテストを開きました. yukicoder.me 全体Tester にはまた Nachia さんに来ていただきました. 二回も全体Tester を引き受けていただき本当に感謝しています!!!! F は特に難しかったので Tester に kaichou243 さんに来ていただきました!!! ありがとうございます!!!! 前回のコンテストは以下です。 yukicoder.me 難易度は ★2.0 - ★2.5 - ★3.5 - ★3.5 - ★4.5 - ★5.0 の 2時間40分 (ジャッジつまりで10分延長！) でした. 前回よりも難しめのセ…

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

最近、餓狼伝説スペシャルのスーファミ版でハイスコアをやり始めた。 俺は子供の頃には歌手になりたかったが、その夢は幼いうちにあきらめてしまって、多分普通の範疇に収まっているだろうみたいなところはあった。母親が「そんなものなれるわけないわよ」って言うような性格だったのもあると思う。 その普通の範疇に入るためには実は厳しい受験戦争があり、中学の時に足を引っ張るためだろうか悪友の誘いで行ったゲーセンのストリートファイターIIにハマった。高校までそれ一筋に熱中してしまい、93年だから高1かな。国技館まで行った。 何も夢を持てないわけでもなく、ミスチルとかウォークマンで聴いて夢に見ていたが、ゲームで強いな…

はじめに 第22回情報オリンピック(JOI 2022/2023)の春合宿に参加しました。 春合宿に参加したのは実は3回目なのですが、参加記などのまとまった文章を自分で発信するのは初めてです。 自分も高校3年生になり1年ほど競プロを離れてしまうことになると思うので、最後に高校生時代の貴重な経験を文章にして残したいという衝動に駆られてこの文章を書きました。拙い文章ですが見てくださったら幸いです。 2次予選 2次予選2日前から39度の高熱と倦怠感に襲われました（後にコロナだと判明）。前年のJOI春参加者は本選までの競技を事前に申請すれば免除することが出来るのですが、申請した記憶が全くなくかなり焦りま…

はじめに Toyota Programming Contest 2023 Springの決勝に参加させていただきました。 JOI、ICPC意外のオンサイトは初めてでとても楽しかったので記録として残しておきます。 予選A うおーーーブザービートで7完したありがとうございました!— KowerKoint2010 (@KowerKoint2010) 2023年2月4日 普段のABCよりARC寄りの重いセットと書かれていて、ARCが苦手な僕は不安でした。 Fで詰まって焦ったんですが、なんとか7完できたので国内51位という結構な成績で予選を通過しました。 普段より面白いセットでした。 予選B kotam…

JOIG 2022/2023の春季トレーニングに参加しました。 問題のネタバレありです。 ~Day -1 直近１年の精進はこんな感じ。↓ Heatmap 気が向いた時にABCに出ていた。特に最近はほとんどパソコンに触れられておらず春合宿に参加するかどうかもかなり悩んだが、色々な人と交流できる機会だと思って参加することにした。 3月に無駄に忙しいスケジュールを組んでしまい、春合宿開始前から既に体力的に限界。腕慣らしのために久々に出たABCでは３完という素晴らしい成績()を残した。 Day0（表彰式＆交流会） 駅さえ間違えなければ大丈夫だと思っていたらその後思いっきり迷った。安田講堂は東大生でもな…

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

自己紹介 先日AtCoder黄色になりました、shinchan(@Sophia_maki)です。最近そふぃあとも名乗り始めました。 目次 自己紹介 予選 Qual A Qual B 東京行き 準備とか 前々日 前日 当日 本番まで 本番 イベント 大宴会 翌日 今後 予選 Qual A 「ふぁ！？3/18？？？TOEIC前日やんけ！前日なら大丈夫やな！うん！」 といいながらレジりました。3完でした(カス)。 Qual B 5完でした。イベント通過は確信しました。 決勝逆ボーダーだとわかり発狂しました。 後日、繰り上がりメールが来ました。2/27にメールが来たのですが、2/28にメールが来た人に…

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