【色変記事】Python で AtCoder 橙になりました

とりゐです．先日に橙色になりましたので，それの報告記事です．

自己紹介

  • 大学四年の理系大学生
  • 大学に入るまでプログラミング経験無し
  • 大学一年の七月に競プロを初めた．競プロ歴は 2 年 10 ヵ月ほど

精進記録

記録は全て 2023 年 5 月 31 日時点のものです．

Rating Graph
Competition History
Achivement
AtCoder Pie Charts その 1
AtCoder Pie Charts その 2
Difficulty Pies

橙になるまでにやったこと

ARC/AGC 埋め

黄色までは ABC でレートを稼げるため，典型さえ押さえておけば戦えますが，黄色以降はそうはいきません．考察力を鍛えるために，特に黄～橙 diff の問題を重点的に埋めていきました．

Codeforces に出る

黄色になってから，Codeforces に積極的に出るようになりました．Codeforces に出る目的はいくつかありますが，その中でも特に，コンテストは（過去問埋めと違って）制限時間があるので，その中での立ち回り方を訓練できるのが大きいと思っています．

作問をする

たくさんしました（TUPC, yukicoder など）．入橙になるのに作問がどれだけ寄与したかはわかりませんが，作問をする過程でいろんなことを考えたりするので，そこで考察力を鍛えられたと思います．（TUPC のボス問全然解かれないで悲しいので解いてね！）

atcoder.jp

その他細かいこと

解説を読む

解説は結構ちゃんと読むようにしています．コンテスト中は正当性の確認とか式の整理とかがちゃんとなされないことが多いので，それの確認をしたり，あるいは解説をみて新たな考え方を得たりしています．snuke さんの動画による解説は思考過程が丁寧に解説されているのでよく見ています．おすすめです．

他の人の提出を見る

Python は書き方によって定数倍に大きく差が生じます．Python で実行速度が速い人の提出を見て，どのような書き方が良いのかとか，自分の書き方のどこが良くなかったかをよく確認しています．

デバッグ力をつける

コンテスト中に WA が出て，落ちるケースが思い当たらないときなどは，愚直解と書いてランダムケースを回して比較するようにしています．以前は WA が出たときに落ちるケースを考えたり手作業で探すなどしていたのですが，自分はそれが苦手だと気づいたので，愚直を書いてぶん回すようにしました．これによって救われたことが ARC で 5 回くらいあります．愚直を書くのなんて 5 分もあればできるので，困ったときは躊躇せずに愚直解を書いています．

Python で競プロをやることについて

Python はそこまで有利でもない

Python のメリットとしてコード量が少ないということがしばしば挙げられると思います．これは，初心者にとっては有利になりうると思います．ある程度実力がついて，マクロを作ったりその言語の書き方に慣れたりすれば，このメリットはそんなに有利には働かないと思っています．

Python は AtCoder においてはそこまで不利でもない

AtCoder の問題は遅い言語にも配慮されて作られていることが多いと感じます．私が手を付けた AtCoder の問題のうち，Python だと解けないけど C++ なら解けたという問題はなかったと記憶しています．特に，ARC/AGC は考察に重きが置かれているため TL がきつく設定されていることが多く無く，言語の速度の差異による不利はほとんどないと言っていいでしょう． ただ，想定解でも高速化をめちゃくちゃ頑張らないと通らない問題（ABC258G や ABC274F）や，想定解の計算量に log 一つつけた解法が通らない問題（AGC057B）もあるにはあります．高速な言語による非想定解法を落とすためなので仕方がないですね．でもそんなことは非常にまれなので，Pythoner はそんなに気にしなくて良さそうです．とはいえ，他の言語だと AC できたのに...となると悲しいので，私は c++ を少しずつ勉強していて，Python でダメだったときは c++ に書き換えられるようにしています．

なお，"AtCoder においては" と書いたのは，海外のコンテストでは Python では到底不可能な問題が普通に出題されるからです．あきらめましょう．

