競プロ日記008: MM141に参加しました！
MM141
TopCoderマラソンマッチ(MM141)に参加しました．この日記を書いているのが10月28日で公式な結果はまだ出ていませんが，PROVISIONAL RANKは25位，最終順位は23位でした．
今回からマラソン参加時に簡単な日記を書くようにしてみたので，今後の自分用と，これからマラソンマッチを始める人にとって少しでも参考になれば良いかなーと思って書き残しておきます．
10/20(Thu)
予定通り午前2時に起きて，サンプルコードとテスターのダウンロードを手早く済ませました．
不具合でページが消えたり一時的に閉鎖されることがあるかもしれないので，問題ページは念のためスクショ．
その後問題をちょっと読んで寝て，日中は普通に仕事をしました．適当に信号を切り替えるだけならすぐできますが，先々のこと(たぶんシミュレーションが必要)を考えて，最初の段階でできるだけ丁寧に書いておこうと，信号切り替え→実際に車を動かす→入力を取る→整合性チェックを厳しめにすることにしました．しかし仕事の後にコードを書いてみるものの眠すぎてめちゃくちゃなコードを書いてしまった結果，次の日の作業が無駄なデバッグ祭りになりました．眠いときはおとなしく寝た方がマシですね．とはいえ，最初にきちんとやっておくことはとても重要で，方向性は正しい(はず)です．
10/21(Fri)
前日に書いたコードを修正して動かしての繰り返し．バグは大体取れたはずなのにいくつかのケースでスコアが-1になってしまいました(assert入れまくってるので異常終了)．
ビジュアライザで見てみたら，
10/22(Sat)
最低限の実装を一通り終えて提出するとスコアは78点くらいで12位，悪くなさそうです．いくらか点は上がるビジョンがあるので安心してこの日の業務を行うことができました．この時点では，グリッド上にあるすべての車について，とにかく前に進むだけです．信号に引っかかって動けなくなれば信号を切り替えるというだけ．それでもそこそこのスコアが出るので，これってめっちゃいい感じじゃね？と思ったもののそこからスコアを挙げる方法がよくわからず．とりあえず前に進める車に優先順位を与えることから取り掛かろうと日曜日の方針を決めて寝ることにしました．
10/23(Sun)
比較的時間はあるので，家族とのんびり過ごしながら何か思いついたら実装して確認というのを何度も繰り返していました．しかしいろいろやっても推定1～2点くらいしか上がらなさそうなので，100ケースくらいをビジュアライザでチェックしたところ，
10/24(Mon)
朝から予定が詰まっていてほとんどノータッチでしたが，いくつかのseedで極端に点が低いことがわかったので残りの時間はグリッドロック対策を行うことに絞り込みました．
10/25(Tue)
調査の結果，やはり早い段階でグリッドロックしていることが確認できました．まずはグリッドロックを検出できるようにしなければいけないということで，それだけ頑張りました．
夜中まで頑張って，「次のターンでグリッドロックが発生するよ！」というのを見つける処理を実装できました．この状態になったら上手く調整して渋滞を回避しないといけないのだけど，残り時間を考えるとバグらせずに組み上げる自信がなかったので，渋滞に関与している車をランダムに停車させて渋滞を回避できるかを何回か(10回)試してみる処理にしました．完全に渋滞を防げるわけではないけどだいぶマシになりました．これで最終日に時間がなくても提出できる状態までもっていけそう！
10/26(Wed)
最終日．普段は高速化とかパラメータの調整くらいしかできそうなことがないけど，今回は割と実装げーな感じでやることが無限にある感じでいつもと違う充実感がありました．残り時間と相談しつつ，できそうなことだけ進める．この日やったのは，まだ動く余地があるのに止まってしまうことをできるだけなくすように，取り除けそうな条件式を取ってはバグって取ってはバグって，じんわりスコアアップしていきました．渋滞が発生したら一時的に車を出現をブロックする処理を加えてみたら，渋滞が起こりやすいケースではある程度機能するもののそうでない場合はスコアが下がってしまってトータルではそんな感じだったので，無理やりコントロールするのは断念しました．
23時くらいに完成して提出し，お疲れ様でしたーと終わるつもりだったのですが，不要なコードを削除していたら削除前とスコアが変わってしまったので，「絶対バグあるやんこれ😱」ということで泣きながらデバッグしました．で，提出できたのが1時57分と超ギリギリ．まあ何とか間に合いました．スコアが1.5点くらい増えたので，もしかしたら2～3ケースWAを出していたのかも．
というわけで，やりたいことがすべて実現できたわけではないけれども何とか形にできました．
やりたかったこと
もう少し時間があったら，1つ先のターンだけでなく複数ターン先をシミュレートしてみてよりスコアの上がりそうな選択をする処理を加えたかったです．2～3ターン先読みするだけでも結構変わる気がするので，そこが心残りではありますが，まだまだ実力不足ということで次に向けて頑張ろうと思います．
競プロ日記007: ABC274も終わったしマラソンマッチをやるのだ！
ABC参加7回目
キーエンスプログラミングコンテスト2022(ABC274)に参加しました．ABCDの4問を解きました．D問題を提出したのが終了2分前くらいだったので後は何もできず…．ACした時間を見返してみると
[A]21:09:05 [B]21:13:20 [C]22:01:36 [D]22:38:04
Aでもたつきすぎなのと，Cで時間かかりすぎでした．Aは四捨五入か面倒やな…と思っていろいろと調べたりもがもがしてましたが，結局のところPython3なら
print(f'{B/A:.3f}')
で通るんですね…😅しかし.3fのところを.3gと書いていて0埋めする方法を3分くらい調べてました．これホンマに2問くらいしか解けないんじゃないかと思ってきましたが，Bは特に迷う要素もなくすんなり通ったのでちょっと持ちこたえました．
しかしCで大幅なロス．問題の意味が全然わからなくて，とりあえずサンプルで入出力が一致するコードを提出してWAを得るということを複数繰り返すことでなんとか通りました．明らかに集中力がなくなってきて，通った時点で諦めようかと思ったのですが，一応D問題も目を通しておこうと開いてみるとできそうだったのでやってみて，終了間際になんとかAC.
振り返ってみると，「わかるぞ！」と思っても37分くらいかかっていてとても遅いので，C・Dの過去問で練習しないと成績は安定しなさそうです．ちょっとずつやっていこかな．
MM141
マラソンマッチ(MM141)が始まってます！ これに関してはまだ途中なので書けることがないですが，今回から日記をつけるようにしたので次回の日記にまとめを書こうかなと思っています．現在37人中20位で，これからもうちょっと頑張ろうと思います．まだ参加していない人はぜひご参加を！！！
競プロ日記006: 今日も割とやらかす
ABC参加6回目
パナソニックグループプログラミングコンテスト2022(ABC273)に参加しました．ABCの3問を解いて，Dを愚直な方法で書いたあとTLEにならずにREになった1ので，なんでやろーと思っている間に時間切れでした．前回までの結果から，テストデータの用意とかスムーズな提出を行うためにいろいろと準備はしていたのですが，新しい環境にした結果余計にもたついてさらに提出が遅れるという事態になりました…．まあ何回か参加していれば徐々に慣れるはずなので，あまり気にせずやっていきたいと思います．
前回からの変更点
この記事を参考にしてatcoder-cliとonline-judge-toolsを導入し，コマンドラインでいろいろとやりくりできる環境にしました．
「これでバッチリじゃろ～」と思ってたのですが，いざ始まってみると
事前のログインを忘れて焦る
acc new abc273した後，何故かぼーっと待ってしまう提出したつもりでできていなかった
というアホみたいなミスをしてしまって，結局最初の5分くらいはワタワタして余計に遅くなってしまいました…．
事前のログインを忘れて焦る
過去問で練習したときにログインしていたので大丈夫かなーと思っていたのですが，再度ログインが必要な状態になっていて，「なんかダウンロード遅いな」と思ってたらidとパスワード入れなはれ的なメッセージが出ていてまず慌てました．1アホ
テストデータの取得時にぼーっとしてしまう
テストデータを自動でダウンロードしている間に問題を読んでスピーディに解答する予定だったはずが，進行状況をただぼーっと見つめるだけになっていました．おそらく1アホのときにかなり動揺したこともあるかな？2アホ
提出したつもりでできていなかった
acc submit src
で簡単に提出できるので超楽チンになりましたが，実際にやってみると(たとえばD問題だと)
[WARNING] the problem "https://atcoder.jp/contests/abc273/tasks/abc273_d" is specified to submit, but no samples were downloaded in this directory. this may be mis-operation Are you sure? Please type "abcd"
みたいな警告が出て，さらに指定された文字列を入力する必要があります．これは事前に確認していたものの，いざコンテストが始まるとそれを忘れてしまっていて，しばらくぼーっとするというのを何度となくやってしまいました．あまりにも注意散漫です．3アホ
まあそんなこともあって，いつもと大して変わらなかったような．やっぱり単純に過去問をやって慣れていくしかないですね．
二分探索
毎回のように二分探索が必要な問題が出ている気がして，毎回同じようにbsearch→いや違う→binary_search→これじゃあ要素が特定できないやん→upper_boundとlower_boundどう違うんだっけ？？と調べて2，毎回結構な時間をロスしているので，ちゃんと覚えておくとかコードスニペットに登録しておくとかせねばならんと思いました．
次回に向けて
過去問を少しずつやりたいと思いつつ，今週はMM141が始まるし仕事がどんどん溜まってきているので，当面はAとかBくらいの短時間でできそうなものに限定して練習をしようかなと思っています．
-
グリッド用のメモリを確保しようとして失敗してたっぽい．障害物の情報だけをリストにしたら大丈夫でした．↩
-
そして毎回https://qiita.com/ganyariya/items/33f1326154b85db465c3を見る^^;↩
おもしろい台形の話
こんなツイートを見かけました．
要するに，台形の面積が上底と下底を文字列的に繋いだものと一致する場合があって面白いねっていう話です．面白そうと思って適当にスクリプトを書いて探してみたら結構たくさんあったのですが，「何か法則的なのない？」と思っていろいろと試したら次のようなパターンが見つかりました．不思議な台形を見つけました！ pic.twitter.com/yjpzvUYpwA
— ポテト一郎🥔 (@potetoichiro) 2022年10月8日
これをベースとして，上底の頭に3をつけ，下底(=高さ)の頭に6をつけます．そうすると，以下のように条件を満たす台形になりました．
もしや…！と思って同じ操作を行うと，やっぱりできました！！
これ，たまたまかなーとも思ったのですが，意外と簡単な計算でこの規則が成り立つことがわかったので，記念に書き残しておきます．n桁の上底を
と表すことができます．下底(=高さ)の方はちょうど上底の2倍の長さなので，
となります．このときの面積は，
となります．ここからさらに
となり，おお！これは何桁でも増やせる！！うれしい！！！となりました．まあ何の役にも立たなさそうですが，こういうのが見つかるとなんか嬉しいですよね😉
競プロ日記005: ABC272と息抜きコードゴルフ
ABC参加5回目
土曜日の朝から鼻水大洪水でしたが，走れば治るやろの精神でABC272に参加しました．ABCDの4問を解いて，Eを愚直な方法で書いたあと時間内に収めるための方法を考えている間に時間切れというかんじ．Eは後でいろいろと試してみたけど，前処理として解に関与しなさそうなAを取り除いておくことで時間内に収まりました．正直あんまりよくわかってないけど，とりあえず通ったのでヨシということにしておきました．
Bで問題を誤読していたので10分くらいロスがあった気がしますが，それがなくても100分で5問解くのは結構しんどそうです．
とりあえず早解き技能なのかな？
5回のパフォーマンスを見てみると大体同じような数値になっているので，現時点での実力はこんなもんなんでしょう．ということで，そろそろ次のステップに進むのも良いかもしれません．TwitterのTLを見る限り，相当な上級者でない限りは全問解けてなくても大丈夫そうで，むしろA～D辺りをミスなく短時間で解いた方が良いように見えます．だとすると，知識を増やすよりまずはスピードアップを目指すのが一番ですね，たぶん．
2回目以降の参加時は，前参加したフォルダを丸ごとコピーして，前のコード部分を消して新たにコードを書くということをやっているので，まずこの辺で無駄操作によるロスがある．あと入力サンプルをその都度コピペしているのも結構無駄の多い操作かなぁ．
順位表とか全然見てなかったけど，後から見てみたらA問題を数十秒で通している人もいるんですね．そして4問正解が1000人以上もいて，単純に解答速度だけでそれくらいの順位差が出るということなので，スピード重視ということで間違いなさそう．しかし問題を開いて，読んで，コード書いて，動かしてみて，提出なんて間違いなく1分以上かかるんですけど…皆さんスゴ過ぎ！
息抜き
TwitterのTLを眺めてたら，A問題はfor文を使わなくても解けるみたいなことが書かれていた(気がする)(どのツイートか覚えていなくてごめんなさい)ので，ABC272のA問題で，Cで試しに書いてみました．これは与えられた入力値の合計を計算して出力する問題です．
s,a;main(k){~scanf("%d",&a)?main(s++?k+a:0):printf("%d",k);}
合計値を保持する変数をkとします．scanfで1つ整数値を読み込んで(aに代入)，1つ目の値はデータ数で合計値に必要ないので，この場合にkを0にセットしています．2番目からはkに足し合わせるようにしました．カウンタには変数sを使いました．確かにfor文を使わずに書けます．ABCの問題はよく考えられていて素晴らしいですね！
…とまあ，懐かしいネタを久しぶりにやるとあなごるとかやりたくなってきますが，我慢してアルゴ力を鍛えることにします😣
競プロ日記004: AHC014の反省
AHC014の復習（反省？）
AHC014では長期コンなのに頑張り切れなかったので，ちょっとだけ復習しておくことにしました．私の場合，MMとかAHCではとりあえずA*を実装することが多いです．よくあるパターンはpriority queueを使ってA*→良さげなら深さ毎にpriority queueを用意してビームサーチ的なものという感じなのですが，これだと結構な数の状態を保持することになるので，速度面でもメモリ面でも十分に最適化できていない状態でこの方針はマズい気がしました．そんなわけで最初にシンプルなDFSを書いてみたんですが，スコアがかなり低かったのでその理由だけ確認しておこうと思いました．
ランダムに負けてんじゃね？
最初の方の操作が後の方にどう影響してくるのかぜんぜんわからないので，DFSとか全く向いてないとは思いつつ，だからといって「ハイ焼きなまし！」みたいなこともできる気がしないので，それなりの評価関数なり枝刈りができればスコアはある程度上がるだろうと一旦書いてみました．案の定とてもスコアが低い．制限時間を延ばしたところで深いノードの周辺でもちゃもちゃやるだけなのであまり意味がないし，まあしかたないかなー．
でね，公式解説を観たんですよ，最初の30分くらい．そしたら負けてるんですよ，ランダム解に負けてる😭．さすがに情けないということで，何がダメなのかを確認しておきました．
小さい矩形を優先
これは最初から気付いていたので，「ですよねー」とか思いながら解説観てたら，小さいものを優先的にランダム配置したものに大きくスコアが負けていました．ここでビジュアライザ（アニメーション）を初めて使いました（遅い）．最初に小さな矩形を作ることができる場所は限られていて，以下の辺りだけです．
このとき，どちらからでも良いんですが，貪欲にみちみちっと点を打ち込んでいくと当然周辺が埋まります．埋まると別のところを埋めていって，全部埋まれば終わりという感じですね．
このようにした場合，上手くやれば埋められた部分がぽっかり空いてしまうことがあります．
ランダムに負けてるのはこれでした．試しに埋めきる前に他の部分に移動する方針にしてみました．
この方針で進めると，無事右下部分を埋めることができました．
まあとりあえず埋まったというだけで，上の方が全然ダメですが…．
反省
これはちゃんとビジュアライザを見て早期に気付くべきでした．あと手抜き実装として，DFSで解の更新がなくなった場合に適当に上の方のノードにジャンプするだとか，最初からやり直すとかしがちなんだけど，もうちょっと真っ当なやり方で改善していきたい😩
競プロ日記003: AHC014とABC271
AHC014
AHC014終わりました！ AHC(長期)の締め切りって日曜日の19時が多い気がするので，今回もそうだと思ってたら前日の土曜日だったんですね．締め切り20分前に気が付いて，とりあえずちゃんと動作しそうなものを提出しました．最終日に細々と実装しようと思ってたことができなかったのでちょっと心残りな部分はありますが，さっさとやらない自分が悪いのでまあ仕方ない．
感想
この問題は盤面の評価が難しくて，一通り点を置かないとスコアの良し悪しがわからないので，ものすごく難しいやつだと問題を読んですぐにわかりましたが，『じゃあどうする』が全然出てきません．こういう状況は最近多くて，ダメなことはすぐにわかるようになっても解決案がろくに出てこないという苦しい時期です．結局は自分にできそうなゆるふわビームサーチをやることになるんですが，MMと違って盤面がとても大きく，また制限時間も比較的少ないため強引な探索ではほとんどスコアがでません．この辺もよくわかっているハズなのに全く対処ができていない．少し時間をかけて戦術を考えておかないといけませんね．
基本方針
盤面が大きく探索が難しいのと，現状では高速化が不十分ということもあって，なかなか酷い方針だとは思うんですが貪欲ガチャしました．具体的にはZobristHashingで盤面を記録しつつ，(その点を置いたときのスコア) × 倍率 - (ペナルティ)を評価関数として貪欲に点を置きます．ペナルティは矩形のサイズの2乗と，縦横バランスとしました．つまり矩形が小さくて，正方形に近いものほど高評価になるようにしています．この評価関数で生成した盤面を記録し，同じ盤面はスキップするようにしつつ，スコアの倍率を変化させながら繰り返し実行する感じです．
とにかく初期の盤面の状態が悪ければどれだけ探索しても意味がないので，最初から何度もやり直して偶然良いスコアが出るまでやっただけですね．本当はそこそこ良いスコアが出た盤面に対して点の削除と追加を何度か行う処理を入れたかったのですが，間に合いませんでした．
データ構造
Nが最大61ということで，どう考えてもBitboard作れってことでしょ！と思って64bit整数の配列×4(縦横斜め)に辺の情報を持たせました．あと，矩形のデータは繰り返し生成しそうだったので一度作ったものはキャッシュするようにしました．これはそんなに悪くないはず．
ダメポイント
まあとにかく遅い．何が遅いかというと，毎回点を打つための候補を盤面全体に対してチェックしているので，これで探索しようとすると全然間に合わない．最初に候補の一覧を生成し，あとは点を打つたびに差分を取るようなことをしなければならないと思うのだけどこれができていない．あとは点を取り除く処理ができていないところで，依存関係を考慮しつつとなるとバグが出そうで作業を後回しにしてしまったところですかね．早い段階でこれが必要とわかっていたのに手をつけないのは反省しないといけません．
次回に向けて
ヒューリスティック問題のコンテストで実力を挙げるには，コンテストが終わった後どれだけ復習するかで決まるような気がしていますが最近はまったく時間が取れていないので，そこをなんとかせねばなりません．コンテスト終わる→溜まった仕事を片付ける→次のコンテストが始まってしまうの連続なので，おそらくどこかでお休みを入れないといけません．もちろん『お仕事』の😁
ABC参加4回目
AHC014の提出を終えてぐったりしている中，京セラプログラミングコンテスト2022(ABC271)に参加しました．今回も3問ですが，初めて解く順序を変えてABDの3問を解きました．朝から子どもの運動会を観に行って，帰って仕事して，仕事中にAHCの締め切りが土曜日ということに気付いて慌てて提出して…と，いろんなことがあって心身ともにかなり疲労していたんですが，まあ何とかなりました．D問題に関しては昔自分が書いた記事でDP解の復元について触れていたので，「これは間違いなくできる」と判断しました．しかし表(H)と裏(T)を逆にしてWA(´Д`;)あとはA問題をPythonで書いたので，B問題でC++に変えたときに言語選択ミスでRE．そうかそんなミスもあるね．やっぱり言語は常に統一した方が良さそう．
Cはちょっと考えてできそうな気もしたんですが，全く頭が働かない状態でやったら間違いなくバグを埋める自信があったのでやめときました．復習もたぶんしないかな．あと3～4回はレーティングが上がりそうだけど，そこから先は何らかの対策が必要になってきそう．何しよ．鉄則本？
