脳log[20231028]

2023年10月28日 (土) [AtCoder] 今日はパナソニックグループ プログラミングコンテスト2023（AtCoder Beginner Contest 326）があった。自分のすべての提出。では ABCDE のふりかえりと F の精進を。F 問題を通すには時間が 15 分足りなかった。D 問題に 50 分かけていなければと悔いが残る結果。■A 問題「2UP3DOWN」。慎重に X と Y の大小を比較してから階段を使うかどうかを判断した。■B 問題「326-like Numbers」。ちょっと前に 321-like Number というものが出てきた。今日の 326 は３桁であることが明白な定義なので易しかったと思う。■C 問題「Peak」。尺取りです。■D 問題「ABC Puzzle」。最大で 5×5 のグリッドだけど、(5*4*3)^5 大なり７億なので愚直総当たりが許されるというわけではない。だけどまあ、ちょっとだけ工夫すれば総当たりに近いことはできる。グリッドが条件に違反していないかを判定する関数を書いてから１行ずつ文字を埋めて判定を繰り返した。実装問題でまんまと時間を使わされた。下手かよ。■E 問題「Revenge of "The Salary of AtCoder Inc."」。名前でにおわせているけど給料に関する問題を解いたことがある。調べたら「AtCoder社の給料」だった。だけどそんなことは今日の問題を解くのには関係がない。答えが合わないからデバッグのためにまずは小数で答えを出すことにした。たぶんすごく簡単な式で答えが出そうな気がするけど、頭がないので手続きを踏んで答えを足し合わせた。今ここにいる確率というものを１つ変数に記録しておいて、A 数列を順番に見ていった。A[i]×(今ここにいる確率) がまず答えの一部。そしてまだ見ていない A 数列の要素にとっての今ここにいる確率というものは、いま今ここにいる確率の N 分の１だけ増える。■F 問題「Robot Rotation」。こういう設定の問題知ってるよ。成分を上下成分と左右成分に分けるやつ。DP をするかと制約を見たら N の上限が 80 と意外に小さい。成分に分けるとそれぞれ 40 だ。2 の 40 乗はべらぼうな数なので各要素をプラスに利用するかマイナスに利用するかを総当たりはできないけど、半分ならどうか。2 の 20 乗はおよそ 100 万でちょうどいいサイズ。100 万と 100 万の組み合わせを総当たりはできないけど、足して X,Y になる相方が存在するかの判定は定数(っぽい)時間で行える。ここまで考える要素はなかった。しかし実装するのに十分な時間もなかった。残念。■出ました。コンテスト成績証。青パフォで上がりはしたけど上がり幅が足りない。F 問題解けてたよ！■D 問題。自分のこの提出 #47031545 の判定関数 OK だけど、前半と後半が繋がっていないので前半の判定結果が捨てられている。嘘判定なんだけど、行方向に関しては制約に違反しないように F 関数の方で配置しているのでセーフだった。怪我の功名。どちらかの関数で行と列の扱いが逆なら間違いだった。