なぜ c++ に移行しないのか

c++ を勉強するか，過去問埋めの精進をするかで得られるものを比較したときに，後者の方が得られるものが多いと判断したので，前者の方にはあんまり時間をかけていません．前述したように，Python から c++ に書き換えられる程度で現時点では十分かなと思っています．

今後について

AtCoder 橙になることが割と最終目標だったりしたので，目標がなくなってしまって困りました．赤になりたいとはあんまり思っていません（不可能だと思っているので）．競プロをやること自体は楽しいので，当分は目標を作らずにだらだらやろうかなと思います．あとは ARC W も機会があればやってみたいですね．

MMA Contest 015 J : Maximum Quadrilateral

問題

xy 平面上に N 個の点がある．4 つの点を選んで四角形を作るとき，その面積を最大化せよ．

O(N^3) 解法

N 個の点の凸包上の点を反時計回りに C_1,C_2,\ldots,C_M とします( M は凸包上の点の数)．このとき， M=3 の場合は，（凸包の 3 点） + (それ以外の 1 点) で四角形を作るのが最適です．よって， O(N) かけてすべての候補を調べればよいです．

以下では， M\geq 4とします．このとき，面積が最大となるような四角形の頂点は全て凸包上にあります（凸包上に無い点を含むとき，適切に凸包上の点に変更することで面積を大きくできます）．

四角形の対角線をなす点を C_L,C_R(1\leq L,L+2\leq R\leq M) で固定します．このとき，残りの二点の候補は C_i (L\lt i\lt R) と C_j(R\lt j\lt L+M) （C_i と C_{i+M} は同一視する）になるので， \triangle C_LC_RC_i,\triangle C_RC_LC_j の面積が最大になる点それぞれを O(N) で調べればよいです．対角線の候補は O(N^2) 通りありますから，全体で O(N^3) で解くことができました．

O(N^2 \log N) 解法

対角線をなす 2 点 C_L,C_R を固定したとき，\triangle C_LC_RC_i,\triangle C_RC_LC_j の面積はそれぞれ i,j に関して凸になっています．よって三分探索をすることにより，各対角線ごとに O(\log N) で求めることができます．

O(N^2) 解法

C_L を固定します．このとき，\triangle C_LC_RC_i が最大となる i は R に関して単調増加になっています．よって尺取り法の要領により，各 L に対して，すべての R に対する \triangle C_LC_RC_i の最大値を O(N) で求めることができます．

CODE FESTIVAL 2017 qual A : D - Four Coloring

問題

H,W,d が与えられる．次を満たすように H\times W のマス目を 4 色で塗り分けよ．

  • マンハッタン距離が d であるような任意の二つのマスについて，それらの色は相異なる

解法

2 つのマス (x_1,y_1), (x_2,y_2) が |x_1-x_2|+|y_1-y_2|=d を満たすとき， (x_1+y_1)-(x_2+y_2)=\pm d または (x_1-y_1)-(x_2-y_2)=\pm d を満たしている．よって

  • (x_1+y_1)-(x_2+y_2)=\pm d のときマス (x_1,y_1), (x_2,y_2) の色は相異なる
  • (x_1-y_1)-(x_2-y_2)=\pm d のときマス (x_1,y_1), (x_2,y_2) の色は相異なる

ようにすればよい．

1 つ目の条件は 2 つの色をつかって塗分けられる．具体的には， (x+y)\%2d が d より小さいか否かで色分けすればよい．

（ H=W=15, d=4 の例）

111100001111000
111000011110000
110000111100001
100001111000011
000011110000111
000111100001111
001111000011110
011110000111100
111100001111000
111000011110000
110000111100001
100001111000011
000011110000111
000111100001111
001111000011110

同様にして，2 つ目の条件も 2 つの色をつかって塗分けられる．

200002222000022
220000222200002
222000022220000
222200002222000
022220000222200
002222000022220
000222200002222
000022220000222
200002222000022
220000222200002
222000022220000
222200002222000
022220000222200
002222000022220
000222200002222

