/ 最近 .rdf 追記 編集 設定 本棚

脳log[20240608]



2024年06月08日 (土) [AtCoder] 今日はサントリープログラミングコンテスト2024(AtCoder Beginner Contest 357)があった。F 問題が解けず、問題の理解があやふやで早解きも失敗し、冴えない結果だった(確認はしていない)。以下ふりかえりを。■A 問題「Sanitize Hands」。シミュレートして使用後の残量が負でない人数。境界を探そうとすると1差で間違えそうで怖い。手のない宇宙人が紛れていると話がややこしくなるんだけど、そういう面倒がない 1≦H という制約だった。■B 問題「Uppercase and Lowercase」。やります。ASCII の6ビット目を数えるという猪口才な判定法。■C 問題「Sierpinski carpet」。今日のつまずきはここから。再帰関数でやろうかクラスでやろうか文字列操作でやろうかいつまでも迷っていた。結局文字列配列を敷き詰めて拡張していく操作が簡単で短かったが、15 分かけた。■D 問題「88888888」。まず勘違い。与えられる N が整数型に収まらないサイズだと勘違いしていた。文字列として各桁を扱わなければいけないのだと思って解いていた。求めるものは初項、公比、項数が明らかな等比級数なのだけど、項数が mod 998244353 だとサンプル3の答えが合わない。Integer Sequence Fair を解いたこと(20230327)が糧になっていない。mod をそのまま指数にはできない。で、繰り返し二乗法を自分で実装しなければいけないのかと思って N が何ビットになるのか確かめたら、60 ビットで足りるようだった。なんだよー。公式に3数を当てはめるだけのことに 20 分かけた。■E 問題「Reachability in Functional Graph」。これも勘違いがひどかった。N 頂点 N 辺だというから、輪っかが1つのなもりグラフなのだと思って解き始めたのだけど、このグラフは連結でも単純でもなかった。サンプル1に言及があったのだけど、自己辺がある。それではと複数のループとループに繋がる毛が生えているグラフを想像してサイクルと直線を検出する関数を書き始めたのだけど、サンプルの3が合わない。枝毛の可能性を考慮していなかったせい。問題文の最後にわざわざ「特に、u=v の時は常に到達可能です」と書いてあるのも読み飛ばしていてカウント漏れがあったし、もう散々だった。およそ 40 分かけて変な関数を書いた>提出 #54372312 (AC / 316 Byte / 227 ms)。順方向と逆方向の DFS を2回やるらしい強連結成分分解をそらで書くことがまだできないので、変な関数を発明しがち。出次数がすべて1だという条件があるから、強連結成分分解はオーバーキルなのだと思う(だから変な関数で解ける)。■自分のすべての提出。■■■C 問題。再帰バージョン。提出 #54407583 (AC / 276 Byte / 138 ms)。結局のところ実装の方針に迷っていたというのは、どの方針にしろ実装を最後まで見通せなかったために二の足を踏んでいたということなのだろう。実装力が足りない。■■■級数という言葉について。ちょっと検索したら、級数というと普通は無限項の和を表すみたい。特定の範囲を除いて0と定義することで有限個の和を表すこともできて、そうでないことを示すために無限級数という言葉も使われるけど、基本的に無限個の和なんだって。「級数」(ja.wikipedia.org)。そうかー。等比数列の和って言わないとだめなんか。長ったらしいなあ。てっきり、並べたものが数列で、並べて足すものが級数なんだと思ってた。