G4NP0Nのブログ

競プロとそれ以外のことについてしゃべります。

Heuristic黄色になれたので今までのAHCを全て振り返ってみる

競技プログラミング コンテスト参加記

先日行われたHACK TO THE FUTURE 2024 (AtCoder Heuristic Contest 027)でHeristicレーティング黄色になりました！

…

Algo入青から2年半ぶりに新しい色に到達できたのでうれしいです。

ヒュの色変記事ってあんまり見たことないので書いてみようかなと思ったんですが、何書けばいいのかわからなかったので、今までのAHCを自分なりに振り返ってみようかなと思います。記憶とツイートが頼りなので嘘を書いてたらすみません。

 

注意！

以下、AHC過去問のネタバレが大量に含まれます

 

Introduction to Heuristics Contest - AtCoder Contest Scheduling

CodinGame SPRING CHALLENGE 2020に参加してみたら思いのほか楽しくて、アルゴ以外のジャンルにも挑戦してみようかなーというタイミングで開催されたような気がします。そもそも自分はヒューリスティック系の知識を一切持っていない状態だったので、解説記事を参考にスコア計算とビームサーチを実装してその日は満足したようです。

その後も、焼きなまし法の練習とかで何度か解き直しています。

解説PDFが非常に有用なので、AHCに興味を持った人にぜひ勧めたいです。

 

AHC001 - AtCoder Ad

順位:354　パフォーマンス:1391　レート:0→391

記念すべき第一回AHC。興味はあったものの、Algo入青直前でそちらの精進にかまけていたので途中までほとんど手つかずでした。

最終日の前日のABCで無事Algo青色になれたのでそこから1日だけ参加。

当然ほとんど知識がない状態だったので、少しずつ箱を大きくしたり動かしたりするだけの貪欲を書きました。

 

TERRYさんのビジュアライザ動画が本当に衝撃的で、今振り返ると自分のAHCの原体験はこれだった気がする。

 

AHC002 - Walking on Tiles

順位:491　パフォーマンス:1169　レート:391→662

第二回AHCは短期コンテスト。当時は19時-23時開催だったんですね、今とずいぶん違うね。

行き詰ったら途中からやり直すみたいなDFSを書いて、マップの半分程度しか埋められなくて途方に暮れていました。なんなら去年もう一度解いてみた時にも大した改善ができず……。（その時はビームサーチを試してたはず）

この時ちゃんと復習をして、経路を部分的に破壊して再構築する手法を勉強していたのが、AHC027の勝因だったと思います。

自分の師匠であるthunderさんがAHC027の2日前に解説記事を書いているので（エスパーか？？？）、興味のある方は是非この記事で勉強してみてください。

AHC典型解法シリーズ第2弾「焼きなまし法」 #AtCoder - Qiita

 

AHC003 - Shortest Path Queries

順位:817　パフォーマンス:658　レート:662→711

AHC初のインタラクティブ問題。

最近ようやく多腕バンディット問題という概念を勉強しましたが、当時は当然そういった体系的な知識があるわけもなく。

通った道の重みを適当に更新しながらダイクストラ法してた気がします。

yosssさんの解法スライドが非常に本格的。そろそろきちんと復習しなくちゃ……。

 

AHC004 - Alien's Genome Assembly

順位:-　パフォーマンス:-　レート:-

不参加でした。

AHC004からAHC010まではほとんどが短期コンでしたね。この時期から1年ほどは入籍や結婚式の準備で土日が潰れていることが多く、短期コンテストに参加し辛かったです。

 

AHC005 - Patrolling

順位:139　パフォーマンス:1703　レート:711→1039

シンプルで結構好きな問題。

ググって出てきた記事を読みながら2-OPTを実装しました。初めてちゃんと山を登った問題かも。

上位陣は使う頂点も焼いていて、「この人達なんでも焼くな……」と軽く引いたのを覚えています。実際にはもっととんでもない問題も平然と焼かれる魔境ですが。

とはいえ、問題設定はシンプルで初心者にもとっつきやすいので練習にオススメ。

 

HACK TO THE FUTURE 2022 予選 - Project Leader

順位:348　パフォーマンス:1277　レート:1039→1114

AHCではないですが、レート変動があったので記載。AHCの名を冠さないRatedのHeuristicコンテストはこれ含め今まで3つしか開催されてないんですね。

各社員の能力を推定したうえで適切に計画を組まなきゃいけないので、けっこう解きごたえがありそうな問題。自分は当時どちらもできておらず、なんならこの記事を書くまで問題の存在を忘れてました……。

 

AHC006 - Food Delivery

順位:-　パフォーマンス:-　レート:-

当日は不参加で、後日ちょっと解いてたかも。

TERRYさんの解説を読んで、強い貪欲を考える大事さを学びました。

Algoでは”全ての基本は全探索”ですが、同じくらいHeuristicでは"全ての基本は（嘘）貪欲"であることを意識したいです。

そのうち丁寧に解きなおしたい。

 

AHC007 - Online MST

順位:-　パフォーマンス:-　レート:-

不参加で、まだ解いてないです。

 

AHC008 - Territory

順位:-　パフォーマンス:-　レート:-

唯一NoSub撤退したコンテストです。とても苦い思い出。

やりたいこと自体はいくつもあったものの、複数キャラクター操作をどうやって管理すればいいのか全くわからず逃亡。

CodinGameでもそうなんですが、マルチエージェントの問題が露骨に苦手っぽい。

iwashiさんの解説記事がすごくよかったので、いつかリベンジしたい。

 

AHC009 - Robust Memory of Commuting Routes

順位:-　パフォーマンス:-　レート:-

当日は不参加で、1ヵ月後くらいに解いてみました。

とはいえ、上位陣のビジュアライザは見ていたのであくまで練習という感じ。

ビジュアライザが見ていてかなり楽しい問題。

 

AHC010 - Loop Lines

順位:194　パフォーマンス:1571　レート:1114→1229

結婚式の翌日でしたが、妻はTOEICに、自分はAHCに参加。ストイックすぎる。

めちゃくちゃ難しかった……今出てもやっぱり解けない気がする。

設定がまあまあ特殊。まずまともなサイズのループを作るのが難しくて、validな状態のまま次の状態を探すのも難しい。しかも2つ必要。

上位解法があまりに天才的でひっくり返ってしまった。重大すぎるネタバレなのでここには書きません、まだ解いていない方はぜひ一度自力で挑戦したうえでひっくり返ってみてください。

 

AHC011 - Sliding Tree Puzzle

順位:115　パフォーマンス:1871　レート:1229→1392

AHC初のパズル問題？ジャンル分けとして正しいのかは知りません。

最終的には100位を割ってしまったものの、初めて"戦えた”という実感を持てたのがこのコンテストでした。初日に徹夜した結果、朝方に木を完成させることができてめちゃくちゃ舞い上がっていたのを覚えています。この辺から長期コンへの取り組み方が沼ってきました。

maspyさんが異常なほど強かったのが印象的です。

 

AHC012 - AtCoder 10th Anniversary

順位:223　パフォーマンス:1550　レート:1392→1441

相変わらず短期コンは苦手気味です。

自分は直線の角度にも自由度を持たせちゃったのですが、水平・垂直方向の直線のみで構成すれば高速に計算できるというのはたしかにといった感じでした。

意図的に制約を設けることで探索空間を限定して高速化するのは典型テクとして忘れないようにしたいです。

ビジュアライザでえげつない形状のケーキがたくさん流れてきてかなり楽しかった。

 

AHC013 - Server Room

順位:225　パフォーマンス:1540　レート:1477

かなり迷走した回。

よい状態というものをあまり考えられないまま、とりあえずビームサーチをしていました。この頃はまだ焼きなましの近傍を考えるのが下手くそで、愚直な近傍でスコアが滑らかにならない問題はとりあえずビーム撃ってお茶を濁しがちでした。

 

AHC014 - RectJoin

順位:254　パフォーマンス:1438　レート:1477→1498

AHC013と同じく、かなり迷走しながらとりあえずビームを打っていました。

今振り返ると当時の自分はAHCへの取り組み方を間違えていて、"その問題が持つ固有の性質を考えずに、とりあえず典型的なヒューリスティック手法を適用して解決しようとしている"といった状態でした。反省。

問題自体はかなり面白いです。seed=0もオシャレ。

 

AHC015 - Halloween Candy

順位:470　パフォーマンス:1104　レート:1498→1501

実際にありそうなゲームが題材で面白かったですね。