これらを組み合わせればよい（上二つのマスの数を足せばよい）．

311102223111022
331000233310002
332000133320001
322201113222011
022231110222311
002333100023331
001333200013332
011132220111322
311102223111022
331000233310002
332000133320001
322201113222011
022231110222311
002333100023331
001333200013332

4 色で塗り分けるというのを，2 通りの 2 色の塗り分け方を組み合わせて考えるというのは AGC にも出てましたね．

TUPC 開催記

2023 年 3 月 4 日に東北大学プログラミングコンテストをオンサイトで開催しました．その記録です．

 

コンテストまでのできごと

TUPC2022 始動

去年サークルで TUPC2021 を開催して結構うまくいってたので，今年もやろうという話がずっと前から出ていました．去年の 8 月頃にサークルの slack で TUPC2022 の writer の募集がかかったので名乗り出ました．僕のほかに sota 君と kari 君と milk さんが writer に名乗り出ました．writer のほかに tester としてこたつがめさんが，運営面の手伝いとしてホスフィンさんが加わり，計 6 人で TUPC2022 を運営することになりました．

 

問題準備

始動してしばらくは問題をひたすらみんなで産みました（9~12 月）．誰かが問題を産んだら，それ以外の 3 人の writer のだれかがまずは問題をチェックするという形式を（基本的に）とりました．各問題ごとの議論とかは discord のチャンネルを生やして行いました．

 

問題文や解説，コードを共有/保存するのは github で行い，テストケースを作って実際にジャッジするのは rime という機能を使いました．rime を使うのは sota 君が提案してくれたもので，彼が rime の使い方を非常にわかりやすく説明した資料を作ってくれたので作業がスムーズにできてとても助かりました．

 

合わせて，今年はオンサイトでやりたいねということ，AtCoder を借りてやりたいねという話をすこしずつしてました．

 

オンサイトの準備

オンサイト開催について，とりあえず Twitter でアンケートを取って聞いてみようということになりました．35 人が「行きたい」に入れてくれており，ある程度人が集まることが見込めたためオンサイトをやる方向で決定しました．

 

 

オンサイトでやることが決まったら，会場探しをしました．まずは仙台市にある貸会議室を探してみましたがあんまりいいところが見つからず，お金がかかるくらいだったら東北大学の適当な場所を借りてやろうということで，サークルの顧問の先生にお願いして大学で借りれる場所を探していただきました．結果としてこの判断が良く，広い会場を無料で借りられることができました．WiFi も貸していただきました．

 

AtCoder のサイトの準備

AtCoder のサイトを借りることについて，chokudai さんの過去のツイートをさかのぼってみると，AtCoder で有志コンを開くための条件として ①橙以上が問題をチェックする ②writer/tester が黄色以上 という 2 つを課しているツイートがありました．幸いにも東北大には赤コーダーのこたつがめさんがいてくださるためこれらの条件を満たしており，とりあえず chokudai さんに DM してできるかどうか聞いてみようということになりました．AtCoder 側から，こたつがめさんがいるなら問題ないだろうということでコンテストページをいただけることになりました．

 

 

ただ Atcoder で開催するにあたって，運営陣がだれも Atcoder でバイトをしていないので，問題文を上げたりテストケースを登録したりする方法を誰も知らないという問題点がありました．そこで，昨年 TTPC を開催していて，かつ AtCoder での writer 経験もある tatyam さんにお願いして，テストケースの登録方法とかを 1 時間くらい zoom をつなげて教えていただきました（後で知ったことだったんですが，教えてもらった日が tatyam さんの誕生日だったらしく，人の記念日の貴重な時間を奪ってしまって申し訳ない気持ちに...）．このとき，オンサイトの運営のことについても少し話をしてくれました．tatyam さんのおかげでかなりのことが助かっていて，ありがたい限りでした．

 

コンテスト 2 ヵ月前～

