おもしろい台形の話
こんなツイートを見かけました．
要するに，台形の面積が上底と下底を文字列的に繋いだものと一致する場合があって面白いねっていう話です．面白そうと思って適当にスクリプトを書いて探してみたら結構たくさんあったのですが，「何か法則的なのない？」と思っていろいろと試したら次のようなパターンが見つかりました．不思議な台形を見つけました！ 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回はレーティングが上がりそうだけど，そこから先は何らかの対策が必要になってきそう．何しよ．鉄則本？
競プロ日記002: ABC270とMM140とAHC014
ABC参加3回目
この1週間は前半MM140，後半AHC014ということで大変ハードでしたが，こういうのはとにかく続けないとダメなのでトヨタ自動車プログラミングコンテスト2022(ABC270)に強行参加しました．
今回はABCと3問解いて残り時間が1時間ちょい，あと1～2問解けるかなーと思っていましたが，いろいろとダメで結局Dをやっているうちに時間切れになりました．前回より正答数が少なかったけど，まだ3回目ということでレーティングは順調に上がっています．
Dは貪欲→WA，うーん全探索→TLEという典型的な失敗を順当に経た後，メモ化かなーとかやっているうちに時間切れになりました．1時間もあってなんで時間切れかというと，貪欲解法のときに「あれ，lower_boundってどんな使用だっけ？」となって30分くらい調べてました^^;翌朝メモ化再帰版が通りました．解説とかTwitterのタイムラインではDPという説明が多くてそれはよくわかるんですが，自分の基本的なアプローチが「貪欲→全探索→メモ化」というステップになりがちなので，これを「あっ，これ競プロ本で見たやつだ！DP！DP！」という感じにならんとスピードアップが難しいかも．
とはいえ，あまり無理な勉強をすると長続きしないと思うので，基本ABC用の勉強はナシ．とにかく実戦経験を積む．解きかけの問題があった場合のみ次の日に最後までやる程度にしようと思います．
マラソンやろうぜ！
今週はMM140の締め切りでした．順位は32人中18位でレーティングはちょい下がり．今回の問題は結構面白かったので，もっとたくさん参加して欲しいですね．まあAtCoderに慣れちゃうといろいろ不満は感じやすいから仕方ないのだけど．まあ自分はこれからも参加しまくります．
それはそうと，AHC014が締め切りまであと1週間くらいなので，そろそろ頑張らないといけません．しかしMM140が終わったところで頭がまだ完全に切り替えられていなくて，まだお休み中です．今晩くらいから動き出すかも．
競プロ日記001: ABC269
ABC参加2回目
先週の初参加に続いてUNICORNプログラミングコンテスト2022(ABC269)に参加しました．MM140とAHC014が始まっていてかなりハードではありますが，やると決めたので気合で参加です．
方針
言語の選択
初参加のときは最初Pythonで書いていて途中でC++に変えました．マラソンマッチのときはいつもC++なので，今回は最初からC++を使うようにしました．Pythonの方が楽な場合が多いですが，あくまでマラソンマッチがメインなので常にマラソンをイメージしてやるようにします．
解答順序
今回も素直にA，B，C，…の順番に解きました．1時間くらいで目標のDまで解けたので終わりにしようかと一瞬思ったのですが，欲が出てきた＋E問題がインタラクティブ問題という見慣れない形式で興味が出てきたため，結局時間いっぱいやってしまいました．F以降の問題に目を通していないので，次回はとりあえず見てみるくらいはやっておこうかと思いました．
テストケースとローカルテスト
A～Cはサンプルを実行するだけにしました．Dは入力サイズ的に大丈夫かと思ったのですが，あまり慣れていないUnion Find Treeを使う問題だったので大きめのテストケース(N=1000)を一応作ってテストしました．全然問題なかったので，今後は余程微妙でない限りはサンプルのみで突撃します．
ソースコード
そんなにガッツリローカルテストをするわけでもないので，今回はABC269というディレクトリを作って，その中にa.cpp, b.cpp, ...のようにソースファイルを作成しました．これで全然問題なさそうです．
結果
今回はABCDの4問が通って，EでWAが出て修正中に時間切れになりました．
WAの原因
EのWAは原因が2つあって，1つは出力フォーマットのミスです．矩形領域だから
? (矩形の左上) (矩形の右下)
かと思い込んでいましたが，実際は
? (行の範囲) (列の範囲)
でした．問題をちゃんと読まないとダメだということですが，これに気付いたのが終了5分前でした．提出の一覧画面に「詳細」という項目があり，そこでWAの数が確認できることを知ったのが遅すぎました．ここをすぐに確認して，「サンプルですらWAになっているのでオカシイ！」と気付けばもっと早く修正できていたはずです．
さて，急いで修正したので間に合ったのですが，それでもWAでした．これは限度の10回(縦横10回ずつと考える)を質問した場合の処理に対応できていなかったからですが，1つ目のミスの発見が早ければ間に合っていたかもしれません，残念．
次回に向けてとか感想
MM140とAHC014を並行してやっていて全く余裕はないので，参加できたとしても今回とほぼ同じ方針で進めようかなと思います．AHC014はとても賑わっていてすばらしいですね．MM140の問題はとても面白いしもっと参加してほしいんですが，新規の参加者があまりに少なすぎて常連ばっかりの飲み屋状態になってきているのが少し心配です．
競技プログラミングの鉄則
はじめに
『競技プログラミングの鉄則』という書籍が9月16日に発売されます．「これは！」と思ったので，少しの紹介と個人的な感想を書きます．尚，書籍の紹介に関しては特に依頼されたわけではありません．単純に一人の読者として感想ですのでご了承ください。
この記事を書いている人
全くの競プロ素人というわけではありません．主にヒューリスティック問題のコンテストに好んで参加しています．また，本ブログ上部にあるようにいくらか本を書いたり出版に関わったりもしています．つまり，ヒューリスティック好きで本を少し書いたことがある人の感想ということです．
読み方
本書の読み方は自由ですが，14頁に「本書の進め方」という頁がありますので，まずここを読むのがベストかと思います．私は目次を見た瞬間「7章ヒューリスティック」を読みたくて少し迷いましたが我慢して最初から読みました．個人的にはどの技術書でも「はじめに」の頁が一番好きで，ここに著者の想いが詰まっていることが多いので，まず最初に読むことにしています．
個人的なほほーんポイント
競プロに関しては普段からTwitterでなんとなくタイムラインを眺めているので，ワードそのものは何となく知っていたのですが，改めてほほーんと思ったことを挙げます．
- いもす法(2章)：遠い昔に差分の累積和がカシコイということを教えてもらったのだけど，今ではその辺が一般化されて「いもす法」と名前がついているのを知らなかった．
- 二分探索・動的計画法(3・4章)：結構細かく分類されていて，ざっくりとしか理解していないと5分とか10分で解くのが難しそうだということがわかった．
- 考察テクニック(6章)：もちろん他の書籍でも似たような記述はあるのだけど，これが1つの章として存在していることがとても重要に感じた．テクニック的なことに限られているけれども，もっと基本的なアプローチ方法とかメンタル面にも触れておいてもらえるとよりありがたいかな．…と思ったら，10章の頭(410頁)と終章(456頁)に欲しい内容が書かれていた．これは素晴らしい！
- ヒューリスティック(7章)：ほほーんはない．…好き😚
- クエリ処理(8章)：この手の問題に出くわしたことが今までにないので，今知って良かった．要勉強！
- グラフアルゴリズム(9章)：ヒューリスティックでめっちゃ使う気がするので，ここはとても重要．
細かい点では他にもたくさんありますが，皆さんも本書に目を通してほほーんポイントを見つけてください(無かったわーという人はかなり上級者だと思います)．
オンラインテスト
https://atcoder.jp/contests/tessoku-book で，本書に解説されている問題と応用問題をテストすることができます．AtCoderの形式なので，コンテストに参加したことある人は何ら問題ないと思います．AtCoderは使い勝手がかなり良いので，初めての人でも大丈夫でしょう．
最後に
「はじめに」とか「謝辞」の頁を読んで，著者の情熱を感じました．章のまとめ方や図表の使い方を見ると，本書を仕上げるためのバランス取りを相当入念に行ったのだろうということがわかります．本当によくまとまってます．あまりにベタ褒めだと良くないよなーとは思いながら読み進め，この文章も書いていたのですが，やっぱり良いものは良いんですよ．というわけで，本書の紹介と感想はこれくらいにしておきます．とにかく一度手に取ってご覧になることをおすすめします．