18年連れ添った愛犬の葬式と被っていたので、1時間半だけ参加しました。

時間作ってちゃんと詰めてみたい問題のひとつ。ゲーム木探索のいい練習になりそう。

 

AHC016 - Graphorean

順位:69　パフォーマンス:2148　レート:1501→1651

問題設定が良すぎる。なんだグラフだけ送れるタイムマシンって。

AHCはストーリーがついていることが多いですが、ダントツで好きなのがこれです。実際の問題ともすごく嚙み合っていて、どうにかグラフを復元しようと四苦八苦する一週間でした。気分は高橋くん。

実際、この問題が一番好きだと言っている人は多い印象です。

 

開始直後に瞬間風速1位を取ったり初の2桁順位＆黄パフォで当時は大満足でしたが、小さいケースが弱かったりシステスで20位以上順位を落としたりと、今振り返ると詰めの甘さがあります。

 

AHC017 - Road Repair

順位:267　パフォーマンス:1550　レート:1651→1665

仲の良い競プロerとスキー旅行に行っていたため、後半のみ参加。

問題の性質を完全に間違ってとらえており、市中のあちこちで細切れに工事する激ヤバ計画を策定するハメに。

よさそうな方針が浮かばないときには、一度数十分とかかけてじっくり愚直に焼きなましてみて、良いスコアの解が持つ性質を掴むべきだという教訓を得ました。

 

AHC018 - Excavation

順位:73　パフォーマンス:2165　レート:1665→1772

コスト不明なグリッド上で最小全域木を求める問題。AHC003を彷彿とさせますね。

実際、ちゃんと推定できている人が勝てていた印象。ここらへんから、インタラクティブ問題で数学的裏付けのない適当な推定じゃ勝てないんだなというのを悟り始めた気がする。

 

2度目の黄色パフォ獲得で、レーティング黄色を意識し始めたのもこの頃です。

 

AHC019 - Silhouette Block Puzzle Creation

順位:136　パフォーマンス:1787　レート:1772→1798

問題文を読んだ瞬間にゲェ！と声が出たのを覚えています。見た瞬間に実装から逃げたくなる複雑さだなと。

血反吐を吐きながらよくわからない貪欲を書いた気がします。あんまり覚えていないです。

この問題でも上位陣が焼いているのを見て、焼きなましからは逃げられないんだなと覚悟を決めました。

 

このclar好き

他のブロックに引っかかって外せないなど物理的に不可能な配置であっても、正の体積の共通部分を持っていなければ有効な解であるとみなされます。子どもたちは超能力でブロックをワープさせることによりそのような配置を作ることが出来ます。

 

AHC020 - Broadcasting

順位:177　パフォーマンス:1787　レート:1798→1819

使う放送局を焼きなましして最小全域木作ってみたいなことをしようとしていたはず。

シンプルに実装がおせぇ！バグらせすぎ！

比較的シンプルな問題設定なだけに、自分のやりたかったことをやりきれなかったという不完全燃焼感に襲われるので、負けた短期コンはつらい。

もっとサクサク焼けるようになりたい。練習あるのみですね。

 

AHC021 - Pyramid Sorting

順位:543　パフォーマンス:1255　レート:1819→1819

完全にトラウマです。

短期コンに苦手意識はあれど、オンサイト全然狙えると思っていたのに大爆死しました。

何より最悪なのは、コンテスト後のTLで”天才貪欲”と呼ばれていた解法を開始30分くらいで書いていたにも関わらず、バグらせていたためにスコアが伸びず、よく検証しないままその方針を棄却していたこと。

2週間くらいは自己嫌悪に陥っていました。うう。

 

AHC022 - Exploring Another Space

順位:49　パフォーマンス:2281　レート:1819→1915

事前に構築した情報から推定を行うという部分からAHC016 - Graphoreanとなんとなく通ずるところがある問題。

このコンテストの前半は徳島旅行と被っていたためほとんどコードは書けなかったのですが、頭の中で標準分布の性質をどうやって使えばいいのかじっくり考えられたのがきちんと実装のときに活きたなと思います。

探索と活用だけではなく構築とのトレードオフを考えなくてはいけないのも難しかったです。ノイズに応じて離散的な点をいくつか配置する解法自体は悪くなかったものの、探索結果を用いて情報を更新していく処理が雑で、あと一歩詰め切れなかった。

 

上位入賞ということで、RECRUITさんのオフィスで行われる懇親会に参加しました。

初のオンサイトイベントで、Twtterで話したことあるAHCerとたくさん交流できてとても楽しかったです。トヨタコンオンサイトに行けなかった雪辱を果たしました。

 

AHC023 - Crops on Grid

順位:174　パフォーマンス:1738　レート:1915→1923

ほぼ土日のみの参加。

問題設定は長期コンテストにしては比較的シンプルでしたが、けっこう上位陣との差がはっきりつけられてしまった。

通路決め打ち＆貪欲で達成できる上界が低そうというのは見えていたのに、別の解法を考え直すことができなかったのは反省点。順位表情報はもっと活用しなければいけないですね。

 

AHC024 - Topological Map

順位:355　パフォーマンス:1283　レート:1923→1924

完全にバグにハマってしまい、初めてまともに動いたのが終了1時間前でした。局所探索の近傍を考えるところまで行けなかったので論外。

短期コンテストではバグらせにくさという軸にもっと重みを置くべき。

ただ、自分では思いつかなかった近傍や、連結判定の簡素化など、コンテスト後のTLから吸収できる知識が豊富でした。延長戦もけっこう盛り上がっていた印象。

いずれはIntoroduction To HeuristicやAHC005で基本的な焼きなまし法を練習した後のチャレンジ問題みたいな位置づけになるのかなと勝手に思ってます。

 

AHC025 - Balancing by Balance

順位:85　パフォーマンス:2087　レート:1924→1963

ハチャメチャにシンプルな設定なのに操作の自由度がとても高くて、どれだけ小さな改善を積み上げられたかがそのまま結果に反映される問題だったのかなあと思います。とはいえ、実際に重さを推定できている方もいたのはかなりビックリしました。

マージソートを自分で丁寧に実装するよい練習になりました。既に比較したことのある集合同士の大小関係情報の推定・伝播は詰め切れない部分もあり、要復習。

 

AHC026 - Stack of Boxes

順位:180　パフォーマンス:1750　レート:1963→1969

トヨタ関係のコンテストはなんかこういう問題多いですね、荷物積載計画みたいな部分に課題感があるとかなんでしょうか（適当）

シンプルな貪欲を書いたところまではよかったのですが、そこから特殊なケースを改善する方向に行ってしまったのが完全に失敗。最後まで貪欲した結果をスコアとするビームサーチに書き換えて全体的なスコアを向上させるべきでした。

一方で、一列ソート方針は全く思いついていなかった。思いつかんくないか？？？

 

AHC027 - Recurring Cleaning Route

順位:25　パフォーマンス:2450　レート:1969→2069

初の橙パフォで入黄！

でも、解法としてはあまり特殊なことはしなかったです。基本アイデアは部分破壊再構築と部分反転だけ。

初期解がスコアが悪化せず長さが短くなるように手を入れたり、スコア計算が少しでも軽くなるように計算順序を工夫したり、ひたすらパラメータ調整を繰り返したりと、0.5~1%の改善をひたすら積み上げました。

そういう意味では、TLで異常高速化回だと揶揄されていたのもあながち間違いではないなあと感じます。

 

まとめ

AHC大好き！これからも参加します！

入籍しました。

本日（2022/07/20）、交際5年目となる彼女と入籍しました。

暖かい家庭をうんたらかんたら……

 

真面目に書きたいことが特にないので、今回の入籍に至るまでの険しい道のりを書き残しておきます。

6/30　エアコンが動かなくなる

ちなみに諸事情あって、これを書いている時点でまだ修理に至っていません。サウナみたいな部屋でキーボードを叩いています……。

7/2 彼女が東南アジアへ旅立つ

まだ帰ってきてないです。お仕事なのでしかたないね。今はタイにいるらしいです。

出発前日、エアコンを求めて宿泊した東横インで午前3時に婚姻届けを6枚かかせたのは本当に申し訳なかった……。（書き損じ対策のため）

エアコンが使えず彼女もいない自宅にいる意味がなくなり、千葉の実家へと帰省。

7/7 コロナ罹患

唐突にコロナ陽性に。しかもかなり症状重たかったです。実家に帰省したタイミングなのでなんとか無事だったけど、エアコン壊れた自宅に一人だったら本当に生命の危機だった気がする。