今年の 1 月中旬くらいにはすでに問題のセットが完成し，この頃あたりから全体 tester のこたつがめさんにも作業をお願いしていました．その時期にコンテスト時間とチーム制限を議論しており，当初私はこのセットは簡単だと思っていたので(え？) 4 時間かつレート制限ありでよいと主張してしました．

 

1 月 30 日にオンサイトでやることを告知し，conpass での募集を開始しました．私は当初 20 人も集まらないんじゃないかと思っていましたが，これも見積もりが下手で実際のところは 43 名もの方にオンサイト参加していただきました．

 

コンテスト開催のちょうど一か月の 2 月 4 日にコンテストページを公開し，2 月 5 日から heno さんに作業を開始していただきました．heno さんの解く様子を見ていると，私が見積もっていた問題の難易度がバグっていることに気づき，正気を取り戻しました．今更コンテスト時間を変えるということは難しいので，せめてもということでチーム制限は撤廃されることになりました．

 

2 月の中旬には，私が名札を作る担当になったので作っていました．TTPC の名札がすごいおしゃれで，そんな美術センス私にはないよ～～とかいいながら，恥ずかしくないような最低限のシンプルな名札を作りました．作った当初はあんまりピンときてませんでしたが，実物を見てみるとまあまあよかったのかなと思っています．

 

 

残りの 2 週間は問題文や解説のチェックをずっとしてました．コンテスト前日にはこたつがめさんが細かいところまで隅々チェックしてくださり，そのおかげもあって（誤読によるものを除いて）コンテスト中は clar が一つも来ませんでした．

 

コンテスト当日

当日，コンテスト開始までは会場でこれといってやることもなく，適当に人々を案内してたりしてました．コンテスト中は人々の提出や順位表をひたすら眺めてたらあっという間に 4 時間たってました．解説会をやって，渾身の懇親をして，そのあと牛タンを食べました．いろんな人とおしゃべり出来て楽しかったです．

 

問題について

全体的な話

問題案を投げられた段階でどの問題も面白くて，tester をしていてとても楽しかったです．クオリティも高く，ARC に出しても遜色ない問題が多かったんじゃないかなと思っています．コンテスト後にはいろんな方から面白いセットだったと言っていただき，うれしかったです．分野も偏りなく出せていたんじゃないかと思っています．atcoder-standings-difficulty-analyzer による diff 推定によれば，4 人全員とも銅以上の難易度の問題を生やしていて，これもすごい．あとは，実装がつらい！みたな問題が少なかったのもよかったと思います．

それぞれの問題の感想とかを書いていきます．

!!!ネタバレをかなり含むので，まだ解いてない問題がある方はお気を付けください!!!

A. Sum Sort

tester しました1．2 分くらいで解けてたかな？シンプルだし 1 問目にちょうどいいね～～と言っていたけど，実力者でも WA を出してる人がちらほらいたみたいで，1 問目に置くには難しめだったっぽい．来年はもっと簡単なのを置きたいね．

 

B. Snowy Aobayama

tester しました2．10 分くらいで解けたと思ったらそのときのサンプルが弱くて 1WA しました（サンプルが優しくないねと言ったら，自分がその罠にはまっていた．アホ）．大学有志コンでよくありがちな，その大学にまつわる問題を簡単枠として出したいねという話があって作ってくれました．やることはそんなに難しく無くて，ABC-C/D くらいだと思ってたけど，この問題も 2 問目にしてはあまり解かれなかったですね．簡単枠の調整難しい...


C. Flip Grid

tester しました3．最初に問題を渡されたときは，グリッドは '#' と '.' で与えられるものだと思い込んでいて，O(HW) で解きました（これも 10 分くらい）．そのあと milk さんに O(黒のマス) で解けるといわれたので H,W,N<=2*10^5 にする今の形式を提案しました（こういう，制約の調整とかを提案とかするのが，共同作問っぽくていいですね）．問題の見た目がいかにも milk さんの問題って感じがして，解法がシンプルで面白かったです．

 

