AtCoder Beginner Contest 198 反省
一応、黄色昇格に王手をかける形となった。とはいえ、次は8問制ABCなのでうまく立ち回らないと破滅し再び黄色が遠のいてしまう。
結果を鑑みて
1500(2) 44:33
149位となった。速解き力、数学力、実装力、そして注意力が必要とされる実にやりづらいセットだった。苦手回ではなかったが、どの問題でも嵌って破滅があり得たセットだった。
A - Div
最初、N≦15という制約を見て少し動揺したが、サンプルからN-1をエスパーしてこれに証明を与えてACできた。
B - Palindrome with leading zeros
なぜかわからないが末尾の0を消す方針で回文判定を行なった。しかも回文判定も１文字ずつ。（S==S[: : -1]でいいのに)
結局4分かかって順位表も見てしまって精神が乱れる要因となった。ここらへんのムーブはかなり変だった気がする。
C - Compass Walking
まず、貪欲に近付いてシミュレーションするのは得策ではなさそうに見えた。そうなると数学することになるが、これもよくわからない。第三の選択肢として二分探索を考えたが、これが実にシンプルな解法だったのでこれが答えだと確信した。
WAが返ってきた。順位表を見ると大勢ペナを出していたのでそこまで焦燥を感じずには済んだ。そのため冷静にWAケースの数からコーナーの発見につなげることができた。
この問題はいつぞやのBishopのような雰囲気を感じた。ここで1ペナつけて12分くらいで200位くらいだったと思う。少し安心した。
D - Send More Money
まず、問題を読んで面倒臭そうに思った。leading zeroを許しているのかどうかもわかりづらい。問題の理解におそらく2~5分かかり、理解すると解法はすぐに生えた。permutationsを使うやや面倒な実装問題であることがわかり、順位表を見るとわずかにEのACがDより多く、Eの方が簡単らしいことが意図せずわかってしまったが敢えてそのままDを解きにかかった。
結局、14分程度かけてこれをACした。このとき、実行時間制限が5secであることにACを取ってから気付いた。ジャッジ中はTLEしないか気が気でなかった。4.4secでギリギリ通って安堵したもののもう少し高速な処理が書けたのではないかと少し思った。
この時点で体感時間的には21:50ほどであったが、実際は21:30ほどで、なかなかよく集中できていたと思う。
E - Unique Color
案の定、この問題は見て少し考えたら解法が生える程度の簡単な問題だった。サンプルを眺めていたときに「出力は昇順か、気をつけないと」と思ったのも束の間、実装に入ると全部忘れて出力をソートせずに出して1ペナつけた。これでパフォーマンスが30~40落ちていると思われる。
最初にミスしそうな点に気付いたらコードにコメントしておくことにしよう。この時点ではpredictorの算出では黄色タッチだった。順位もそこまで悪くなく、安心して次の問題を見ることができた。（とはいえ、Fが異常そうなのはAC数から既に察していた。）
F - Cube
これは解けなかった。難問。
ボリアの数え上げ定理に思いを馳せたが、三次元の回転にどう持って来ればいいのかわからなかった。これに関連して、mod 6でうまいこと順列表現してサイコロの同型判定ができないか考えたりもした。
また、サイコロのパターン列挙は6!で進み、これの同型判定ができればあとは組み合わせ論の計算に落ちることを見出したが、最初の同型判定をどうすればうまく進められるのかわからなかった。対称性のある無向グラフについての判定と見て、隣接行列をうまく照らし合わせられないかと思ったが......。また、それができたとしてもその後の計算も特に方法が思いつかなかった。
そんなこんなで、22時くらいには恐らく解けないし、解かなくても大丈夫な問題だなと判断してそこから10分ほどまた考えた後にお風呂に入って完全に撤退した。（とはいえお風呂でもついつい考察してしまうのだけれど）
総括
出だしのムーブが変だったような気がするが、C~Dあたりのムーブはまあ良かったと思う。Eのようなミスは今後しないようにしたい。
AtCoder Regular Contest 116 反省
4完、遅解き...... とはいえ微減少なのでARCとしてうまく立ち回れたほう。
結果を鑑みて
1700(1) 80:27
全体491位、レート-6となった。Dで時間かけ過ぎたとは思うが、その割に減少は優しかった。
A - Odd vs Even
最初は何もわからなかったが、偶奇性はあるなと思って、{2, 2以外の偶数, 奇数}で場合分けした。この時点でサンプルは通るが、さすがに4や6で試してみると答えが異なっており、そこからなんとか解法を思いつくことができた。
4分半かかって、まあそこそこだろうと思ったら600位くらいだった。びっくりした......
B - Products of Min-Max
最初は主客転倒オーラがすごいのでその方針で少し考えた。さすがにminとmaxではうまくいかないから、とりあえずソートすると、区間についてごにょごにょする問題に見えてきた。
あとはいい感じに値を累積しながらmaxかminの値を固定して計算すればいいことに気付いたが、添字ガチャでごちゃごちゃになってしまい、結局11分かかった。
順位表を見て、まあARCだしそうだよねという気持ちになった。ここまでのムーブのせいで焦りが生まれてしまったかどうかはあまり覚えていないが、そこまで精神は乱れていなかったと思う。
ちなみに、ここでmodの取り忘れでペナをつけた。
C - Multiple Sequences
読んですぐ、Mまでの全探索となんかの約数列挙が思い浮かんだ。sieveは整備済みなのでこれを引っ張り出して取りかかった。
解き進めていくと、1~Mの整数の素因数をN個の箱に突っ込んでいってその際の場合の数を数える問題になった。 ここの数式ガチャで手こずり、とんでもないコードを書いてしまった。
16分かかった。
思えば、この時点で何だか脳死コードを書いているし集中力が破滅しかけていた。部屋が少し暑かったせいだと思う。春の訪れだろうか。
D - I Wanna Win The Game
序盤〜中盤はなんだか意識が朦朧としていて、何を考えていたのかまるで覚えていない。20~30分ほどを何だかよくわからない解法に費やして破滅しかけていた。ここで順位表は見ないぞと（精神安定のために）決め込んだのは悪くなかったと思う。
考え方を変え、解法ガチャに再度戻ってくると実に素朴なO(M^2logM)のdpが生えた。いやいや、pypyでこんなの通るわけないだろと思いつつコードテストに放り込むと存外高速で、なんとか通すことができた。
解法ガチャを最初にやるときは紙に解法を書き出しておいていつでも参照できるようにしておくべきかもしれない。
E - Spread of Information
パッと見では木の中心からのdpと二分探索に見えた。これのおかげで意識がはっきりし、以後の考察はいい感じに進めることができた。解けてないけど。
木の中心に情報伝達すると、まず最初のサンプルで落ちる。代わりに、葉からなるべく直接情報伝達する点が少なくなるように配置する方法を思いついた。葉から見るとそれが最適な配置になる上に無駄がないように見えたが、このdpの結果直接伝達する点が0個になってしまう場合や多すぎる場合などに対処する方法が思いつかず、そのままタイムアップとなった。
総括
だんだん気温もあったかくなってきたので、体温調節をしっかりするように気をつけよう。解法ガチャは時間かかりそうな問題(ARCやAGCなら400点~)ならば紙に書くなどしよう。
なんだか終わってみるとどっと疲れた回だった。今これを書くのも結構しんどい。Dで自分が今書いているコードの意味がわかっていないような状態が中盤続いてひどかった。体温の問題なのだとしたら、次回以降対策できると思うのでしっかりやっていきたい。
AtCoder Beginner Contest 197 反省
あたたまれてよかった。UTPCを５時間もやって脳みそ破滅していたかと思いきや、良いウォーミングアップになっていたようだ。
結果を鑑みて
2100(1) 80:38
基本的に考察はすんなりと進む問題セットだった。得意回ということになるわけだが、得意回なら60分以内に全完したかったところ。pythonの定数倍関連での知見が増えたのでよしとする。
A - Rotate
１文字目と末尾を交換する問題だと思っていて少し時間かかった。rotateって書いてあるだろうが。
B - Visibility
こういうグリッド上の上下左右探索がABCで出るのは3回目くらい？B問題としては難しいと思った。読んですぐに解法はわかったが、実装には少し手間取った。5分かけてfor文を4個書いてAC。
C - ORXOR
題意が少し取りづらかったけれど（読解力さん？）制約をみるとbit全探索で、解法はすぐに生えた。仕切りの位置の組み合わせを全探索してAC。5分ほどで終わった。
この時点で順位表を見て、そこまで悪くはなかったので特に焦ることはなかった。
D - Opposite
第一感として、正多角形ならば外心を使うことができることに気付いた。最初は外接円半径を出そうとしたが、よく考えると外心を中心としてp0を回転させるだけなのでwikipediaの回転行列公式をググってなんとかACした。そこまで悩んだ印象はなかったが7分かかった。
ABCで300点以上のO(1)数学が出たのは久しぶりな気がする。これで誤差ゲーだったらブチ切れてAtCoder引退をしていたかもしれない。
この時点では順位もいい感じだったのでいい気分で先に進むことができた。
E - Traveler
パッと見た感じ、色ごとにまとめて色の昇順に見るのが良さそうで、右端行ってから左端行くのと左端行ってから右端行くのでは移動距離が変わる場合があって、これが貪慾性をもたらすように思えたが、よく考えるとこれが次の色に取り掛かる時にも影響を及ぼしているので単純な貪慾ではなさそうだった。無限場合分けかなと思ったが、その色の右端で終わるか左端で終わるのが流石に移動距離的には正しそうなのでこれを持ってdpすることにした。ほぼお気持ち証明だったが、なんと正しかった。
13分ほどでACでき、順位も上々だった。精神的には安定していて、橙パフォあるかも〜とか思っていた。
F - Construct a Palindrome
第一感として、回文なら両側から同時に歩を進めれば良いだろうというアイデアになった。最初、N≦10^5だと思っていたので解法は特に思いつかなかったが、制約のN≦1000を見ると直積グラフを作ってDFSするだけの計算量的余裕があることに気付いた。すぐさまDFSを組み、サンプルをチェックすると正しい答えが得られた。
ここで提出する前に一呼吸おいてN=1000の一直線なグラフについてテストするとなんといつまで経っても処理が終わらず、PyPyでさえN=200で5secかかるなどえらいことになっていた。ここから20分ほどかけて定数倍高速化をして、PyPyでN=200で3secまで縮めたがあまりにも遅くてびっくりした。
最後の希望としてDFSにつかっていたスタックをlistからqueue.Queueに変えた。これをするとなんとN=1000でも0.6secほどのスピードで進んだ。驚きすぎてうっかりテスト用の入力を残したまま提出して1WA、その後ACできた。
listよりqueueモジュールの方が速いという話は聞いていたが、これで橙パフォがおしゃかになったと思うと全完後は辛い気分になった。
ところで、コンテスト終了後に外を走っていた時にふと気付いたことだが、queue.Queueは"FIFOキュー"である。つまるところ、気付かないうちにDFSではなくBFSになっていたことになる。この問題の本質は直積グラフの最短経路問題なので、DFSは不適でBFSを使うべきシーンであった。
なんと、考察の大詰めでしくじっていておまけに運でACしていたということである。この事実に気付いた時、あまりの不甲斐なさに私は膝から崩れ落ちて目の前が真っ暗になってしまった。
総括
queueモジュールについて理解を深める必要があること、直積グラフは想像しづらいので最短経路問題であることにすら気付けなかったことなど色々と課題が見つかった。
コンテストのムーブとしてはA~Eまでは大変良かったと思う。Fは知らない！
AtCoder Beginner Contest 196 反省
つらいね ぐにゃぐにゃになります
結果を鑑みて
1000 15:25
やらかした......という気持ち。青下位パフォ、全体785位、レート-29となった。最近やらかしたABC級4完はCaddiコンで、まあもう4完なんてしないだろ と思ってたらこんなことになってしまった。その時も今回もE: 数学, F: ライブラリ+高度典型といったラインナップだったので、こういうのが苦手なんだなーとはっきりした。
余談だが、CaddiコンのWriterと今回のWriterを見比べてみると......
A - Difference Max
見てすぐ解法はわかったのでその通りにやった。
B - Round Down
Xの上限が10^100とか書いてあってぎょっとしたが、これはよく考えると文字列で受け取って小数点で分割すればいいことにすぐ気付くことができた。いつぞやのABCで出た誤差ゲーでも浮動少数点数をまず文字列で受けるというテクが出たことがあって、そこで破滅したので記憶に残っていた。
C - Doubled
問題文が簡潔なので問題読む前に制約が目に入った。問題文を読むと制約の意味がすぐに理解できた。てきとうに全探索するだけなのですぐに書いて出した。
ところでサンプル2の1333ってなんだろう。
この時点で初めて順位表を見た。そこそこだったので焦らず進むことができた。
D - Hanjo
少し悩まされた。まず、問題文と制約から盤面の全列挙が可能なことに気付いた。これをbitDPで組もうとするのは少し大変で、精神のリソースを消耗することが予想された。そんなわけで少し逡巡して、dfs木の深さが高々8程度に抑えられることから、盤面と１畳の畳を引数に持った再帰的な解法を試みた。
サンプル2で答えが大きくなりすぎて少しびっくりした。重複をうまく除去できていないからこの方法じゃダメなんだ、と思ってコードを消そうとしたが、どういうわけか踏みとどまって順列で割ることを思いつくことができた。ふと思い出した蟻本のボリアの数え上げ定理の記憶が助けてくれた。ありがとう蟻本。
この時点で順位表をみるとかなりいい感じだったのでエンドルフィンの分泌を感じながら次の問題へ進むことができたのだが......
E - Filters
問題を読むと、操作についての前計算を行い、クエリに対して小さい計算量で解答する問題のように見えた。
次のように解法の予想を立てた。
1. maxやminをif文に置き換えて数直線上のイベントソートのようにやる
2. なんかがんばると遅延セグ木に載る
3. 実はmaxもminもまとまっていい感じになる
コンテスト中は特にパッと思いついた2. が光明のように感じられて、大半の時間をmaxの合成写像を考えることに費やした。
1. もそれなりだが、加算操作のせいで前計算が二乗計算量になってしまい、うまくいかなかった。
1. も2. もうまくいかず、すっかり焦ってFを見に行ってあれこれ考えたりした。こういう時、どうやって思考をクリアに戻すのが正しいのだろうか。
最後10分ほどで3. をやけくそになって考えた。実はこれが最も答えに近かったのだが、結局コンテスト中に提出することすらできなかった。
できあがる関数の形に注目する問題はABCでも度々出題されているが、だいたいの場合はそれが単調性と結びついて二分探索やら三分探索につながる問題だが、自分は今までそのような問題に対して「単調性がありそうか」を調べ、その結果として関数の形に気付くことが多かった。maxやminの合成関数の概形が正しく想像できなかったのも無理もなかったかもしれない。ただ、サンプルは明らかに単調だったので嘘でもにぶたんとかしておきたかった......
F - Substring 2
この問題を見たのはEに詰まっていたときで、パッと見てdpや前処理、差分などに思いを馳せた。感覚的には解けなくもなさそうだった。solve probability 30~50%程度の感覚だった。
Binary Trieとの相性が良さそうに見え、それを使った考察に時間を使い、ダメだと思ってEに帰る、といったことを繰り返した。
大局的に見たような定式化ができればこれは解けたかもしれないが、流石にEが通っていないとその余裕はなかったろうと思う。
解説を見て悔しい思いをした。配列同士のなんやかんやを多項式乗算に帰着する問題はyukicoderで一回解いていたのだ。とはいえEが通っていたとしても組み切れていたかはわからないが。
総括
Dまでのムーブは大体よかった。バランスよくいろいろな方面に思考とエスパーを巡らすことができ、それが功を奏した。
Eで1時間強も椅子を温めることになったのはかなり厳しい気持ちになるが、時間配分やレートロスの最小化を考えた際に適切な判断ができていなかったのは問題だと思う。Fはやらずに順位表の動向だけ適宜見てEに取り組むべきだったかもしれない。
一方で、思考に詰まったときにこれを回復する術の習得が必要なことがわかった。試しに、ビハインドな上に思考の詰まった状況になってしまったら外を走ってこようと思う。
また、数学寄りの問題への習熟度の低さが露呈したので（というよりも考察のボトルネックが数学になっている）これもこどふぉなどで頑張って研鑽していきたい。
ちなみに最近すまーとうぉっちを買ったので、コンテスト中身につけていた。
ストレス値はコンテスト中ずっと低い状態で、心拍数がコンテスト開始時102 bpm、徐々に下がって22:00には76 bpm、最後10分は追い込みで103 bpmとなっていた。
80~90 bpm付近の頃は（問題が簡単なのもあるだろうが）エスパーが冴えていた。サンプル数が少ないのでよくわからないが、心拍数はある程度高い方が思考には向いているのだろうか。100 bpmあると流石に思考と脈のリズムが噛み合っていないような感じがした。
ちなみに、平静時は60 bpm程度なので、心拍数の爆上がりする競プロを毎日10時間やる生活などをしているといずれはしぬとおもう。
AtCoder Regular Contest 114 反省
A, Bが明らかにABCのものより難しいのはさておいて、Cを通せなかったのでただの速解き2完になった。
結果を鑑みて
700 25:31
全体547位、レート-16となった。ARCで２完などをやるとだいたい-30くらいは覚悟しなければならないことが多いが、今回はちょっと優しめの減少だった。
A - Not coprime
パッと見でGCD、LCM系の問題に見えたのでLCMをとってみたが普通にサンプルが合わないのでよく見ると昨日見た問題に酷似していた。
恐る恐る提出するとAC 7分弱かかった。
この時点では200位ちょっとくらいだったと思うので、そこまで焦らずに済んだ。
B - Special Subsets
パッと見で特に思いつくものはなかった。
少し考えると、f(a)=b, f(b)=c, f(c)=aみたいに有向閉路になる部分はひとつにまとまることに気付くので、SCCを持ってきた。
そこから、強連結成分分解した有向グラフ上のパスを数える問題だ と解釈したわけだが、これは正しくなかった。入次数をうまく管理しなければならなかったりして複雑な実装になる予感がした。
そんなこんなでここで時間を使ってしまったが、有向閉路の考察に立ち返って、有向閉路の集合になることがTの必要十分条件であることを疑った。この考えは正しかった。正当性を厳密に考えることはできなかったが、辺の本数がN本であることがうまく効いてくれていることを信じて提出するとACした。この問題にはなんと20分近くかけている。たまげた......
順位は微妙になったがCが解けそうな見た目をしていたので取り掛かることにした。
C - Sequence Scores
パッと見で最適な操作はわかった。この段階では種類数がそのまま答えになると思っていた。その線で実装すると値が合わないので、ノートで実際に実験して次の性質を洗い出した。
・種類数がそのままコストにプラスされる
・A[i + 1] > A[i]であるとき、コストに+1
1番目の性質は良いのだが、小さなサンプルばかり考えていたせいで2番目の性質を俯瞰して検証することができなかった。主客転倒でdpを組むと最後のサンプル以外はすべて合っており、ここから1時間ほど考えていたがついに2番目の性質を拡大することはできなかった。
毎回そうだが最後の1,2分は正常に考えるのが難しい。時間がなくなるほど俯瞰してみるのが困難になる。
値・要素数の比較的大きなケースを考えること。愚直実験コードを作ること。などが反省として得られた。
総括
愚直実験コードや大ケースでの実験は問題の考察を進めるうちの早い段階で作っておかないと精神力が足りなくなり、また、「今更作っている余裕があるのか」という逡巡が入ってしまうためミスに繋がりやすいかもしれない。
ただ、問題にどのくらいの時間を割くことになるのか推定するのは難しいので（Cはパッと見た感じうまくいけば30分以内に終わるだろうと踏んでいた）比較的難しい問題に対しての時間感覚を身につけることが必要になってきそう。
パナソニックプログラミングコンテスト(ABC195) 反省
よかったんじゃないかな。うまくキリ番を踏めれば賞金もありうるというところ。
結果を鑑みて
2400 46:58
橙パフォ、全体33位、レート+60とかなり良い成績だった。B問題の凶悪さにもペースを乱されることなく進むことができた。周りもBで詰まっていたので遅れを感じずに済んだのが大きい。
実装の軽い問題が多く、いずれの提出コードも700byteを超えない程度のものであったことも速解きにつながった。
A - Health M Death
パッと見た感じ、ただの倍数判定なのでやるだけだった。46秒で通した。
B - Many Oranges
パッと見た感じ、除算についての問題でO(1)で解けるものだろうと踏んだ。同時に細かな処理（切り捨てとか切り上げとか） が面倒臭く、実装によってはコーナーケースが無限に生じうることを予感した。あとMがキログラム単位でびっくりした。サンプル見て首を傾げていたのだけれど、これに気付くとちょっとだけむっとした。
制約を見ると、全探索が可能そうに見えた。つまり、O(1)を頑張るか全探索するか選べる問題だと理解した。こういうときは経験的に全探索を選ぶのが速さ・正確さ共に安定することを知っていた。そういうわけで全探索路線に切り替えた。
全探索できる項目は少ないので、すぐにオレンジの個数についての全探索が思い浮かんだ。そしてこのときの最適な１個当たりの重さは個数nに対してW/nであることもさっと証明できた。（２つのオレンジの重さをW/nからずらそうとするとW/nであった時より得をすることは絶対にない。）
そういうわけで何とか通せた。解法の逡巡などがあり8分かかった。CかD問題相当に見えた。周りも同じくらい手こずっていたので焦りは感じずに済んだ。
これが初参加のコンテストの人とかってこの問題でどういう気持ちになるんだろう。
C - Comma
パッと見た感じ、O(logN)の解法がぼんやりと浮かんだ。10^3, 10^6, ...といったカンマを打つタイミングの数に注目した。
この第一感は正しく、特に証明はしなかったが適当に式を合わせるとサンプルも合ったので提出した。2分ほどでACできた。Bの方が難しかったなと感じた。この時点ではそこそこ良い順位だったとおもうので（スピードが出ている時は順位表を見る癖がある。精神安定に繋がる。逆の時は逆の作用を持つ。）良いテンポで進んでいたと思う。
D - Shipping Center
パッと見た感じ、制約や入力などからナップザック問題の前計算によってクエリO(1)、あるいは半分全列挙のbitDPなどの解法を連想した。（実態に即してはいない。あくまで「そういう解法があてはまるかもな〜」という予想。）
内容がごちゃごちゃしているように感じて、すべきことや本質などを探るのに時間がかかった。全体感を掴み取るのに5分近く使っていたのではないかと思う。これは、ちゃんと考えればすぐに掴めた本質をエスパーで適当にさらって掴もうとしたために起きたロスだと思う。それでもエスパーをやめてちゃんと考える方にシフトできたのはよかった。
ちゃんと見ると制約や入力はナップザック然としているが問題は全くナップザックではないことに気付いた。それと同時に雑な貪慾法が生えた。O((NM+MlogM)Q)程度の計算量だが、パッと考えたところ計算量には十分な余裕があるように見えた。ソートと貪慾の正当性は感覚で理解していたが最後までナップザックオーラを放つ問題文が怖くて祈りながら提出した。何とかACをとれたのでよかった。
この問題は焦ると解法ガチャをミスったりそれに固執したりして取りこぼしやすいような問題に見えた。パッと見た感じはE問題相当、解くとD問題として妥当な難易度に思えた。
この時点でかなり精神に余裕が生まれた。
E - Lucky 7 Battle
パッと見て、ゲームdpかな という感じだった。
大正解、というかこの形式だともうそれくらいしか疑う方法がないのだが。問題文についてサンプルなどを見て理解しながらコードを組んだ。
ゲームdpは最終局面から遡るのが定番である。S, Xは予めreverseしておいてdpを書いた。ループ中では7*Nの状態を追うことになるが、ゲームdpを書いたのが久しぶりなのがあって、逆再生するような配るdp(つまるところ貰うdp)として組む時に少し遷移を書くのに手間取った。最適戦略の基本に立ち返ることで何とか遷移を決めることができた。
あと、ゲームの始状態は0 mod 7の状態になるわけだが、 これがなんだか自信がなくてこれも祈りながら提出した。間違っていても取り返せるくらいには先行しているし という気持ちがあって思い切って出せた。なんとかACを取れた。この問題には12分近く使った。コードの構築に一番時間がかかった。
F - Coprime Present
パッと見た感じではB-Aについての奇妙な制約が目に止まり、区間篩を連想した。また、なんかすごい方法によるbitDPもどきとか。あとは独立集合の数え上げについてググった。
3~5分のうちにとんでもないひらめきがあった。73以上の倍数が72個の連続する整数に2度以上現れることはないのではないか というものである。このアイデア自体は恐らく何度か目にしたことのあるものである。
この気付きの後は上記の解法を並行して考えつつおはなつみに向かった。リフレッシュは大切で、精神的な余裕は解法を落ち着いて精査する余地をもたらしてくれた。ここで大方の方針は決まり、戻ってくると72以下の素数の個数をググった。
あとはいい感じに進み、ただpypy特有のTLEが怖かったのでインラインにしたりなど適度な定数倍改善を含みつつ提出し、ACを得た。
Bで2ペナくらいしてたら焦りでこの問題は解けなくなっていたと思う。
総括
制約をがっつりと見てそれに即した解法をエスパーしたり、それとは関係ない方向にも考えたり、今回のムーブはバランスが取れていて理想的だった。実生活における心配事は減ってきていて（というか際限なく後回しにしているだけなのだけれど）、それが安定したプレイングの土台になったのかなと思う。
ちなみに、INHOPではないがこの週は乾燥させたホップの株から出したハーブティーを毎日のように飲んでいた。香りは香ばしく精神安定作用があるように感じた。味は......
因果関係はないのかもしれないけれど、ひとつひとつの小さな調整が実を結んでいってくれるといいな。次はどうなるのかな。
AtCoder Beginner Contest 194 反省
今回からコンテストの反省を書くことにした。いつもいつも何千字も書けるとは限らないが、可能な限りやろうと思う。
解法にはあまり触れない。解に至る過程で辿った思考と精神状態を中心に書いていこうと思う。
結果を鑑みて
1500(1) 39:09
レートが+1された。簡単な問題で詰まったり変なミスが多かったので微増で耐えたのがほぼ奇跡のようなものだが、低難易度に対する直観力が少し鈍っている気がする。新adminになってから少しずつコンテストの傾向も変わってきているので弱点を作らないように取り組んでいきたい。
A - I Scream
パッと見た感じでは場合分け、B問題相当に見えた。
解いていくと「A問題だしいいだろ」と思って読み飛ばしていた部分に重要なことが書いてあったりして結局3分も使ってしまった。
単純な場合分けだが、乳固形分が与えられないとかラクトアイスは乳脂肪分ではなく乳固形分が3%以上であるとか、詰まる部分がままあった。
B - Job Assignment
パッと見た感じ、ただのソート系の問題に見えた。B問題として妥当そうな難易度だと思った。
解いていくと、ソートして貪欲にそれぞれアサインした時に同一人物かどうかの判定が必要になることに気付いた。これだけなら(かかる時間, index)を持たせてソートしてあげれば判定は容易だが、その判定が何度も連続したりすると色々面倒くさそうに見えた。
第一感はそんなわけではずれ。ちらと制約を見ると二乗で良さそうなことに気付けるので後は普通に二乗ループを書いて通した。
第一感に引きずられて制約を見落としてしまい、4分も使った。
この時点では予想外の出遅れに焦ったが、どうせ後ろの方の問題で巻き返せるだろうと自己暗示をかけることでなんとか平静を保った。
C - Squared Error
Errorというのはこの場合は誤差のことだと思うが、この形式で何が誤差なんだろうか。（というより何が真値になるのやら）不思議だね。
パッと見た感じ、「こういうのはパターンが決まってるから得意なんだよな〜」という気分になった。C問題にしてはやや難しめ、D問題相当に見えた。先ずは雑な展開により総和と二乗和を使う方法が思い浮かんだ。
この時の第一感は正しかった。何度かこのような問題を解いているのでこうなることはすぐに直感できていた。しかし、暗算でやった雑な展開でどうも係数をミスったらしく答えが合わず首を傾げていた。
そのまま10分近く経過し、流石にまずいと思ってループを回すことにした。ループとΣやΠは読み替えが効きやすい。iを固定してjについて計算することを考え、なんとかiの逆順に回していい感じにコードを書いてACできた。
最初で躓いてえらい目にあう という経験はABCで何度か経験しているので「ああ、またこれか......神よ......」といった焦りを通り越した諦念の気持ちでその後の問題を解き進めることとなった。
D - Journey
基本的に期待値を使う問題は簡単なものしかやっていないのであまり慣れていないところがある。だからパッと見た感じは少し嫌な気分になったが、ここまでくると何をやろうがビハインドなので落ち着いて読んだ。文自体は短く、そのおかげもあってか考察がこれまでとは打って変わってすんなりと進んだ。
コンプガチャ系の問題にありがちな、ある状態へ遷移するために必要な操作回数の期待値がその状態へ遷移する確率の逆数になっているという性質、そして状態は頂点番号ではなく未踏の頂点の個数を持つだけで十分だということに気付いた。
前述したように、期待値問題はあまり自信がないので祈りながらコードをテストした。コーナーとかもよくわからないのでエイヤ！と提出するとACが返ってきた。このときは相対誤差とかあまり気にしていなかったがdecimalを使わされることになるかもしれないし、ちゃんと制約は読んだ方がいい。今回はここまでかなり読み飛ばしによるミスが多かった。
結局この問題は2分ほどで片がついたので精神的には少し楽になった。
E - Mex Min
見慣れない制約の書き方をしていて、ひょっとして有効数字が2桁だからN=1549999とか出るのか とか意味わからんことを考えた。
パッと見では「たぶん解けるな」と思った。制約から察するになんだか線形計算量で解けるっぽい。SWAGや尺取法が似合う問題に見えた。
第一感はおそらく正しかったが、5分ほど考えたあたりでふと部分問題に何となく既視感を感じた。試しに range mex queryで検索すると見たことのあるウェブサイトに到達した。どうもSegment Treeで区間mexクエリ（この問題のものとは少し違うが）が解けるという内容っぽく、詳しく読むとこれを利用した解法が思いつけた。
線形計算量の方針で考え続けても恐らく解法にはたどり着けたのではないかとは思うが、たぶん時間かかって破滅していたと思う。それまでの考察を一旦置いてgooglingできたのはコンテスト中のムーブとしては悪くなかったと思う。
それはそれとしてSeg木を引数でバグらせて1ペナつけたのは注意力散漫としか言いようがない。
とはいえ、だいたい考察を置いて検索に頼る時というのは行き詰まっている時なのでこれは後で線形計算量で解いてみようと思う。
F - Digits Paradise in Hexadecimal
これは解けなかった。
パッと見た感じ、桁dpに見えた。順位表を見ると自分より10分も前に手をつけている人たちがこれを通せていなかったので一筋縄ではないんだろうなと思った。
桁dpを考えると状態数だけでO(logN * (2^16))となり、とても間に合わない。
「こういうタイプの問題は遷移のうまい省略でインラインdpにするんですよね〜」と思って考えるが、時間ばかりが過ぎた。
そんなこんなであんまりうまく進んでいなかったが、終了20分前くらいで境界を走っていない状態（たとえばN=1000なら09??とかを含む状態）からは遷移させずとも組み合わせの計算でちょうど種類数がKになる時の場合の数が計算できそうだということに気付いた。そこからは集中して取り組み、コンテスト終了後30分まで考えることができた。
考えた結果、この解法の過程で必要になる包除の計算量がデカすぎるということになった。ああ〜〜（脳みそが溶ける音）
この問題も方針新たにもう一度解く。
総括
変なミスや読み飛ばしが多かった。注意力散漫だったと思う。奇跡的に冷えずに済んだが、-30ぐらいあってもおかしくないムーブが多かったので気を付けたい。こういう注意力が散漫な日、みたいのは実際の心配事に起因している可能性があって、実際に私は来週の月火と心配の要因になるような出来事がある。だからといって対処案はないのだけれど。
BGMは環境音がいいという話を聞いて、コンテスト中のBGMを図書館の環境音にした(BG"M"とは言わないかもしれないけど)
1年間同じBGMでコンテストに臨んでいたのでこれによるルーティンのアドバンテージはないけど、これが今後うまくいってくれると嬉しい。