で、このコロナのせいで、かなりいろいろな予定が崩れました。

エアコン点検がリスケ

もともと猛暑のせいでかなりアポが取りにくく、7/1に電話して10日以上待たされていたのだが、コロナで点検に立ち会うことができずに延期に。結局、7/21まで再度延期する羽目に。

結婚指輪が受け取れない

本当は7/17に受け取れる予定だったのですが、コロナの後遺症で外出が難しくなり、泣く泣く受け取り延期。婚姻届に指輪載せて写真撮るやつができなかったの悔しい。まあ予備の婚姻届が何枚かあるので指輪受け取ったら撮ります。

 

（撮ったらここに貼る）

 

7/19~20 婚姻届記入＆提出

大変でした。

戸籍謄本の準備

戸籍謄本はコンビニで印刷できるというのを知っていたので、コロナの療養中であったこともあり前日まで特に準備等していなかったのですが、住民票と戸籍謄本の市が違う場合、5日前までの事前申請が必要とかいう謎ルールが提出前日に発覚し、慌てて仕事を抜け出してチャリで区役所に向かう。

婚姻届記入が難しすぎる

いろいろあって午前3時くらいに眠たい目を擦りながら記入。

住所を記入する欄が小さすぎて発狂するかと思いました。大学で明らかに4文字分くらいしかない学科欄に小さな字で"情報エレクトロニクス学科"って書かされたのといい勝負。

あと、現住所と元の本籍と新本籍が全部違うのがややこしくて、めっちゃ間違えた。

いざ、区役所へ

区役所の入り口の建物名を見て、半年間住んでた区の漢字を間違えていたことが発覚。そんなことある？

婚姻届けの現住所の漢字も間違えており、かなり焦ったけど受理してもらえた。ありがとうございます。

終わりに

結婚報告じゃなくて呪われし7月の近況報告みたいなものが出来上がってしまった。どうして。

CodinGame Spring Challenge 2022 参加記

はじめに

CodinGameの Spring Challenge 2022 に参加しました！

www.codingame.com

結果は288/7695位(Legend) でした！コンテスト期間中のLegend到達は初なので、大満足です。

お前は誰

北大工学部を卒業し、社会人2年目に突入した競プロerです。

コドゲは2020春が初参加ですが、ゲームAIのイロハを一切知らずに毎回適当にSilverまで上がって満足してやめてた程度のエンジョイ勢でした。

4月に突如コドゲのモチベが沸き、LineRacingでゲーム木探索を勉強したのでいざ実践！という意気込みでコンテストに臨みました。

まあ今回のコンテストではゲーム木探索使えなかったんですが。

ルール

防衛ゲームに見せかけた超次元サッカーです。

ツカモさんの翻訳+α記事がわかりやすいです。リスポーン地点の話とかスペルの細かい仕様は自分だけじゃ把握できてなかったので助かりました。

tsukammo.hatenablog.com

やったこと

探索も盤面評価もしない、攻撃2守備1のルールベースです。本当は敵の動きも見たかったのですが、とても実装が間に合わなかったので一切見てません。敵の座標すら確認していないので、このターンに確実に死にそうなMonsterにスペル打つみたいな無駄なこともけっこうしてます。

序盤

マナが初めて120溜まるまでモンスターを狩ります。

攻撃役は敵陣に近いリスポーン地点前で、防御役は防衛拠点で待機します。

各ヒーローの現在地から3ターンで攻撃可能なモンスターがいる場合攻撃に向かいます。ただし、各ヒーローに割り当てられたマナ稼ぎ拠点から離れすぎると陣形がめちゃくちゃになるので、マナ稼ぎ拠点からの距離で行動範囲を絞りました。

攻撃

Windでモンスターを敵baseまで4700以内に飛ばし、次のターンで2HeroでWindしてゴールにねじ込みました。Twitterで二重の極み戦法って呼ばれてたやつですね。

ボンドさんのリプレイから着想を得ました。

 

自分が最初したときにはこんな感じ。ゴールから4600の距離で待機しておくことで、ヒーローのWIND範囲にモンスターが入ったときにモンスターから見てモンスター→ヒーローのベクトルになるようWINDを打つことでモンスターがW WINDでゴールできる位置に移動するはず！みたいなことをGeoGebraでお絵描きして確認したりしました（リンクした動画では普通にパスミスもしてますが）

 

近くにシュートできるボールモンスターがいない場合はだいたい以下のように行動していました

  1. このまま進めばシュートできるようになるモンスターがいる場合、待機継続
  2. 1のようなモンスターがいないがControl範囲内にモンスターがいる場合,CONTROLでセットアップ
  3. モンスターが近くにいない状態なので、ヒーローの片割れがリスポーン地点にモンスターを探しに行く
    • モンスターがいれば上記1,2をして拠点に戻る

あとは残りHealthが少ないモンスターを対象外にしたりとかマナの残量次第でマナ稼ぎしたりとかも入れてみてます。

はじめはゴールとの角度45度の箇所で待機してたんですが、中央は敵の防衛も手厚いのでなかなかシュートのタイミングが訪れないんですよね。最終的には(0,0)ゴールの場合(4400,1280)くらいの位置で待機するようにしました。これでかなり順位改善しましたね。本当は(4600,0)で待機したかったんですが、壁に向けてWINDしたときのボールの軌道計算が面倒だったので、楽をするために少し境界と距離をおきました。

やってることはシンプルなんですが、予想しない挙動がたくさん起きていたので、主にここの制御を精緻化するのが今回のコンテスト期間の大部分を占めましたね。

防御

みんな言ってるけど、本当に難しかったです。攻撃側が取れる戦略が多彩すぎる。

結局、自base到達が一番早いモンスターを優先的に排除するというザ・平凡な方針に。

  1. このターンに自baseがダメージを受ける場合、WINDする
  2. 自baseとの距離が一定未満のモンスターがおり、マナに余裕がある場合WINDする
  3. 1,2でない場合,MOVEする
    • 全モンスターの動きをシミュレートし、一番早く自baseに到達するモンスターを特定
    • 1で求めたモンスターを攻撃できるようになるまでの時間を計算
    • 全モンスターを対象にbit全探索し(ただし、1で求めたモンスターを含めるもの),各モンスター集合に対して最小包含円を求める。求めた最小包含円の半径が800以下で,2で求めた時間以内に中心にたどり着けるもののうち最も多くの点を含むものを採用

防衛時に複数モンスター巻き込みは最初から考えていたものの方針が浮かばなかったのですが、Terryさんのツイートを見てbit全探索でいいじゃん！となり、最小包含円計算は適当にググって出てきた記事を参考にO(N^3)のものを実装しました。

Controlでお手玉されたりShield物量作戦にかなり弱く、攻撃役がゴールを決めてくれるまでの時間との勝負になりがちでした。

雑な日記

コンテストに関係ない要素が多々含まれるので興味ない人は飛ばしてください。

前日譚

かえでさん,ボンドさん,ツカモさんと遊んでコドゲのモチベを上げたり、

thunderさんの記事を読みながらLineRacingでLegendに到達してたりした。*1

qiita.com

次のコンテストでもLegend目指すぞ～という気持ちに。

4/21 ~23:00

コドゲ参加者とTwitterでコンテスト開始までワイワイと盛り上がるなどしていた。

4/21 23:00

問題公開。ツカモさんが翻訳記事を出してくれるのを待つのもアレなので、Deeplを駆使しつつ問題文を読む。

複数キャラ操作ゲーか……パックマンで途方に暮れていた苦い記憶が蘇る。しかも盤面がかなり大きい。DUCTは難しいのかな？とか考えながらとりあえず拠点に一番近いモンスターを狩りに行くコードを提出すると、なぜか毎回1ターン目に死ぬ。

何かと思いきや、実は入力にルールに記載されていない「ヒーローの数」とかいう固定値があるらしい。なんやねんそれ。

翌日も労働があるので、とりあえずWood2を抜けたことを確認して、就寝。

4/22

朝起きたらWood1抜けてBronzeいってるかなーと思っていたが、視界が制限されたことにより敵ヒーローの位置が取れていなかった関係でバグっていた。

直した＆ちょっと適当にロジックを直して,Bronzeへ。

競プロをもともとやっていて新卒のプログラミング研修が暇そうな親友にLineRacingを布教してみたらハマってて草。

4/23

この週末はAtCoder関連のことしてた時間の方が長かったな。

 

なるほどーっつってた。確かにスプラトゥーンでもスマブラでも結局強みを押し付けるムーブが最強なんすよ。

 