ここまでが Welcome 枠でした．この時点ですでに難易度を見誤っており，やばい！

D. Zeta Sum

横で見てました1．実は自力で解けませんでした．数式を見ていかつすぎ～とか言ってたら全然解けなくて，答えを見ました．こういうのは展開しないとダメですよねぇ．この問題は D に置かれちゃダメだろとはずっと思ってたけど，そうなると後ろの問題をを削って前に簡単枠を追加しなきゃいけないことになり，いろいろ面倒なことになるのでこのまま出すことになりました(当然正解者数が大変なことに...)．

 

E. 00-11 Rotation

tester しました4．30 分くらいで解きました．milk さんは転倒数を出しがちという偏見があった（多分ゆきこで出してた転倒数が印象に残っているせい）ので，転倒数とかかな～ってエスパーしたら解けました．この問題は，答えが転倒数になることの証明が結構大変で，writer 4 人でみんなで考えてました．

この問題は 10 月に提案されていました．1 月に diff 予想をしたときには，解いたときから時間がたっていたのもあってこの問題はすぐ解けたものだと思い込んでいたらしく，diff は 1200 だと主張していました．30 分もかかっていたことに気づいたのはコンテストが終わってからで，自分でも 1200 と主張していたことに驚いています．作問作業に長い間携わっているとバイアスがかかってしまって正常な判断をするのが難しいですね...．D>E とも主張していました（D：解けない，E：解けた　だったので...）．

 

F. Block Rotation

tester しました5．考察・実装共にそこそこ時間がかかった気がします．高々 2 回の回転で元の形に戻るというのになかなか気づけず，サンプル 4 をお絵描きして気づけました．実装はちょっと大変だけど，やること自体は難しくないと思って diff 1600 を主張していましたがこれもはずれ．この問題の元ネタが万華鏡ってのを聞いて確かに～～となってました．

 

G. All Pairs

writer しました1．完全グラフで遊んでたら思いついた問題です．もともとの想定解は場合分けをして実際に構築していくもので，これが結構面白いと思っていました．オイラー路を再帰的に構築するアルゴリズムを後から知って，このアルゴリズムを知ってるとどこに辺を追加するかさえわかれば貼るだけの問題になってしまってちょっと悲しい気持ちになってました．でもまあ辺を追加する場所はそんなに自明じゃないと思ってそのままだしました．

答えは偶奇によって変わるので，提出デバッグがされないようにするために AGC061B の形式をパクってマルチテストケースにしてみました．一応 O(N^2) でも解けますが，O(N^3) でも pypy で N=1000 が 3000ms になって区別が難しかったので O(N^3) を許容しました．実装が短くできるのがお気に入りポイントです．

解説スライド用に gif を頑張って作ったのでここにも貼っておきます（N=5, 6 のときの構築方法です）．

 

H. Next Permutaion

writer しました2．階乗進数の問題を作りたくて作りました．特に言うことはないです．個人的にはあんまりおもしろくないと思っていたのですが，tester の sota 君がおもしろいと言ってくれたので出しました．

 

I. Count Setwise Coprime

writer しました3．約数・倍数系の問題かつ数え上げの問題を作りたいなーって言ってたら生えました．見た目がシンプルで気に入っています．解法については，多くの人は数論関数の累積和で通してくるんだろうなあと予想していて，実際にそうでした．想定解 1 の方は ABC-Ex で一回出ていて，実装も軽いしコンテスト時間も 4 時間あるので，ABC の問題が橙中位であることを踏まえると黄色上位とかになると思ってましたが，思った以上に難しかったみたいです．この問題も実装が短くて気に入っています(こたつがめさんの提出を参考にしたら python で 24 行になりました)．

 

ちなみに，今回の問題は Setwise Coprime の数え上げでしたが，Pairwise Coprime の数え上げは ABC で出てます．こっちは R-L がどれくらい大きくしても解けるんだろう？（全然考えてない）

atcoder.jp

J. AMidA

