競プロ日記009: ABC276
ABC参加8回目
ABC275は一度お休みして，AtCoder Beginner Contest 276に参加しました．ABCDの4問を解きました．E問題に目を通したのが残り10分ちょいでしたがマラソンマッチでよく書くタイプの問題だったので「いけるかも！」と思ったけど間に合いませんでした😢
解く順番をちょっと変えてみた
これまではA問題から解いていたんですが，データセットのダウンロードに時間がかかってしまったため待ち時間の間にB問題に目を通していました．そうすると頭の中がB問題になってしまったのでBACDという順番になりました．全体的な出来には対して影響しなかったけれども，無駄な待ち時間は数十秒くらい減ったので悪くないかも．C以降の問題も見た方が良いのかもしれない．
C問題: Previous Permutation
どうやらprev_permutationという関数があるらしいけど知らなかったので，真面目に考えました．数字列の後の部分が単調増加している区間を見つけて，そのひとつ前（単調増加が崩れている箇所）から並び変える感じですね．
9 8 6 5 10 3 1 2 4 7
という例なら，
3 1 2 4 7
という部分で，3と2を入れ替えて，
2 1 3 4 7
のようにして，2より後の部分を降順にソートします．
2 7 4 3 1
解説とかは見てないので想定解かどうかは知らない．
D問題: Divide by 2 or 3
結果的にそのまま実装すればよかっただけなのだけど，ここら辺までくると余計なことを考えて迷ってしまうことに気付きました．「本当にそれだけで良いの？何か高速に計算しないとダメ？」みたいな．大きいテストケースを想定したときの時間感覚が身についていなくてそういう思考になるのだろうなと思うので，やっぱり過去問等使って練習しないと早解きは難しそうですね．
3つ以上の数の最大公約数を求める方法がパッと思いつかなかったのでものすごくややこしい実装をしてしまいましたが，よく考えたら3つ以上でも順番に計算すれば良いだけでしたね．焦りは禁物．
E問題: Round Trip
これはマラソンマッチでめっちゃ書くタイプのグリッド問題なのでACしたかったところですが，時間切れ😢やっぱりスピードがネックだ…
競プロ日記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で解の更新がなくなった場合に適当に上の方のノードにジャンプするだとか，最初からやり直すとかしがちなんだけど，もうちょっと真っ当なやり方で改善していきたい😩