新しいPCが届いたので環境構築した（っつってもVisualStudio入れるだけ）

 

kenkooooさんとカフェでお茶しながらお仕事についてやkenkooooさんご本人の経歴についていろいろと教えてもらう。めちゃめちゃ面白かった……。

 

夜はABC249に参加。ひさびさの4完で-40くらいしてしまった。Eが解けなかったのは筋力の衰えを感じる。

4/24

AHC10に参加。難しすぎませんか？DFSを早いうちに切り捨ててしまったのが大悪手だった。

Algo Artisの方達が爆死してたのが面白かった。

 

夜はARC139に参加。まさかの0完太陽をキめる。-84して逆入水。そんなことある？

まあ、どうせ青にはすぐ戻れるので気にしてないです。

4/25~4/28

労働に屈していました。頭の中で戦略を組み立てたりはしていたが、一切コーディングはできておらず。

複数キャラを用いた盤面,Action管理をどう実装するのが楽か？という部分について悩んだ。3体個別操作は自分の実力では難しそうなので、攻撃か防衛役どちらかを2人重ねて実質攻撃役と防衛役の2キャラ操作とみなせないか？と考えていた。

4/29

スプラトゥーンをしていました。

4/30

ようやくコーディング着手。

この時点で攻撃2防衛1の構想はできていたが、Silverに上がるためには守備だけどうにかなればよさそう。

1週間頭のなかで考えていたことがとっちらかりすぎてどこから手を付けていいのかわからなくなったので、Scratchみたいな感じでやりたいことを日本語で書いてみる。

1人防衛役のコードを書く。この時点ではまだ丁寧にクラス設計とかをしていた。

完成した防衛役コードを3人全員に適用する。攻撃なしでもSilverに上がることができた。

5/1

7時

早くに目が覚めたので、今後の実装方針を考える。

この時点ではまだ結構時間に余裕があると思っていたので、呑気に彼女と買い物に向かう。無印良品でゴミ箱とスリッパを買った。

11時

コンテスト期間を5/3までだと何故か勘違いしていたが、この時点で残り24時間と少ししかないとようやく気付き、焦る。

正直今回はLegend無理かもな……となかば諦めの境地に。

とりあえずGoldを目指して攻撃役のコードを書き始める。とりあえずゴール角45度の距離4600の箇所で二重の極み発動をただ待つだけの攻撃役コードを書く。

15時

完成したのでとりあえず提出してみたらGoldに上がった。えっこんな簡単でいいの？

防衛用コードにbit全探索と最小包含円を実装する。敵の読みも入れようとしたが実装が重いわりに効果が不確定だと思ったのでそちらには手を付けず。

この辺からまともな設計をすることを諦め、すべてのロジックをべた書きするスパゲッティ実装になり始める。

19時

LastBattlesを見て意図せぬ動きをしているものを見つける→デバッグ→暫定修正をする、を数時間繰り返す。

パラメータを適当に弄ったりもした。無駄な時間なのはわかってるけどやっちゃうんだよね。あとは勝った試合を眺めて時間を溶かしてた。

5/2

2時

ゴール角45度で待つよりも、真横で待つほうが敵の防衛も薄いしモンスタースポーン地点に近いのでよいと気が付き、攻撃待機拠点の場所を変更する。これが功を奏し、Gold200位くらいに。

5時

ゴールできない状況なのに二重の極みセットアップしたり、逆にゴールできる状況なのに無駄にControlを打っている試合がいくつかあったので、攻撃役のロジックを変更。

さすがに体力の限界を感じ、修正したコードを提出する。就寝。

12時

目覚ましが鳴ったので起きる。リビングで彼女が唐突にAmazonで買ったらしいオカリナを吹いててめっちゃ笑った。順位を確認。Gold40位で、かなり惜しい感じがする。

あまりにも眠かったので、パラメータを一部変更し、二度寝。

13時

起床。順位表を確認するとGold4位でクソデカい声が出る。出かけたと思っていた彼女が実はソファで昼寝しており、ジト目で抗議された（ごめんなさい）

飯を食っている場合じゃねえ！ってことで、COMPを流し込む。COMPはいいぞ（唐突なステマ）

www.comp.jp

 

何か改善できそうな余地がないか必死に考える。

考える。

 

考える……。

 

 

 

考えていたら他の人の提出でボスのレートが下がり、Legendに到達した。やったね。

Silver到達から40h以下でLegend到達できたので、まあまあスピーディにLegend行けた気がする。うれしい。

 

あとはTwitter見たり漫画読んだりゴロゴロしながらコンテスト終了までを過ごしました。

 

おわりに

めちゃめちゃ楽しかったです！！今回のLegendは普段に比べてめっちゃ緩いみたいな話もあったけど、まあそんなに気にしていないです。

俺が†Legend†や！

CodinGame最高！

*1:この辺の話も記事にしようと思ってたんだけど記事にする前にコンテストが始まってしまいました

ABC198 参加記＆解法メモ

コンテスト参加記 競技プログラミング 解法解説

f:id:G4NP0N_kyopro:20210411230853p:plain

47分2ペナ5完で271位でした。黄パフォ！AGCで溶かしたレートを取り返したぜ。

 

atcoder.jp

A - Div

Aくんが得るお菓子の個数が1個,2個,…,N-1個となるので、答えはN-1通りとなります。

B - Palindrome with leading zeros

先頭に0をつけることで回文にできる→末尾の0を削除することで回文にできる、という言い換えは典型っぽい。入力を反転して0の間文字を消去してできる文字列が回文かどうか判定すればいいです。

文字列の回文判定は反転した文字列が元のものと等しいかをチェックすればいいんですが、毎回忘れてて普通にfor文で前後から見てチェックしちゃう……。

C - Compass Walking

幾何に見せかけた誤差問題に見せかけた知識＆コーナーケース問題。

とりあえずまっすぐ近づいていくことを考える。もし通り越してしまう場合は,途中で少し遠回りすることで目標の座標にピッタリ到着することができます。これは知識というか経験で知っていたんですが、サンプル3を見れば初見でも思いつけそう？

nR>=√X^2+Y^2を満たす最小のnを求めたいです。ABCで教育されてきたコンテスタントなら、原点から目標までの距離は小数となるので、少し誤差が怖いな～と思うのが自然ですね。両辺を2乗する式変形により、整数型のまま計算することができます。32bit整数型では収まらないので、long longなどの64bit整数型を使いましょう。

二分探索でもいいですが、R=1,X=Y=10^5のときでも高々10^5*√2歩程度でゴールできるはずなので、for文でチェックするほうが楽ちんですね。

 

ここまでコンテスト開始から7分程度。いざ提出……というタイミングで順位表をチラッと見ると、まだACが20人ちょいしかおらず、ペナ率が尋常でない。何か見落としはないか……と考えると、目標地点がRより近い時には一度遠くを経由する必要があることに気が付きます。これも似た考察を昔なんかの問題でしたことがありました。知らないと誤差を疑ってしまいそう。

場合分けを追加して提出、一発AC！この時点で33位でした。

 

実際には適切な実装をすれば誤差で落ちることはないようです。

 

D - Send More Money

算数パズルの王者、覆面算ですね（？）

まず問題文が難しい。丁寧に読みましょう。文字が別なら別の数字が割り当てられるようです。ということは、文字が11種類以上出てくるものはそもそも構築不可能なことがわかります。

文字が10種類以下であるとき、O((文字の種類)!)の順列全探索が十分間に合いそうです。

keyを文字、valueを一意なidとする辞書dictを用意しておきます。

順列を表すperm配列をNextPermutationで回していきます。Sのi文字目にperm[dict[S[i]]]が割り当てられますね。

 各文字列を数字に変換して、計算して成り立つならそれを出力して終わりです。ある程度の自信を持って提出しました。

f:id:G4NP0N_kyopro:20210412001012p:plain

うげ！？

サンプルすら落ちているのでもう一度問題を読み直します。出力する整数は対応する入力と長さが同じである必要があるとのこと。つまり先頭が0のようなものは認められないのですね。

REは、10桁の整数が出てくるのに32bit整数で計算していたため。TLEは正直予想外だったので面食らいました。ここで順位表を見て簡単そうなEを通してから戻ってきたのですが、1桁目の計算が矛盾ないときのみ最後まで計算するように改善したところ、無事1300msでACできました。だいたい10倍くらいの定数倍高速化のはず？