tester しました6．これ今回のセットで個人的に一番好きです．最初に問題見てから数日たって解けました．かかった時間は合わせて 2 時間 30 分とかかな？問題を渡された段階のサンプルがすごい親切で，最小回数!=転倒数 のケースが含まれていたので助けられました（このサンプルが無かったら倍近くかかってもおかしくない気がする）．この問題はまず最小回数が (N-サイクルの個数) になるのに気づくのが難しくて，渡された優しいサンプルをいじったりしていろいろ実験してたらそれに気付きました（この時点で 100 分位かかってたと思う）．あとはサイクルを管理するのも難しくて，O(N^2) でいったん書いてみた後に，マージテクが適用できることに気が付いて解けたという流れでした．高度なライブラリが一切いらず，使うアルゴリズムがマージテクだけというのが競プロの問題としてかなり面白いと思っています．

優しいサンプルにとても助けられたので，サンプルは弱くした方が良いという提案を当然しました．テストケースの作り方も少し助言したりしました．

私が自力で解けたのもあって diff は 2400 と提案してましたが，2 時間 30 分もかかってるならもっと高くつけるべきでした．本当に diff 予想が下手ですみませんという...

 

K. Lebesgue Integral

tester しました7．私は少し考えて何もわからなかったんですが，誰もやる気配がなかったので引き受けました．CHT をつかって O(NK) にするところは比較的すぐできて，そこからが何もわからず困っていました．O(NK) はできたがその先が分からないと writer に言ったら Aline DP というものがあるよといわれ，noshi さんの記事を教えてもらい，そこに書かれた事実を認めたら解けました．monge 性の何がうれしいかとかなんで三分探索でうまくいくのかとかは何もわかってないです．

今年に入ってぐらいから，TL で monge の話題がたびたび出ていたので，そのたびに「あまり話題にならないでくれ！」と言ってました．universal cup に monge が出たらしく，それの影響もあって正解者数が後半の問題の中では一番多くなりました．

 

L. Inversion High and Low

横で見てました2．なんか最初 milk さんがすごい解法をもっていて（でももともとは 500 回は想定していなかったっぽい？），tester の sota くんは最初マージソートで頑張ろうとしていて，それで 2 人のやり方をいい感じに混ぜると 487 回が達成できることがわかって，すげ～～～ってなってました．共同作問のいいところを見られて感動してました．自分はというと，ARC154D にあるようなマージソートっぽいことは一応考えていたんですが，どうやっても 500 回を下回らず無理でした．ローテートして前・中・後ろに分けるっていう発想は賢すぎるよ～～～～～．インタラクティブのジャッジを作るのが結構苦労してたみたいでした．

この問題だけ 3 時間経過しても正解者が出ず，終了 10 分前に QCFium さんが通したときは writer みんなで盛り上がってました（QCFium さんの直前の提出が 1 ケースだけ WA だったのもあり，祈るように見守ってました）．

 

M. Fractal Tree Isomorphism

tester しました8．これはどれくらい時間かけたかよくわからないです．問題を渡されてから 1 ヵ月以上かけて解きました．最初は，SSRS さんがツイートしていたような解法を考えていました．具体的には，有限の木に対して，その木の各頂点の深さとか次数をもとに有理数を割り当てて，それを無限級数っぽくやることで fractaltree に対しても有理数を割り当てるみたいな方針でした．この方針を writer に伝えたら hack されたので，木の同型判定を使うというヒントをもらって考えなおしたら，最小単位を考えるのに行き着きました．この問題もかなり面白くて好きです．

 

私の途中の考察

 

この問題も diff を 2400 と主張していて，終わっています．

無限周りの定義とか厳密性が全然わからなかったので，数学科の 2 人に見てもらったりしてました．私は解説に書いてある証明がなかなか理解できず苦労しました．

 

もともとは 2 つの木が与えられて，それらから誘導される fractaltree が同型か判定する問題だったのですが，テストケース作りが大変そうだなーって思って複数個にすることを提案しました．この提案が結果的に良かったみたいで良かったです．

 