おそらく、整数配列を結合して文字列に変換→再度整数に変換、という処理がかなり重たかったのだと思います。面倒くさがらずにきちんと計算しよう！

E - Unique Color

シンプルな問題設定ですね。C,Dの凶悪さに比べて、E問題にしては比較的素直です。

頂点1を根とした部分木とみなします。根から下っていったときに既に使用した色を管理しておきたい気持ちになります。これは、setで使用済みの色の情報を持ちながら深さ優先探索することで解くことができます。具体的には、ある頂点に到着したときに、その頂点の色がまだ使われていないなら答えにその頂点を追加し、setに色を追加します。その頂点を根とする部分木の探索が終了したらsetから色を削除します。再帰関数での実装がわかりやすいでしょう。

    public void Solve()
    {
        var N = io.GetInt();
        var C = io.GetIntArray();
        var G = io.GetUnweightedAdjanceyList(N, N - 1, false, false);
        var ans = new HashSet<int>();
        var used = new HashSet<int>();
        void DFS(int now,int from)
        {
            var added = false;
            if (used.Contains(C[now]) == false)
            {
                used.Add(C[now]);
                ans.Add(now);
                added = true;
            }
            foreach(var next in G[now])
            {
                if (next == from) continue;
                DFS(next, now);
            }
            if (added) used.Remove(C[now]);
        }
        DFS(0, -1);
        foreach (var v in ans.OrderBy(e => e)) io.Print(v+1);
    }

F - Cube

数学オリンピックか？っつってた。数字を色とみなすことで立方体の塗分け問題として考えていましたが、場合分けがまず10通りくらいあってそれぞれについて数え上げる必要があって、不可能でした……。

ACかなり少なかったですね。こういう問題もいつか解けるようになってみたいです。

 

そんなわけで

青色復帰です。一安心。

 

 

 

ABC196 参加記＆解法メモ

競技プログラミング コンテスト参加記 解法解説

f:id:G4NP0N_kyopro:20210321063231p:plain

97分5完でした。

atcoder.jp

 

A-Difference Max

2変数x,yの範囲が与えられるのでx-yの最大値を求めてね、という問題。

この手の変数の範囲が与えられて色々する問題はA,B問題などでよく出ますが、変数の境界を見ることで容易に解けることが多いです。

今回の場合は(xの最大値)-(yの最小値)、すなわちb-cが最大になりますね。とくに罠という罠もないです。

 

 

 

f:id:G4NP0N_kyopro:20210321064053p:plain

あれぇ！？

 

C#で出すべきところを間違えてPythonで提出していました……。

B - Round Down

やー、なぜか特定のWriterの顔が浮かんでくる問題だねー。

めっちゃ長い小数が与えられるから整数部を返してね、小数部の長さは0から100だよ、っていう問題。

入力を数値型として受け取るのは不可能（できる言語だとしても64bit浮動小数点数だと誤差が出る）ので、文字列として受け取る。

文字列内に'.'があればその手前まで出力し、なければ全部出力。

for文でチェックしながら出力するんでもよいし、'.'で文字列を分割して1つ目の文字列を出力するのでもよい。使ってる言語に応じてよしなに。C#ならX.TakeWhile(c=>c!='.')だけでいいですね。

 

ちなみに小数入力を文字列として受け取るテクニックは最近のコンテストでも何回か登場しているので、覚えておくのがいいと思います。decimalみたいな誤差の出ない数値型がある言語ならそれを使うのでもまあいいんですが。

A - Integer Product

C - Doubled

桁数が偶数であって前半と後半が同じ文字列でN以下であるような整数xの数を数えてね～、って問題。

N≤10^12なので全探索は不可能。必要条件から絞っていくのも筋が悪そう。

ここで、前半と後半が同じ文字列であるという条件に着目する。この整数文字列は10^6以下であるので、全探索が可能となる。1以上10^6以下の各整数について、2つ結合したものがNを超えないかどうか下から愚直にチェックしていけばよい。

D - Hanjo

これ難しいっすね……。最初問題斜め読みしてツルカメ算かと思った。

2×1の畳と1×1の畳を使ってH×Wの部屋を敷き詰める方法は何通りあるかな？っていう問題。

H×W≤16っていう制約の主張が強いので、bit全探索を初手思い浮かべるも、どう見ても面倒そうなので他の解法を考える。

これを思い出したけどどう見ても関係なさそうだったので記憶から飛ばす。

グラフとみなして探索もできそう。ただ、うまく状態を持ちながら探索する方法がパッと浮かばない。

他にもいろいろ考えたが、結局きれいに書けそうな方針が浮かばなかったので意を決してbit全探索で行くことに。

 

図のように、セルの境界となる辺に番号を割り振る。また、セル自体にも左上から数字を割り振る。

f:id:G4NP0N_kyopro:20210321074528j:plain

 辺の数NはH*(W-1)+W*(H-1)となるので、最大でも24本。これをbitで管理する。

i桁目のbitが立っているとき、その辺を跨ぐように1×2の畳が敷かれているとする。

1×2の畳が重なるときを考えると、セルを構成する辺のうちbitが立っている辺が2本以上あることがわかる。

f:id:G4NP0N_kyopro:20210321080344p:plain

よって、立っているbitがA個であり、セルを構成する辺のうちbitが立っているものが2本以上であるようなセルが存在しない部分集合の数を数えればよい。

 

セルの番号と辺の番号の対応は図のようになる。ただし、該当する辺がセルとの境界でない（外枠である）場合は飛ばしてよい。

f:id:G4NP0N_kyopro:20210321120645p:plain

ここの対応を正しく導出する部分で手間取ってしまった。添え字ガチャは悪い文化。

 

計算量がよくわからなくて不安だった。

最悪ケースはおそらくH=W=4かつA=8の時。bit全探索パートで2^24≒1.6*10^7個の部分集合を列挙し、そのうち24C8個で最大16個のセルについて4方向の辺の判定処理を行うので、そこは4.7*10^7くらい？ただ実際には枝狩りが相当効くはずなので、まあ間に合わんことはないだろうということで実装。提出してみたところ、155msと十分短い実行速度でACした。

 

ちなみにこの問題、DFSやbitDP,trit全探索(O(HW*3^HW))など、けっこういろんな解法があって面白かったです。想定もDFSでしたね。制約が小さい問題を筋肉解法で通すのも一種の実力だと思います。（TLを見ている感じだと僕の解法もかなり筋肉よりでしたけども……）

E-Filters

途中で状態が変わらない珍しいタイプのクエリ処理問題。いかにも前処理してからO(1)で解きたくなります。

以下、t=1,2,3の関数をadd関数,chmax関数,chmin関数と呼ぶことにします。

add関数がない場合を考えてみると、入力xに関わらず、chmax関数の最小値より小さい結果とはならず、またchmin関数の最大値より大きい結果とはならないことがわかります。更新が行われなかった場合は、入力がそのまま答えとなります。

また、add関数とchmin,chmax関数の合成を観察してみると、max(x+α,a)=max(x,a-α)+αという式変形が成り立つことがわかります。入力に関わらず、add関数で加算されたaだけ上下の境界が”ズレる”ということです。

よって、add関数でどれだけ加算されたかを記録しておく変数sumを初期値0で用意しておき、add関数ではsumにaiを加算、chmin,chmax関数ではaiからsumを引いたものとの比較更新を行う、という処理を前から順番に行うことで、ズレを考慮しながらchmax,chmin関数を適用することができます。

事前計算では、infと-infを代入して実際に計算する、もしくはchmin関数の最小値とchmax関数の最大値を求めることで上下の境界値が求まります。境界の外にある場合は境界まで近づけた値にsumを足したもの、境界に挟まれているもしくは境界上にある場合は入力にそのままsumを足したものが答えとなります。

上下の境界を求める部分で、上の境界が下の境界より小さくなることがありえる実装をしていたのに気が付かず、コンテスト終了直前までWAが解消できませんでした。危なかった……。

 

解法とクエリの中身、サンプルからなんとなく関数の形を想像できたのが大きいですね。

 

そんなわけで

直近7回のコンテストで6回目の青パフォです。安定してきて嬉しいな。

AtCoder青色になりました【自分語り ver】

競技プログラミング

すべてをお話しします。

これは何？

この記事はこれの自分語りバージョンです。色変記事ではないです。自己紹介のが近い。でも書き終わって見てみると「この1年を振り返って」みたいな感じなのかな。よくわからん。お気持ちポエムなので。

クソ長いです。そのくせ内容は薄いです。何もしていないのに一日が終わってしまって罪悪感に襲われて眠れない夜とか、マンガアプリで次の話を読むための無料広告を再生してるときとか、そういう虚無の時間の暇つぶしに読むのがいいと思います。

自分語り、就活の話、惚気要素、飯テロ等が含まれます。苦手な方はブラウザバックしてください。ここで警告したんだからTwitterで文句言ったりしたらやーよ？

 

 

 

 

 

 

 

 

 

 

 ポエム

AtCoder青色になったぜ！！！！！！

 

 

 

やかましいねこれ

 

 

 

 

いや～～～～～ようやく青になれた！！！！！！

本当に長かったよ……水色になってから10か月かかったらしい。

青に行くのが簡単じゃないのはわかってたよ？chokudaiさんだって「学生時代を競技プログラミングに注ぎ込んでも、ここにたどり着けない学生は大量にいます」って言ってたし、最近じゃコロナで暇になった東大生京大生東工大生ヤンキー中高生がゴロゴロ流入してきてるしさ。この1,2年でレートが大きく下がったり、きちんと精進してるのにずーっと停滞している人がいるのも知ってる。だからまあ、ちゃんと目標にしてた青になれた自分をきちんとほめてあげたい。俺、えらい！！！！！！最強！！！！！！！じーふぉーぽんたんは長いですから、天才とお呼びください。

 

でもやっぱさ、「プログラミング未経験から3か月で青になりました！！！！！」「コンテスト15回参加したら黄色になれたわ（笑）」みたいなバケモン成長速度の人を見てると嫉妬しちゃうよね。俺とアイツは何が違うんだって。上を見たらキリがないのは知ってるけど、やっぱ見ちゃうじゃん、上。そういう意味ではSNSって使い方間違えると本当に精神によくないと思う。Twitterを法律で禁止したほうがいいよ。

 

まあバケモンと比較するなっていうのはみんなが口を酸っぱくして言ってるし、実際そこまでダメージはなかったんだけども。「ライバルだと思ってた人たちが、気が付いたら先に色変してた」これがつらかったね。水色になったころにお気に入りした人たちが気が付いたらどんどん青になってるの。えっ、学生生活を競プロに捧げてもたどり着けないような場所じゃなかったんですか！？彼らはいったい何を捧げたんだろう。右腕と左足かな。等価交換は錬金術の基本だからね。

後に新しく始めた人たちもどんどん迫ってくるし。みんなすごいよ本当に。

 

一方で、鬼のような精進量なのになかなか結果が出ない、みたいな人もいて。彼らが色変したときは、本当にうれしかった。努力がきちんと報われているのを見て、ものすごく勇気をもらったよ。ありがとう。っつってたらもうすぐ下まで迫ってきて、もうちょいゆっくりでもいいんやで、という気持ちになるんですが

 

AtCoder青色になるまでにやったこと

1997年6月27日　生誕

伝説はここから始まりました。

皆さんもご存じのとおり、ここ日本では乳幼児を体重レートで呼ぶ習慣があります。出生時の平均体重が2900グラムであることから赤ちゃんと呼ばれることが多いですね。

僕の出生時体重は1793グラム。元気な青ちゃんでした。

2010年4月

算数パズルが得意だったので某校章がナワバリバトルみたいな中学に進学しました。繰り上げ合格だったけど。

スプラトゥーン2】ナワバリバトルの立ち回りと勝つためのコツ｜ゲームエイト

2013年

「変態王子と笑わない猫」というノーベル文学賞受賞作品を読み、感銘を受ける。昼飯を犠牲にオタクグッズを買い漁る日々。おっまた出てきたね、等価交換の法則。

筒隠月子ちゃんはいいぞ。カントク先生を推せ。

2016年 3月

なんか大学受験に全部落ちる。

2017年 3月

予備校をサボって秋葉原でjubeatしたりしつつもなんとか北大に受かる。北大後期、ガバガバなのでオススメです。

2017年 12月

人生初彼女ができる。今に至るまでずっと付き合っています。かわいいし賢いしめちゃくちゃ面白いしで本当に大好きです。結婚してくれ～～～

2019年3月

ちょっとしんどすぎることがあって生きる意味を見失う。

失意の底にある中、どういう経緯か思い出せないんだけど（？）AtCoderを始める。

AtCoderが楽しくて少し生きるのが楽になる。

chokudaiさんの色評価記事を読んで「水色になれたらいいな～。いやでも数学得意だし青もいけるか。俺は算数パズルで中学受験を勝ち抜いた男」とか考えてた。

 

いやほんとさ、この界隈の「数学が得意」の基準おかしすぎませんか？一応大学受験を数学で乗り切ったと自負しているんだけど、そういう次元じゃなかった。怖いよ、ほんと。

まあでも数え上げ問題とか解いててたのしー！！って感じられるからまだ適正があったほうなんだろうな……

 

あとはこの頃、小中学生向けプログラミングスクールの講師バイトを始めた。（伏線）

 2019年4月

↑のしんどさの原因が解消されたのでハッピーになる。AtCoderをやめる（は？）

2019年5月

就活開始。リクナビで「石油王」って検索したりしてた。

サポーターズの1on1イベントで1日で15社と面談したんだけど、これのおかげで就活うまくいったみたいなところある。マジで。面接は経験値ゲーなので、積めるときに経験積んどくのがいいわ。第一志望の本選考が初めての面接、とかはやめたほうがいい。

2019年夏

1weekインターン×3社行ったりしてた。優秀賞もらって選考免除とかになって浮かれていました。おめでたいやつ。

あとは千年戦争アイギスにドハマりしてた。スケベなかわいい女の子のイラストに釣られて始めたのに普通に面白くて困っちゃった。悔しい、でも遊んじゃうﾎﾟﾁﾎﾟﾁ

2019年12月

インターン先から内定が出る。就職活動おつかれさまでした。とくに競技プログラミングは役に立ちませんでした。

 

プログラミングスクールのバイト仲間が競技プログラミングをしていて、「そういやそんなんあったな」と思い出す。（鮮やかな伏線回収）

久しぶりに出たらパフォ402　これはマズいと思い、再開を決意。

2020年2~3月

実家へ1ヵ月ほど帰省。Twitterの競プロ垢開設したのもこの頃。

コロナウイルス対策の自粛という名目で、自室に引きこもって過去問の熱烈精進を進める。

 

3/1に緑到達。3/14に緑Diffを埋め終わっていたらしい。

当時は1問解くごとに時間を計測していた。水Diffの自力ACにこだわっていた。

 

2020年5月

入水

 

 ちなみに入水翌日にパフォ1882を出してさらにガツンとレートを上げたんですが、そこから最高パフォを更新するまで半年かかったらしい。長い長い停滞の始まり。

2020年6月

彼女が競プロを始める。今まで何度か布教していたものの、本当に始めてくれるとは思っていなかったのでびっくりした。

2020年夏

1日15時間くらいスプラトゥーンしてた。そりゃ競プロ強くなるわけねーわな。でもやめられねんだわ。

この頃はモミジと落ち葉使ってた　いやがらせブキしか勝たん。

 

あとは学生最後の夏休みということで、コロナウイルス感染対策に万全の注意を払いながら彼女とあちこち遊びに行ってた

f:id:G4NP0N_kyopro:20210318194838p:plain

f:id:G4NP0N_kyopro:20210318194857p:plain

f:id:G4NP0N_kyopro:20210318194903p:plain

f:id:G4NP0N_kyopro:20210318194913p:plain

f:id:G4NP0N_kyopro:20210318194137p:plain

f:id:G4NP0N_kyopro:20210318194921p:plain

 

f:id:G4NP0N_kyopro:20210318194930p:plain

f:id:G4NP0N_kyopro:20210318194938p:plain

f:id:G4NP0N_kyopro:20210318194949p:plain

 
画像貼ってたらめちゃくちゃ腹減ってきた……

2020年11月

青Diffを下から埋めてたと思う。あとはこの頃からJOI埋め始めた。

色変アドベンドカレンダーに登録して競プロモチベが高まる。

えすえふさんのこどふぉバチャに手を出し始めたのもこの頃。こどふぉにも参加するようになって元々終わっていた生活習慣が完全に破滅する。

Codeforces Anytimeすごくない？AtCoderにも欲しいな。

2020年12月

顔面を真っ青にしたりしていた。正直このネタを言うためだけにアドベンドカレンダー登録したみたいなとこあるんだけど、なんかこどふぉで青になれたのでそっちでいい風にごまかした。本当にごまかせていますか？