N. Matrix Game

横で見てました3．この問題だけセットの中で唯一考えてないです．なんか大変そうな見た目してるな～って言ってたら，writer の sota 君が「大変だから無理して考えなくていいよ」と言ってたので，そのまま何も考えないままになってしまっています．tester の 3 人は実験してエスパーしたらしく，すごい...

 

O. Equidistant Binary String

writer しました4．もともと，順列 P,Q に対して dist(P,Q) を転倒数で定義して，2 つの順列 P1,P2 が与えられたときに dist(P1,Q)=dist(P2,Q) を見たす順列 Q についての問題をいろいろ考えてました．Q の数え上げとか Q の辞書順最小とか．それでうまくいかなかったので，なんとなく順列じゃなくて 01 列に置き替えてみて，さらに辞書順最小と数え上げを融合した問題を考えてたら，考察がどんどん進んで解ける問題を生やせました．

考察中は，ARC132 の解説のように，01 列を 2 次元グリッド上の経路としてとらえて考えていました．経路として考えることで，2 つの文字から等距離にあるという条件を経路の下側の面積として表現でき，これがうまく使えました．辞書順最小という条件もうまい具合に表現できて，びっくり．

当時のメモ

コンテスト中に 2 名の方に解いていただいてとてもうれしいです（だれにも解かれたくないという思いも多少はあったんですが，それだと悲しいので）．ありがとうございました！

 

全体の感想・振り返り

まず反省しなければならないのが，難易度の設定ミスでしょう．過小評価しまくっていたのは良くなかったです．どうすれば過小評価を防げるんでしょうか？来年の課題ですね．

そのことを除けばかなりうまくいったんじゃないかなと思っています．コンテスト準備・運営で反省すべき点もいくつかありましたが，初めてのオンサイトコンテストの運営にしてはよくやれたのではないでしょうか．

懇親のときに，セット内容についていろんな人に褒められてうれしかったです．ARC 書ける実力ある世ともいわれて，ARC writer をやるモチベがわいたので，さっさと橙になりたいね！（O みたいな問題をまた生やせる気は全然しないけど）

ほんとにめちゃくちゃ楽しかったです！来年もやるつもりでいます！

 

ざっくりこんな感じです．

ご参加いただいた方々，仙台まで来てくださった方々，本当にありがとうございました！また来年もよろしくお願いします！

 

TUPC2022 おしまい

Python 遅いものたち

Python に関する遅いものたちをまとめました．

Python

Python は遅い．

改善策

  • c++ を使う

numpy でないもの

numpy でないものは numpy であるものより遅い．

改善策

  • numpy を使う．

tuple

tuple に関するものは大体遅い．dict の key にしたり，リストに突っ込んでソートしたりするとやばい．tuple の比較自体が遅い．

改善策

  • tuple を使わない．
    • 例えば 2 要素の tuple で，要素が 2 つとも 109 以下なら，(x, y) は z = (x<<30) + y のように 1 つの整数に変換する．z から x,y を復元するには mask = (1<<30)-1 として x = z>>30, y = z&mask とすればよい．
  • tuple のソートは key を指定する

再帰

PyPy だと特に遅い．

改善策

多倍長整数

263 を超えると途端に遅くなる．

改善策

多次元リスト

遅い．

改善策

  • 一次元化する．
    • 例えば H×W サイズの二次元配列 A は，長さ HW の一次元配列 A' に対して，A'[W * i + j] = A[i][j] とすればよい．

list の append

遅い．

改善策

  • list のメモリをはじめに確保しておく．

入出力

入力がいっぱいやってくると詰む．

改善策

  • sys.stdin.readline を使う
  • 出力が複数行にわたるときは '\n' で join して一つの文字列で出力する

pow(x,k,mod)

何で遅いのかよくわかってない

改善策

  • mod を引数に取らないと除算高速化をしてくれるみたい