g4np0n-kyopro.hatenablog.com

 

あとは自分のツイートが元ネタとなって新しい競プロミームができた。

笑うわ

 

彼女とクリスマス＆交際3年記念ミニパーティーをした。楽しかった～！

f:id:G4NP0N_kyopro:20210318195202p:plain

 

除夜の鐘コンテストとか、競プロ流行語大賞とか、思ったより競プロ界隈の年末企画が充実してたのが印象的。来年も楽しみだな。

 

この頃から卒論発表の準備が本格化してきて、精神的にも競技プログラミングをできる雰囲気ではなくなっていた。モチベだけあって精進時間が取れない期間に入る。モヤモヤ。

かわりに隙間時間でスプラトゥーンを遊んでいた。若葉シューターをメインブキにしてみたら3日でガチエリアXいって面白かった。

2021年1月

 卒論準備がピークに。それと並行して引っ越しの準備も進める必要があり、かなり大変だった。

 愉快な絵面だなあ……

 

精進量もガクンと落ち、月に2回も緑パフォを取ってしまった。10月以来の緑パフォに、だいぶ凹む。

 

卒論発表を1週間後に控えた1/31、とびきり旨い鮪を食べてから北海道を発つ。今までお世話になりました。

f:id:G4NP0N_kyopro:20210318195826p:plain

f:id:G4NP0N_kyopro:20210318195831p:plain

2021年2月

卒業論文発表。一番手でけっこう緊張したが、素人に刺されることもなく無事発表を終える。ちなみに卒論タイトルは"行列の繰り返し二乗法を用いた気体中電子速度分布緩和過程計算 -直流電界下技術実証-"でした。そう、みんな大好き行列累乗。月刊競技プログラミングは卒業研究の役に立つ。

 

卒論発表終わった勢いでコンテストに出たら初めての黄パフォをたたき出す。

まあ明らかに普段のABCとは違う雰囲気のセットだったね。某pro_friendsのおかげで誤差問題への耐性が付いていることを自覚したよ。ありがとう某pro_friends……

 

卒論発表が終わったので、令和ABC-Eと令和ABC-青を埋めることに。

あとはこどふぉバチャもけっこう走ったかも。

 

2021年3月1日
  • こどふぉ紫になる。

 色変記事書くって言ったのに書かなくてすみませんでした……（懺悔）

f:id:G4NP0N_kyopro:20210318202934p:plain

 こどふぉの実力、下ブレしてると思ってたんだけど、Codeforces Anytimeの結果をみるに適正でしたって感じがする。グラフの形状が完全に一致していて面白い。

 

  •  kenkooooさんからPAST本の献本をいただく。

実は本が届く直前にDMでやりとりをしていたんですが、

G「ちなみに献本をいただけることになったのはAtCoder Problemsのsponsorになっていたからでしょうか？それとも偶然でしょうか？」

G（いや偶然なわけないか。sponsorだからだよねえ）

k「偶然です！」

いや偶然か～い！！！！！

k「G4NP0Nさんが読んで役に立つ点もあると思ったことと、もしかしたら読むかもしれないG4NP0Nさんの彼女さんが、本書のメインターゲットである『プログラミング初心者でアルゴリズムに関心がある人』である可能性が高いためです！」

これ、すごく嬉しくないですか？献本を誰にあげよう？と考えた時に、こうやって思い出してもらえたっていう事実にかなり感動しました。推しからの認知、それだけで俺たちは生きていけるんだ……。

さて、肝心の中身ですが……

 

ものすごく良いです。

アルゴリズムとは？という導入から始まり、pythonの文法を深堀りしすぎない程度に解説したのち、様々なアルゴリズムの説明に入っていくんですが。

もうね、競技プログラミングの入門書としての親切度がすごいです。

ABC-Cくらいの難易度の問題にも、見開き3ページくらい使って丁寧に丁寧に議論を進めています。かといって本当に簡単な問題だけでなく、終盤にはPASTのM問題も同様に丁寧な議論を踏みつつ解説しています。これとけんちょん本だけで充分水色を目指せるレベル。

そういうわけでpythonで競技プログラミングをやっているあなたと競技プログラミングを始めようと考えているあなたと競技プログラミングで使えるサブ言語を用意しようと考えているあなた！！！！PAST本を買おう！！！！！！！

www.amazon.co.jp

 

それと、お財布に余裕がある方はAtCoderProblemsのsponsorになりましょう。

石油王の方は1億円寄付しましょう。

github.com

2021年3月3日

抽選に当たっていたらしく、シンキングサプリが自宅に届いていました。

 一応きちんと毎日飲んでいるんですが、体感としての変化はあまりありません。ただ、実際色変できていたり、AHC001でなんかそれっぽい成績残せたりしているので、思ったより効果はあるのかもしれない。あとは臭いが少しキツい。

 

正直サプリが家に届いた時点で、3月中に色変できるのを確信していた。だってツキすぎてるもん。宝くじとか買っておけばよかった。

2021年3月6日,7日

ABCはDのド典型期待値問題で時間を溶かした。これさんざんやったやろなんでできないねん。でもE問題をシンプルなセグ木解法で通せたので全体では微冷え。耐えた。

AGCはAの1完で青パフォ。そんなことある？こどふぉで鍛えたギャグパワーが猛威を振るうぜ！Bは何もわかりませんでした。

2021年3月12日

37.3℃の熱と激しい頭痛に襲われる。

数日前に久しぶりに遠出していたこともあり、コロナか！？！？と家族が騒然となる。

近くの病院を受診。

 PCR検査も陰性でした。

 

あとは人に教わりながらセグ木の二分探索を理解した。

2021年3月13日

パナソニックプログラミングコンテスト（AtCoder Beginner Contest 195）にてパフォ1858獲得、青色到達。

2021年3月14日

AtCoder Regular Contest 114にてパフォ1745獲得、青色維持

直近6回のコンテストで5回が青パフォなので、まあ青色適正ということで色変記事書くか～ってなる。

2021年3月15日

かわいすぎて気がおかしくなりそうだった。

 

最後に

AtCoder最高！！一番好きなネトゲです！！

AtCoder青色になりました【マジメ ver】

競技プログラミング

 

 

 

 

 

少女解答中

        NowSolving…

 

 

 

 

 

 

先日行われたパナソニックプログラミングコンテスト（AtCoder Beginner Contest 195）にて、AtCoder青色になりました！！

atcoder.jp

 

競技プログラミング界隈ではAtCoderの色が変わったときに色変ブログを書く慣習があるので、それに乗っかっていきます。AtCoder水色になったときには記事を書いていなかったので、色変記事を書くのはCodeforces青色になったときのものに引き続いて2本目ですね。

g4np0n-kyopro.hatenablog.com

 

AtCoderで初めての色変記事だしお気持ちポエムとか自分語りとかして～～～～～って思ったんですが、普通にAtCoder青色を目指す参考にしようと思ってアクセスした人に自分語り読ませるのは申し訳ないので、記事を分離することにしました。この記事はマジメ verです。自分語り verは暇すぎて脳みそが溶けそうなときとかに読んでください。

 

青色になるまで

f:id:G4NP0N_kyopro:20210317182215p:plain

AtCoderを始めたのは2年前なんですが、茶色になってから1年弱ほとんど参加していませんでした。(この期間の精進量はほぼゼロです）1年ちょっと前くらいに再び参加するようになって、きちんと精進をするようになったのもこの頃からです。

余談なんですが、2年前の茶色になったときは一切のアルゴリズムの勉強をしていなくて、全探索と算数っぽい何かだけで茶色中位まで行きました。今のレベルからすると信じられないですね。

 

f:id:G4NP0N_kyopro:20210317182548p:plain

コンテストごとのレートとパフォーマンスの推移はこんな感じ。春休みをすべて捧げた結果、緑になってから2か月、回数で言えば10回くらいで水色に到達できていました。この時は完全に調子に乗っていて「ま、すぐに青にもなれるだろうし色変記事はまだいいや」とイキり散らかしていたんですが、結果的に青になるまで10か月かかりました……。

水色になってからのレート推移は、今見てみると線形に見えるものの、当時はかなり停滞感がありました。特に1300~1400は相当しんどかったですね。

ほかの青になった人を見ていると色変間際には黄パフォや橙パフォを何度もたたき出している人が多いようなんですが、自分は結局パフォ1900越えが2回しかありませんでした。よく青色になれたなあ。

 

競プロ環境

使用言語はC#です。Visual StudioをWindowsノートPCに入れてコーディングしています。ディスプレイにHDMI接続してデュアルディスプレイにしています。競技プログラミングはマシンパワーをそこまで必要としないのでいいですね。重い重いと言われがちなVisualStudioも、メモリ8GBで十分動いてくれます。C#を使っている理由は親だからです以前から使用していて手に馴染んでいたからですね。あとはVisualStudioのリッチな開発環境に慣れてしまったからというのもあります。

また、競プロ用にiPad miniを購入して考察ノート替わりにしています。Apple Pencilひとつで複数色のペンと消しゴムを兼ねられる、方眼紙と白紙の切り替えが自由で直線や円なども容易に描画できる、携帯性が高く場所を問わず問題の考察ができるなど、競プロとの相性は抜群です。


AtCoder青色になるまでにやったこと

AtCoderの過去問精進

定番ですね。AtCoder Problemsで見れる情報をいくつか張ってみます。

f:id:G4NP0N_kyopro:20210317181413p:plain

f:id:G4NP0N_kyopro:20210317181643p:plain

f:id:G4NP0N_kyopro:20210317181703p:plain

f:id:G4NP0N_kyopro:20210317181838p:plain

 AC数は青到達者としては並かやや多いくらいだと思います。虚無埋めがけっこう占めてる割合多いので。

見てすぐに解けてしまう難易度の問題を埋める、いわゆる虚無埋めはっこう賛否が分かれるところですが、自分は音ゲーのいわゆる低難易度埋めを楽しめるタイプ（そして高難易度特攻が得意でないタイプ）なので、とくに抵抗感なく進めていました。ただ、脳死でやるだけではもったいないので、意識的に「どうやったら最もシンプルに解けるのか？」みたいなことを考えながら埋めていた気がします。

 

水色到達以降は「まずは水Diffを全部埋める！」というモチベーションで精進をしていました。最終的にはAGC数問を残して埋め終わるところまでいきましたが、レート最大化という点からみるとあまり効率がいい方法ではなかったと思います。

単純にレート最大化を目指すならば、流星のごとく現れた期待の新星、Rcoderさんの色変記事が本質だと思います。

seashellpink-frostywhite.hatenablog.com

ただし、精進がレートに反映されるかどうかは運も絡んでくるので、レート最大化だけを重視した精進はモチベーションの維持がなかなか難しいです。なので、〇色まで埋める、RPS△点を目指す、streakを伸ばす、そういったレートとは独立した目標を設定すると、長期的なモチベーションとして機能すると思います。

 

青Diffを意識して埋め始めたのはレートが1500に乗ってからくらいでしたね。それまでもちょいちょい解いてはいたんですが、解けそうな問題だけ解いたりしていたので、精進としての効果は非常に薄かったと思います。やっぱり青に上がることを意識して青Diffを解くのは非常に効果的でした。令和ABCの青Diffを全部埋めたんですが、とても学びが多かったです。

 

コンテストに参加する

当たり前ですが、大事です。

2020/1/18のキーエンスプログラミングコンテスト2020以降,引っ越しの準備で参加できなかった2回を除きすべてのratedコンテストに出場しています（たぶん）

Problemsでざっと見た感じだと、1問目から解けなかったAGC044を除けば、NoSub撤退もARCで1回あったのみでした。

コンテストに出ることが最も時間効率のいい精進だという話もありましたね。誰が言っていたか忘れましたが。

ちなみに、個人的には現行ルールにおける潜伏は問題ないと考えているのでARC,AGCで潜伏することは結構あったんですが、結果的にだいたい提出に至っていました。ABCの潜伏はマジで無意味なのでやめたほうがいいと思います。

 

Codeforcesのコンテストにも参加していました。こちらはアドホック要素が強めなので、考察力や発想力を鍛えるいい練習になったと思います。特に数列操作とグラフの問題が多め。ABCよりはARCで効果が出ると思います。ABCで青を目指すだけなら必要ないかもしれません。

 

バチャに参加する

みんな大好きバーチャルコンテスト。僕も大好きです。大きく分けてAtCoder Problemsを利用したAtCoderの過去問バチャとCodeforcesの過去回の2つがあります。

目的に応じて参加するバチャを選ぶのがいいと思います。バチャに片っ端から参加してしまうバチャ中毒みたいな人も多いですが……

オススメのバチャを軽く紹介しておきます。バチャの名称は適当です。

  • くじかつ　

    TERRYさんがAtCoder Problemsで毎日21時から主催しています。難易度傾斜が程よく、ABC対策として一番効果的だと思います。

  • えすえふバチャ　

    えすえふさんが主催している21時からのCodeforcesバチャ。こちらも参加者が比較的多く、感想戦で盛り上がっていますね。

  • Moringforces　

    タイヨウさんが主催している朝7時半からのCodeforcesバチャ。起きる部分が最難関ですが朝からバチャに参加すると一日をいい感じに競プロ漬けにできます。これの常連メンバーはきちんとみんなレート上げてるな～って感じ。

  • かいけーバチャ　

    異常バチャ精進の王かいけーくんが不定期にCodeforcesバチャを開催しているので目についたら並走しています。

  • poyoさんバチャ

    期待の新人バチャジャンキーことpoyoさんがAtCoder Problemsで不定期に開催しています。最近は23時から開催が多い？

AtCoderバチャを復習用に、Codeforcesバチャを考察力訓練に使うのがいいと思います。Codeforcesバチャは正直あんまり復習まで手が回らないことも多かったんですが、なんだかんだ効果はありました。

 

EDPCを解く

フォロワーの熱心な布教により解き始めました。DPはけっこう得意だと思っていたんですが、典型を忘れていたことが発覚したり、期待値DPが大の苦手であることを把握できたり、高度典型DPの概観をつかむことができたりと、非常に大きな成果がありました。

青になれた回のE問題もEDPCの応用問題でした。ありがとうEDPC。

まだ後ろ数問をACしていないので早いうちに埋めたいですね。TDPCにも手を出してみたい。

 

データ構造/アルゴリズムの勉強

これは人によって進め方がかなり異なると思います。茶色でセグ木やったり緑で全方位木DPやってるバケモノも中にはいますが、自分は精進を進めるうえで必要になったら用意する、くらいのノリでやっていました。蟻本とかも全然読み進めていない……。

自分は抽象化が好きなので、よく典型のデアを抽象化して遊んでいました。セグ木なんかはみんな抽象化していると思うんですが、ダブリングやLISを抽象化しているのはけっこうレアなんじゃないかと思います。抽象化をすることによってそのデアへの理解はかなり深まったので、オススメです。

自分は青コーダーとしてはデアの履修率がかなり低いはずなので、まだ自分のものにできていないものを列挙しておきます。これらができなくても青色になれる！！！（コラ）

  • 遅延セグ木　一応持っていたんですがバグっていました
  • 全方位木DP　1回だけEDPCで解いたけど、まだ経験値が圧倒的に足りないです
  • 文字列アルゴリズム各種　Z-algorithmとかロリハとか。ABCで使わないから……
  • フロー　Dinicを一応持っているので重み無し最大二部マッチングは何度か解いたんですが、他はからっきしです。
  • ベルマンフォード法　使う機会なくない？一応仕組みはわかってると思うけど空で書けない気がする
  • Binary Index Tree　セグ木でよくない？＊よくないです
  • 平方分割　やらないとと思いながら一生後回しにしています
  • 強連結成分分解　AGCで必要になったときに計算量酷いやつを再発明しました。
  • FFT,NTT　名前だけ聞いたことがあります。
  • FPS　スプラトゥーンなら得意です。

 

開発

たぶんやらなくてもいいと思います。でも楽しいのでやりました。

これとかこれとか作りました。ぜひ使ってください。

 

CodinGame

たぶんやらなくてもいいと思います。でも面白かったのでやりましょう。

 Twitter

たぶんやらなくてもいいと思います。でも楽しいのでやりました。

ライバルが精進している様子を見てモチベーション上げたり、疑問点を放流したりして強い人が教えてくれたりします。いやこれやったほうがいいな。みんなTwitterをしよう！

 

AtCoder青色になって

AtCoder青色は、競技プログラミングを始めた際の最も大きな目標でした。

「大学在学中に青になりたい！！！」という思いをずっと持っていたので、なんとかギリギリ目標を達成できたことに安心しています。

 春から社会人となりますが、これからも競技プログラミングへの情熱を絶やさずにいきたいなぁ。次の目標はAtCoder黄色です。遠く険しい道のりですが、くじけずに頑張っていきたい！