def fpow(x,k):
  res=1
  while k:
    if k&1:
      res=res*x%mod
    x=x*x%mod
    k>>=1
  return res

RECRUIT 日本橋ハーフマラソン 2022夏 (AHC013) 参加記

自己紹介

 

大学三年生です．アルゴの方は結構やっていて，現在黄色です．ヒューリスティックは今回が初めてでした．焼きなましとかビームサーチとか何も知らない状態での参戦でした．

 

考えたこと/やったこと

ヒューリスティックで戦う方法を知らないので，とにかく貪欲にやりました．考えたこと/やったことを順番に書いていきます．

 

まず，1 色のコンピュータ 100 台をすべてつなげるとその時点で 4950 点がもらえてかなりお得だなと感じたので，それを達成する方法を考えました．とはいっても移動できる操作回数が限られており，特に遠くにある 2 つのコンピュータをの接続をどうするか非常に悩みました．しばらく考えて，以下のような方法にたどり着きました．

 

初期段階で，移動しなくてもすでにいくつかのクラスタが形成可能です．その中から 2 つのクラスタを選び，うまく接続して 1 つの大きなクラスタにします．その後も，できあがった大きなクラスタと別のクラスタを接続してさらに大きなクラスタを作る，ということを何回か繰り返すことである程度の大きさのクラスタが出来上がります．具体的な手順は以下の通りです．

 


これをある程度行った後，残ったコンピュータたちをどうにかして接続していきます．方法は完全に iwashi31 さんのやり方と完全一致でした．

 

 

これ以外にも，周りに囲まれたコンピュータを救出する方法も行いました（実装がかなりしんどかった...）．使ったアルゴリズムは BFS だけです．

他にも，できる限り移動回数を減らす工夫をしたり，残りの余った部分で別の色をつなげるということをしました（細かすぎるので割愛します）．こんなことをしてたら pretest で 246000 点ほど得られました．

その時の seed=1 の結果です．

このとき，順位は 11 位でだいぶ調子が良かったみたいです．

しかし，上の画像を眺めると，1 のクラスタが分断されているせいでスコアが 4950 からあまり伸びていません．これらの分断されたクラスタをうまく連結できる方法を考えました．

 

いろいろ考えた結果，外周をあらかじめ別の色で囲っておいてからその内側ででかいクラスタを作ると，残りの部分でうまく連結させられるのではないかという方針にたどり着きました．

 

これをすることで，pretest での score は 300000 点を超えることができました！．

seed=1 の画像です．

残りの部分のクラスタが分断されるという問題点をかなり解消できているのが一目でわかると思います．

結果

ここから先は自分でも問題点が見つからず，アイディアも浮かばずで何もせずに終わってしまいました．pretest で 310000 点，システムテスト後の順位は 34 位でした．

良かった点・悪かった点

良かった点としては，ヒューリスティックで使える手法を何も知らないまま果敢に挑戦できたことだと思います．他の上位陣が焼きなまし法を使ってる中で自分は BFS という簡素なアルゴリズムだけでここまで順位を上げれたことは良かったのかなあという風に感じています．

また，実装量が多いことを嫌がらずに黙々とコードを書けたことです．ICPC の練習で培った実装力を生かせました．

 

悪かった点は，ちゃんとヒューリスティックのための勉強をしなかったことでしょう．さらに上位に行くためには，ヒューリスティック特有の手法を身につけないとだめなんだなと痛感しました（でもヒューリスティックの勉強をするやる気が起きない...どうしよう...）．

それから，ここまでちゃんとやると思ってなかったので，最初の方のコードがかなりぐちゃぐちゃになって可読性が失われていたことです．デバッグするのが本当に大変で，かなり精神が疲弊しました．

 

今後

今回初めて参加した感想としては，楽しかったけど精神的・肉体的にかなり疲れるなあという感じでした（楽しさ<<<疲労 だったので長期コンには当分出ないかなあ...）．短期コンは出てみようかなと思います．ヒューリスティックの勉強は気が向いたらしようと思います．