/ 最近 .rdf 追記 設定 本棚

脳log[2024-04-08~]



2024年04月08日 (月) [AtCoder] 先週末にあったトヨタ自動車プログラミングコンテスト2024#4(AtCoder Beginner Contest 348)のふりかえりと精進について。■A 問題「Penalty Kick」。サンプルを出力して気がついたけど、oox の繰り返しを必要な長さ出力するだけだった。だけど各 i についてそのつど判定する方が簡単だったのでそのように。■B 問題「Farthest Point」。距離の比較をするのにルートはいらない。Ruby には Math.hypot (sqrt をとる) の2乗の値を返すメソッドがあると思ってリファレンスを見たけど見つからなかった。たぶん Complex#abs2 のことが頭にあったのだと思う。解法は愚直総当たりで最初に見つかったものを答えにする。素直に書けば「番号が小さいもの」という条件は自然に満たされる。■C 問題「Colorful Beans」。色でグループ化してグループ内の最小値の最大値を出力する。要は悲観主義者が最もましな選択肢を選んだ場合がどうなるかという話。この C 問題まではプログラミング言語の扱いが問われている。やりたいことが書けますかと。Ruby で参加しているなら、C 問題は Array#group_by を知っていますか、という問題だった。■D 問題「Medicines on Grid」。グラフですよね。S と T と薬のマスを頂点として、同じ頂点を2度通らずに S から T へ到達できますかという問題。これは訪問済み頂点を記録して DFS でやろうか。そして頂点間の繋がりがグリッドで与えられていて、探索をしなければ明らかにならない2段構えになっている。最初はきれいに2段に分けて解こうとしたんだけど、面倒くさくなった。最初のグリッド探索のついでに到達可否の判断をしてもいいじゃないか。プライオリティキューを使わずにテキトーにキューに探索地点を追加してエネルギーを記録していった。これに 50 分くらいかけたんですよ。それはダメ。■E 問題「Minimize Sum of Distances」。全方位木 DP。頭が破壊されました。こういうのは終了したあとでじっくり落ち着いて書きたい。終了3分後>提出 #52114566 (RE)。頂点番号を1始まりのままにしていたのに、0 から N-1 を処理対象にしてしまったせいでエラーになっている。終了 13 分後>提出 #52115938 (AC)。結局惜しくはなかった。今日になって全体が見通せる状態でイチから書いたもの>提出 #52179331 (AC)。最初からこれがすらすら書けないのは理解が遅いってことだよ。


2024年04月04日 (木) SO2R。手っ取り早い攻撃力アップ手段である、アトラスリング、バーサークリング、ルナティックピアス、メテオリングについて。アトラスリングの効果は ATK+100%。つまり物理攻撃力2倍。残念ながら2つ付けても +100% のまま増えない。参考までに、ATK+20% のファクターとは効果が累積する(複利ではなくベースの数字の 120% が加算される)。バーサークリングの効果は怒り効果でダメージ2倍。敵の防御力が高いときは ATK を増やす方が効果的だと PS 版の攻略本で読んだが確かめてはいない。PS 版ではアトラスリング+アトラスリングとアトラスリング+バーサークリングの組み合わせ比較に意味があったのだ。すでに書いたように SO2R ではアトラスリング+アトラスリングの組み合わせに意味がないので、基本はアトラス+バーサーク。メテオリングの効果はヒット数+1。1回殴るとダメージの数字が2つ出る。バーサークリングとの違いは、たぶん必殺技に効果が乗らないだろうという点。戦士キャラには向かない。ダメージ上限を 9999 から増やすスキルがあるので、ガントレットより源氏の小手を選んだほうがいい理由もない。これは FF6 の話。自分のように呪紋キャラであるレナでボコスカ殴る場合にはバーサークリングの代わりに装備してもいいと思う。ヒット数+2であるスレイヤーリングはまだ持っていないので今は考慮の外。ルナティックピアスの効果は ATK+200%。なんとアトラスリング2つ分の効果。その代わり命中(HIT)マイナス 50% の効果も付く。HIT と命中率の関係式は知らない。常に背後をとるようにすればいいんじゃないでしょうか。ピアス系のアクセサリは女性限定。そしてお子様は付けられない。実際は個別に差違があるのだけど、ルナティックピアスに関して言えばセリーヌ、チサトが OK で、レナ、プリシスが不可。不審人物ウェルチが OK なのは、17 (レナ) と 18 (ウェルチ) のあいだにお父さん的ボーダーがあるってことなの? そしてルナティックピアスは効果が重複する。なんと ATK+400%。なぜか HIT マイナス効果の方は重複しない。つまり2つ装備するとプラス効果は2倍だけどマイナス効果は2倍にならない。なにそれおいしい。これの罠は、ATK 上限が 9999 だということ。本編シナリオをプレイ中の現在でもすでに上限に当たってしまう。それならバーサークリングと組み合わせるのがいいかも。ここで、隊列効果の ATK+60% の扱いが気になったので調べてみた。つまり、ATK 9999 の状態で ATK+60% の隊列効果に意味があるのかどうか。結果は、10000 程度のダメージが 16000 程度に上がっていたので、素直に 9999 を超えた ATK の数字がダメージに反映されていると思う(あるいは ATK+60% の隊列効果とは物理ダメージ 1.6 倍という意味なのか)。こうなると、キャラクターのパラメータである ATK の上限が本当に 9999 なのかを疑いたくなる。実質の上限なのか見かけだけの上限なのか。テキトーに比較した感じ実質の上限っぽかったけども、現状では 9999 を大きく超える ATK が作り出せるわけではないので、微妙な数字を比較した結果ではある。だけど期待はしていない。


2024年04月03日 (水) 9年ぶり2度目にお風呂で死にかけた話。お風呂で 15 分ほど本を読んでから湯船を出て歯を磨いていた。胸がずんずん苦しくなってきて吐きそう。吐いたら楽になるかなと考えるけど吐けない。床に倒れ込んで楽になりたい気がするけど、楽になるはずもない。だけどひたすらに胸が重苦しいので、どうにかして解放されたいのだ。さっきから便意があるのも吐き気と連動しているのだろうか。お風呂に入る前にもう出してるんだけど。ここで、あ、これ脱水でのぼせてるんだと気がついた。経験があるから今度は少しだけ気がつくのが早かった。15 秒くらい。のどの渇きはないけどシャワーのお湯を3口飲んで様子を見る。楽にならない。倒れ込みそう。倒れる前にうんこを出しておきたいと思った。体を拭いてトイレへ。出したあとたぶん5分くらい朦朧としていた。なかなか良くならないので飲んだのが3口では足りなかったかと不安になる。でももう動けない。水分が減っているということは血圧が低いだろうと思って、頭を下げるために肘をついて床を眺めていた。上半身に支えが必要だったということもある。そうしているうちに徐々に頭のもやと胸の苦しさが晴れてきた。濡れた肌に夜の冷気が心地よい。そのあとはお風呂に入り直した。寝る前に飲むためのお茶をお風呂に入る前に淹れていたのだけど、飲むタイミングが間違っていたね。だけどのどは渇いていなかったのだ。■今日は朝からいつもと違っていた。いつもは遅い朝食を用意するときに急須に 500 mL ほどお茶を淹れる。食後にココアも作る(300 mL くらい)。ココアを飲んだあとの口直しにティーバッグでコップ半分くらい(140 mL)のお茶も淹れる。それがどういうわけか今日に限って 140 mL だけで満足していた。今日一日それだけで満足していた。感覚がバグっていたのだろうか。数字で管理しないといけないのだろうか。■しかし、この日記を書くにあたって検索してみたら、前回(20150115)がもう9年前だったということが驚きなんですよ。感覚に従えば3から5年前くらいというのが妥当。年をとればとるほど体感時間は短くなるらしいが、それは生きてきた時間を尺度にして時間を計るからなのか。年の数で計る余命より体感する余命はずっと短い。


2024年03月30日 (土) [AtCoder] 今日は AtCoder Beginner Contest 347 があった。コンテスト成績証自分のすべての提出。CDE が緑 diff で、その次の F が黄 diff の壁だったらしい。緑 diff の問題を解いて青パフォをもらって自己ベストにあと6のところまで戻ってきた。なんだかなー。AC までの所要時間が A=1分程度、B=1分ちょっと、C=15分、D=19分+ペナルティ5分、E=11分。■A 問題「Divisible」。% 演算と / 演算。Array#filter_map がぴったり。■B 問題「Substring」。制約が小さいので全探索。文字列を切り出して重複を除く。ところで、前回の B 問題 Piano も同じような全列挙、全探索だったのだけど、Ruby で一番最初の提出だったこちら(#51548594)が WA だった原因は、間違いがあるとわかって探してもなかなか見つけられないのではないかと思う。実際二度見三度見しても見つからなかった。対処法の1つは #51616574 のように、combination に代えて repeated_combination を使うこと。もうひとつは今日の B 問題への提出 #51816314 で採用したように、文字を切り出す範囲を表すのに .. (終端を含む) に代えて ... (終端を含まない) を使うこと。要するに、長さ1の部分文字列を表現する方法が確保されているかどうかが WA と AC を分けている。一般的な文字列検索と正規表現検索との違いで顕在化しがちな問題として、特定の位置の空文字列を表現する方法があるかどうかというものがある。普通のテキスト検索では長さ0の文字列を探すことも見つけることもないので、表現能力の不足に気がつけないことがある。C++ のイテレータが開区間ではなく半開区間なのは、こういう理由からもよくできてるなと思う。いいものはどんどんまねしよう。そしてこれはトリビアだけど、サイズ N の配列 A があるとき、A の末尾の要素は A[N-1] であり A[N] の読み取りは不正だけど、A+N が A+N-1 より大きいことが C 言語の規格で保証されているらしい。でないと範囲が表現できないもんね。■C 問題「Ideal Holidays」。配点が +50 の 350 点ということでやや難しめだと予想できる。実際その通り。予定が A+B 周期で何日目に当たるかを求めてソートして、順番に各要素が休日の1日目にあたると仮定して N 個後ろの予定が A 日目までに収まっているかを判定する。提出直後に同じ日に複数の予定がある場合に正しく判定できないことに気が付いたのだけど、今見ると制約によって重複が排除されていた。優しい。そして今一度よく考えると、D%(A+B) したときに重複が生まれる可能性がある。重複する予定が3つあったとして、最初に処理する予定に限って正しく判定ができるので、結果的に問題がなかったのだ。■D 問題「Popcount and XOR」。C は最大で 60 個のビットを持っており、立っているビットを X または Y のどちらかに割り振る。割り振るのはどちらでも良いが、popcount(C)<a+b のときは C のビットが立っていない位置で X と Y の両方にビットを割り振って打ち消し合わせる必要があるので、a と b の大きい方に 1 のビットを割り振るのがよい。最初に WA×1/RE×1 を出したが(#51837959)。7分後に AC (#51842648)。両方の提出でやっていることは同じ。ただ、RE/WA を出した方では、不可能なケースを最初に判定するようにしていた。一方の AC 提出の方では、操作をしたあとで、結果が満足しているかどうかで出力を切り替えた。要するに、不可能なケースの判定に漏れがあったのだ。おそらく C の0のビットが a, b の大きさに対して不足している場合を弾き損ねていた。最初に提出する前に不安はあった。だから普段書かない assert、……はないから raise を埋め込んで前提が間違っていないかを確かめていた(その結果 RE が出ている)。残念。■E 問題「Set Add Query」。所要時間によれば CD より簡単でしたよね。まず、各時点での集合のサイズというのが操作をシミュレートすることで予め求めておける。次に、各 x (1≦x≦N) について集合に含まれていた区間を調べる。これはクエリを順番になぞりながら値 x からクエリ番号の列を逆引きできるように記録をとればよい。クエリの列から2つずつ取り出したものが x が集合に含まれていた区間。■今回は水 diff と青 diff が問題セットに含まれていなかった。今日の自分は緑 diff 以下の簡単な問題に滅法強いマンとしてレートを稼いでいる。仮にここに水 diff の問題がプラスされると、水 diff の問題にはそこそこ時間がかかるので、水 diff 以下の問題に滅法強い人にタイム差をつけられて相対的にパフォーマンスが下がる。さらに青 diff の問題がプラスされると、自分は青 diff の問題は時間内にほとんど解けないので、青 diff が解ける人に点差をつけられて、やはり相対的に自分のパフォーマンスが下がる。しかし水も青もなかったから、自分を含めて黄 diff が解けないグループがひとまとめにされて、緑 diff の問題で優劣が判定された。それで青パフォをもらうのは、なんだかなーだよね。


2024年03月29日 (金)

最終更新: 2024-04-03T08:25+0900

[AtCoder] パ研合宿2023 第1日「SpeedRun」

AtCoder をプラットフォームとして利用する有志コンであり、AtCoder の問題ではないけども、競プロカテゴリとして AtCoder に分類しています。

リアルタイム参加はしていない。ABCDFHIE をこの順に解いたのでふりかえって書く。

 A - Kazuate Game (100 点)

出現数を数える。Array#tally そのもの。

 提出 #51702284 (AC / 67 Byte / 103 ms)

 B - Cutting Circle (100 点)

2本の線が一致することはないので、必ず3つか4つに分割される。ソートするなりしてうまく分類する。

 提出 #51702526 (WA)

うまくできませんでした。

 提出 #51702670 (AC / 146 Byte / 51 ms)

 C - Infinity (200 点)

数列が a,1,b であるとする。そうすると、b=a+1、a=b+1、b=a+1 と操作を繰り返すことで無限に大きな要素を作ることができる。A[1]=1 の場合であっても、A[1] を無限大にすることができる。初期数列が1以上の要素を含んでいることが必要十分条件だと思いました。証明は知りません。

 提出 #51702806 (WA)

間違えました。最初は、2つの要素を足して1以上になることが必要十分条件だと思ったんだよね。証明は知らないとか言ってっからだよ。

 提出 #51702871 (AC / 62 Byte / 100 ms)

 D - Bishop (200 点)

すごーく難しかった。4回間違えた。順番に WA×13WA×3WA×2WA×1

まずは問題を理解する。X 座標と Y 座標について、正負どちら方向に移動することもできるけど、移動量の絶対値が一致していなければいけない。

どういう操作を構成するか。最初からずっと想定していたのは、まずは X 座標もしくは Y 座標の、ずれが小さい方の数字を一致させる。その後はずれが大きい方を、偶数回の操作で一致させる。偶数回というのは、先に合わせた方の座標をずらしたくないので、移動量を等分して打ち消し合わせるということ。

この考え方で WA×1 まで行ったのだけど、一方のずれに対して他方のずれが非常に大きい場合に答えが微妙に合わなくなる。

結論を書くと、最初に目指すべきポイントは近い方の座標ではなかった。偶数回の操作の折返し点を目指すべきだった。要するに、X 座標のずれが DX、Y 座標のずれが DY だとして、DX<DY なら最初に目指すべき点は DX+(DY-DX)/2 だったということ。DX だけ移動してから DY-DX を偶数回で移動するのではなく、DX+(DY-DX)/2 移動してから (DY-DX)/2 移動する操作を構成するのだった。

 提出 #51722059 (AC / 124 Byte / 127 ms)

ARC で 400 点ぐらい配点してもいい問題だと思います。400 点というのは、数学的センスがある人は瞬殺するけども、自分は1時間以上苦しむという、そういう問題。

 F - Mean Median Construction (300 点)

任意の部分列について成り立たなければいけないので、一番極端なケースを想定する。つまり、N=1 のケースと N=2 のケース、そして中央値に対して極端に平均を下げるような列を。

N=1 のケースでは中央値と平均値が一致する。N=2 のケースでは a1<a2 なる列の中央値が a1 なので平均値が必ず中央値を上回る。N>=3 の場合で N が偶数のとき、中央値より大きい値の数が小さい値の数より1つ多くなるので、平均値は大きくなりがち。だから N が奇数の場合だけを考える。もっといえば、N=3 で成り立つなら N=5 でも N=7 でも成り立つと思うんだけど、そんな気がするだけ。

N=3 のケース。a1<a2<a3 としても構わないのでそうする。平均を下げたいので a1 は最低の 0。a3 がいくつなら平均が a2 以上になるだろうか。2×a2 が最低ライン。N の制約が 20 万以下ということだけど、要素が倍々に増えていくなら ai≦10^9 の制約から実質的な上限は 30 程度になる。

 提出 #51724886 (AC / 114 Byte / 97 ms)

 H - Winter Road (400 点)

問題文の表現にひっかかりがありますね。「氷の張ってある道をなるべく通りたくないです」「氷の張ってある道を通る時間を最小化して街 N に移動するとき」。要するに氷が張っている道を通ることもあると言っている。01BFS みたいに、氷が張っている道を0回通る場合の最小値、1回通る場合の最小値、2回の場合の……、を N にたどり着くまで繰り返して求めれば良さそう。うまくやればいらないかもだけどプライオリティキューを使ってダイクストラ法をした。

 提出 #51749960 (AC / 1166 Byte / 674 ms)

01BFS ということでこれは2本のキューを切り替えながら使った。

 提出 #51755608 (AC / 968 Byte / 704 ms)

氷の上を何回通ったかと経過時間とを1つの値にエンコードすることで、キューを1本だけ使う普通のダイクストラ法になった。

 I - Swap and Sort (400 点)

まずは問題を理解する。ある要素を1つ後ろに移動し、その際に K を加算する、というのが操作。

最初は後ろにある要素に操作を繰り返して大きくすることで昇順の列を作ることを考えた。最低2つの要素があれば、交互に操作対象に選ぶことで任意の回数 K を加算することができる。2つの要素の初期の差を解消したり拡大したりすることはできないけど、1回の操作で昇順にできるので問題ない。

これの問題は K=1 で Ai が上限の 10^9 に近いとき。初期数列が A1=10^9、A2=1、A3=1 だったとして、A2 と A3 に操作を繰り返して A1 以上にすることは可能だけど、操作回数が 50 万を超えてしまう。

次に考えたのは、最小値を列の前に持ってくること。i 番目に最小値があるとして、i-1 から 1 まで下りながら操作することで A1 から A_{i-1} にそれぞれ K を加算しつつ、Ai を先頭に持ってくることができる。以降これより後ろの数列に対してどんな操作を繰り返したとしても、Ai より小さい値が後ろに出現することはなく昇順が保たれる。

初期数列が降順にソートされている場合が最悪ケースだけど、N*(N-1)/2 回くらいの操作で昇順になる。N≦1000 だからちょうど操作上限の 50 万回を下回るくらい。

 提出 #51750508 (WA)

しょうもないミスをした。

vector の任意の位置から値を追い出すときに、末尾の要素とスワップしてからポップするというテクニックがある。順番に意味がないときは使って損がない。

順番に意味はあったのだ。順番が保存されていないと正しい操作対象が選べない。いや、自分は壊れた順番の中で正しい対象を選んでいたのだけど、そのせいで勘違いしたのだけど、ジャッジが正しさを検証できなければ意味がない。

 提出 #51750693 (AC / 224 Byte / 278 ms)

 E - Thin Ice (300 点)

300 点だけど難しかった。これが解けたのが嬉しくて今日の日記を書いているところがある。

  1. K=1 ならひと筆書きということで、ケーニヒスベルクの逸話で有名な、次数に着目した判定法がある。
  2. でも K>=2 の場合は?
  3. たとえば1つの頂点から3つの頂点が出ているテトラポッド型のグラフの場合、ひと筆書きはできないけど、K=2 なら全ての辺を2回通ることができる。
  4. 2つの丸が1本の辺で繋がっているメガネ型のグラフはどうだろう。
  5. 円に直径を引いたような日型のグラフはどうだろう。
  6. 頂点数が最大 20 万個あるときに個別具体的な判定はできないよ。
  7. 最近の ABC-G で、グラフだけど木なんだと、木として考えていいんだというコメントを聞いた。
  8. 木だったら簡単に判定できますか?
  9. すべての辺をちょうど2回通ることで、木の根をスタートしてすべての頂点を訪れ木の根に戻ってくることができる。DFS のルート。オイラーツアーと辺の関係を maspy さんが書いていた。
  10. グラフを木+余分な辺と考える。なんなら余分な辺は余分な木かもしれないし、余分なグラフかもしれないが話は変わらない。余分な辺に寄り道をして戻ってきてまた DFS を再開することで、どんなグラフでもすべての辺をちょうど2回ずつ通って、任意の頂点をスタートして同じ頂点に戻ってくることができる。
  11. K が偶数の場合の答えが出た。
  12. K が奇数の場合、K=1 が Yes なら Yes だ。
  13. 提出 #51755274 (AC / 127 Byte / 291 ms)
  14. K=1 が No でも K=3 なら Yes になるケースがないとは確認できていないんだけど、どう考えたらないと納得できるんですか?

とある赤い亀さんの日記を読みました。

  1. 「K 倍してオイラー路」ってどういうことだろう
  2. K 回通る、ではなく、K 本の辺を1回ずつ通る?
  3. あー!
  4. 答えを聞いても理解できない鈍さが嫌になるね

学びのある問題だった。


2024年03月28日 (木) 一日のあいだに2つ続いたので「近しい」警察が出動しました。■1つめ。「659ccのエンジンはちょうど『1299パニガーレ』に搭載されるエンジン(デスモセディチ/2気筒)の片側の気筒に近しいイメージ。」■2つめ。「ゲームスピード自体が早めに設定されているためソウルライク作品とは大きく異なるプレイ感ではありますが、強敵やボスを倒せた時の快感は近しいものを感じました。」■(チカ)しいは(チカ)しいとも書く言葉で、(シタ)しいと読んだときと同じように親密さを表す言葉です。より一般的な近さを表すなら近いと書きましょう。余分な文字をくっつけたくなる心理的な傾向が、圧力要因がいくつか考えられると思う。無意識に安易に流されないことだ。つまり、近いという言葉を知らないはずがないのだから、どうしてあえて「近しい」と、結果的に筆者が知らなかったことが明らかになった言葉を選んでしまったのか、理由があるはずだということ。同じミスを繰り返さないために反省ができるはずだ。


2024年03月27日 (水) honto で去年の年末に8冊の本を注文したとき、そのうちの1冊の発売日が知らないうちにひと月ずれていたらしく発送予定が1か月後になっていて、お前正気か? と思いながらひと月待ったけど、昨日 Webike にセール品を含む3つの商品を注文したら、そのうちのひとつがメーカーからの取り寄せであり入荷予定が6月から7月だということがあとになって判明した。キャンセルの選択肢も見えるけど、お前正気か? と思いながら発送を待つことにした。だけど別のセールが始まってそのときの方が得だったらキャンセルして再注文するよ。こういうときアマゾンはオプションがどうであれさっさと分割して送ってくる。発送される荷物の個数が増えるコストを度外視している結果かもしれないけど、それを考慮に入れた場合でも、ひと月も3か月も(未来の未決の)注文と在庫を抱えて(現在の)販売機会を見逃すことに経済合理性はあるのかなと疑問になる。自分にとっても合理性はない。受け取りと支払いの手間が増えるとしても、さっさと送れる分だけ送ってくる方が良い。待てるから待つけどね。アマゾンで2年半待ってタイムアウトしたこともある>20180309


2024年03月25日 (月) 平易な言葉選びを心掛けていたコラムで「奇をてらう」と使ったら「どこの方言ですか?ここでは共通語を使うべきだと思います」とコメントが届いてびっくりした→さまざまな意見が集まる - Togetter」■読んでたら「俺も「とっぽい」って言ったら、どこの方言ですか❓って言われた事あるわ」ってコメントを見つけて笑っちゃったよ。自分が「とっぽい」という言葉を初めて見たのはスーパードクターKで、それ以外では記憶にないよ。さておき、(テラ)うは「衒いのない」とか「衒学」とか、奇を衒う以外にも用例があってそんなにレアではないと思うなあ。女衒のゲンとの繋がりはわからないなと思って引いたら「「衒」は売る意」とあった。繋がりはない? あ、『衒学始終相談』の2巻が来月発売です。これは競プロの話題なんですね。著者の人を知ったのが『レストー夫人』という別の作品を通してで、それをおすすめしていたのがたしか kinaba さんだったので。■以前にもちょっと書いたけど、自分は「(コス)る」ってどこの方言なんですか、と思ってるよ。ネットでは分野を問わず各所で珍しくない頻度で見かけるけども、自分の語彙にはない。ここで言っているのは摩擦するの意味ではなくて、用例を観察するに「執拗に繰り返す」ことを指しているように思える使い方。辞書に当たっても少しでも当てはまりそうな、こじつけてでも解釈できそうな意味は載っていなかった(擦る動作のイチ典型としての往復運動からの連想であろうとは想像する)。だから「片す」や「違くて」「違かった」と同じように、他所で使われているけったいな言葉、だと思っている。けったいも方言だけど、これは自分の言葉。


2024年03月23日 (土) [AtCoder] 今日はユニークビジョンプログラミングコンテスト2024 春(AtCoder Beginner Contest 346)があった。くやちい。F 問題を通すのに2分13秒足りなかった。こんなに悔しいことはない。ではふりかえり。■A 問題「Adjacent Product」。Array#each_cons を使います。■B 問題「Piano」。数が重要なのであって、W=5/B=2 のとき wwwwwbb が見つからなければいけないわけではない。wwbwwbw でもいい。なんで問題を繰り返してるかって? わからなかったからだよ。問題文のせいじゃなく思い込みのせいだよ。累積和でやるの? ややこしくない? とか思って先に CD 問題をやった。そのうちに愚直解法が許されると気がついたので愚直に文字列を連結して、愚直に文字の数を数えた。愚直といっても、初期文字列のサイズ(12)×(B+W)≦2400 だけどね。他の提出を見るともっと豪快なのがいっぱいあった。■C 問題「Σ」。1 から K の総和は K*(K+1)/2。A のうち K 以下であるものを選び重複を取り除いたものの総和を引く。■D 問題「Gomamayo Sequence」。まず、00 もしくは 11 にする場所を決めます。そうすれば、左に向かって 010101...を作るコストと右に向かって 010101...を作るコストの和、もしくは、左に 10101...、右に 10101...を作るコストの和が答えの候補になる。N-1 個の位置のペアに対して、答えの候補が2つずつ。そのうちの最小が答え。やりたいこと知りたいことが明らかになれば、うまいこと累積和を作って単位時間で答えの候補を求める。■E 問題「Paint」。逆順に考えれば上書きされずに塗れる数がわかる。あとは数えて記録するだけ。■F 問題「SSttrriinngg in StringString」。f(S,N) に対してどういう操作がしたいだろうか。ある文字について、あるインデックス以降で最初に現れる位置が知りたい。そして、そこから同じ文字がある個数現れるまでにインデックスがいくつになるかが知りたい。そのインデックスが f(S,N) に収まっているかどうか。これを k に対する二分探索の中で T に沿って判定する。罠がいっぱいあったんだよ。N は S のサイズではない。N はサイズではない(2回目)。二分探索の中で二分探索を行うことに警戒感があって、最初は対策をしていた。このとき参考にしたものと同じ(「261 ms の提出を読んだ。A 数列の値から添字を得る逆引きインデックスを事前に作成するのがキモであるようだった。A の値の範囲は 10000 以下なので、それが配列のサイズとなったところで大した大きさではない。 言われてみれば、そうだね、という感じ(だけど思いつかなかった)。313 ms の提出も 328 ms の提出も 329 ms の提出も、同じ下拵えをしていた」)。でもなんだかいらない気がして途中で消したんだよね。そして TLE (#51604101)。案の定だよ。対策は知っているのですぐに出し直したけど、TLE に混じっていた WA×8 が手つかずだった (#51606089)。25、26行目が機能していないのが明らかなんだよね。二分探索をやめたから is_j が nil になることはない。終了後2分13秒で通ったんだけど (#51610081)、何に時間がかかっていたかと言えば、サンプル3の答えが1ずれていた。その原因が 26 行目の条件式 if is[is_j]<i%Sz に等号が付いていたこと。時間に追われる中でその微妙な差違に気が付くのは無理でしょう。なまじ解けただけに時間不足が残念でならない。■コンテスト成績証。青パフォでプラスではある。しかしものたりないなあ。このチャンスを逃した今、明日の ARC からまたもう何度目にもなる落ち目が始まる可能性だってあるのに。


2024年03月17日 (日) [AtCoder] 昨日はモノグサプログラミングコンテスト2024(AtCoder Beginner Contest 345)があった。22:40 になったら結果も他の人の提出も見ないですぐに離れてしまったんだけど(面白くないことがあったのです)、なんだかすごいことになっていたみたい。EF がどちらも黄 diff だったんだって。恐ろしい大虐殺があったということだ。コンテスト成績証。「早解き大成功で棚ぼた青パフォの回だった」と書いた前回より解いた問題が1問少なくて、順位とパフォーマンスは逆に少し上なのだから、ぼた餅のありがたみが増量している。まあ、お前はいつまで崖を見上げる立場でいるんだって話ではある。あんまりふりかえって書くことはないかな。D 問題みたいなのは箱入り娘ソルバーとかカレンダーパズルに似ている(2021012120210527)。テキトーに計算量を見積もって最大限に手抜き実装をしたら 25 ms だけオーバーしてペナルティを食らってやんの(#51311820)。条件式をループの外に出して AC (#51314164)。■@2024-03-21 E 問題「Colorful Subsequence」。Ruby でがんばったけどこれが限界。提出 #51483115 (TLE×20 / AC×18)。今のところ TLE しかないよ>Ruby によるすべての提出。制約による暴力はやめてください。■■■[AtCoder] 今日は AtCoder Regular Contest 174 があった。自分のすべての提出。結果はまだ。AB は早かったけど C がさっぱりで、早々に見切りをつけて D に集中するも1時間以上かかった。■A 問題「A Multiply」。累積和の問題。ABC338-G「evall」の部分問題みたいなもので、「範囲の両端が + の内側にある場合の寄与は、これは累積和の問題として単独で D 問題あたりにでもなりそうな難易度の問題」と書いていた部分。ABC-D ではなく ARC-A として出てきた。他所でいろいろ読んで場合分けをしているケースがほとんどみたいだったので、自分のやり方を書く。ある要素 A[i] が範囲に含まれるとき、全体の和をどれだけ増減させるかは C*A[i]-A[i] で計算される。これの部分累積和が最大になる範囲を求める。場合分けはしない。判断をすれば判断ミスをするし、分岐すれば分岐した先それぞれでミスをするので。部分累積和の最大を求める方法だけど、名前が付いているらしかった。「Kadane's Algorithm | 最大部分配列 問題 - Ark's Blog」。名前で特定するより自分でひねりだすほうが簡単では? ダイクストラ法もね、優先順位付き(重み付き) BFS という、実態に即した命名の方が理解を促す面があると思うんだよね、固有名詞で特定するよりもね。■B 問題「Bought Review」。星は増やすことしかできない。星を水増しして総数を増やすことに意味はない。それを確認すると無駄な情報が見えてくる。星3の数はいらない。星123を増やす選択肢もいらない。星1と星2を星4と星5で打ち消すための配分を考える問題。二分探索が頭をよぎって線形性を探したけど、実は星4を2つ増やすコストと星5を1つ増やすコストの大小で即座に優先すべき選択が決定する。ぴったり打ち消すのがいいか、1つ星を余らせた方が効率的にも絶対的にも得かは、条件次第で判断が分かれるところ。最適な式を探るより候補を3つ並べる方が簡単。■D 問題「Digit vs Square Root」。小さい N に対して答えを列挙してみると、答えが見つかる範囲が 10 の冪乗とそこからいくつか下った狭い範囲に偏っていることがわかる。1、10、9、8、100、99、98、1000、999、……といった具合。あとはがんばる。ランダム入力に対して愚直解法と答えを突き合わせて1時間20分かかった。つらい。実装しながら Project Euler の Problem 63 Powerful Digit Counts に似ているなと思っていた(20110308p01.02)。■日記を書いているあいだに結果が出た。コンテスト成績証。ARC にはレートを吸われるばかりなので、微増は勝ち。


2024年03月11日 (月) [Sony Reader] BOOX Max2 も持ってるけど外に持ち出すのは今でも PRS-650 だ。13 年前に買ったもの。バッテリーの持ちが悪くなったとはいえ現在の使用頻度では週一で充電すれば十分。だけどとうとうバッテリーの劣化のしかたが線形ではなくなってしまった。前日にケーブルを繋ぎ直したりして2度まで満充電になったことを確認しているのに、翌日に使おうとしたらバッテリーが空っぽだと表示されてしまう……ことがある。必ずではない。けど3割の確率で読もうとしたときに読めないのでは役に立たない。赤色じゃないし刻印もないので愛着もないけど、中古で確保していた予備機を出すときが来たようだ(半年に1回程度思い出したときにバッテリーの充電だけはしていた)。128 GB と 64 GB のメモリーカード2枚を差して使えるものは他にないよ。HDD を内蔵した iPod が画期的だったのはライブラリをまるまる保存できたことなのであって、何を入れて何を入れないかのやりくりを今になって繰り返すことほどあほらしいことはない。■@2024-04-11 代替機も同じようなバッテリーの減り方を見せたので別の原因を疑っている。最近メモリーカードの読み取り不良がちょいちょいあったので、それによって無限に処理が走ってバッテリーが枯渇しているのではないか。スリープ中にカードを抜くようにしてみる。たぶん差し込んだときに走る処理が負担だけど、知らないうちに空っぽになってるよりはましなので。


2024年03月10日 (日) [AtCoder] 今日は ARC173 があった。1時間かけて A のみの1完だけどかすり傷なのでセーフセーフ。コンテスト成績証自分のすべての提出。では A のふりかえりと C の精進を。■A 問題「Neq Number」。1桁ずつ選べる数字を考えてみると、先頭の桁はゼロを除く1~9の9通り。続く桁はどれも0~9から前の桁と同じものを除いた9通り。ある桁の重みは9の冪乗で簡単に計算できる。桁数を決めて、ある桁について K から重みを引くと同時に数字をインクリメントしていけば簡単に答えが出ると思ったけど、細かい部分がさっぱり合わなくて苦しんだ。かつての ABC-D くらいの難易度と問題傾向だと思うんだよね。なぜすぐ解けない。ところで、問題文が難しかった。「例えば 1,173,9090 は “Neq Number” です。」とあるが、1と1が並んでいるのに Neq Number であるとはどういうことかと、Neq Number の定義を何度も何度も読み直してしまった。この日記を書いている今気がついたことだけど、3桁区切りと4桁区切りが混在している不自然さを読み取らなければいけなかったのですか。■C 問題「Not Median」。どういうときに区間の幅が伸びていくかというと、ある数の左側にある数列が、ある数との比較において高低高低高低高低……と並んでいて、反対側には低高低高低高……と並んでいるときに、どういう区間を選んでもある数が中央値になることが避けられない。問題は、そういう均衡を破る最初の位置を効率良く見つける方法。過程を飛ばして結論を書くと、高高となる位置と低低となる位置を記録する2本の BIT を使った。高低は相対的なので処理順を1から N の順にした。そうすると最初は低低の位置はどこにもなく、すべての位置が高高の並びになる。これをスタートにして BIT を更新しながら答えを計算した。ところで、左右の端にある要素については効率良く数える方法がわからなかった。例えば入力が 4 3 5 6 2 1 7 で、4を中央値にしたくないとしよう。4との相対で数列を書き直すと 4 低 高 高 低 低 高 となる。高高や低低の並びを検索したとしても項数を奇数に揃えた途端に釣り合いがとれて4が中央値になってしまう。4 の左に低もしくは高のどちらでも存在していれば即座に答えが確定できるのだけど。だから両端の要素については線形時間を使って答えを出した。■B 問題「Make Many Triangles」はね、解ける人は 30 分くらいで解くみたいだけど(Ruby では2人)、自分にはさっぱりだった。3点以上が乗る直線を引いてグループを作ったとして、どういう規則でトリオを作っていけばいいのか、そういうやり方で答えが出せるのか、何もわからなかった。複数のグループに属する点の扱いもわからなかった。■■■@2024-03-14 B 問題。E8 さんの解説画像を見ました(それと類人猿の人の)。ダメなケースから考えていけば良かったみたい。たとえば、全てが一直線上に乗っているとき、三角形は1つも作れない。では1つだけ直線から外れていたら? 直線上から2点を選んで1つだけ作れる。以下順々にくりかえし。直線上の点が先になくなったときは、直線上にない点を選べばいいんです(※)。テキトーに3点を選べば大体の場合において三角形は作れるんです。だから作れないケースから考えている。そのためには最も多くの点が乗る直線を1本見つければいい(※)。提出 #51223271 (AC / 272 Byte / 342 ms)。へー、なるほどねー。ネタバレを読んだあとではいくらでも知ったかぶりができますけどね。当日は早々に見切りをつけて C 問題に専念していたわけで、次にこのような問題が出るときも、やっぱり途方に暮れて全く手が出ないと思うな。■※を付けた2つの部分に飛躍がある。自分では超えられない飛躍が。たとえば直線上の点がなくなったとき、他に選べる点が他の1つの直線に乗っている点だけだった場合は? わかりやすく2本の直線に半分ずつの点が乗っているとき、交互に2個と1個、1個と2個で組を作っていけば無駄なく三角形を作っていけることはわかるけど、いつでもこんな風にうまくいくだろうか。1本の直線にだけ注目して答えにたどり着くことが、やっぱりまだできない。


2024年03月09日 (土) [AtCoder] 今日はトヨタ自動車プログラミングコンテスト2024#3(AtCoder Beginner Contest 344)があった。コンテスト成績証自分のすべての提出。早解き大成功で棚ぼた青パフォの回だった。F 問題が壁だったのか。では ABCDE のふりかえり。■A 問題「Spoiler」。split を使う解答と sub/gsub を使う解答が考えられる。Ruby の split はたぶん Perl 由来の仕様なのか、split した結果生じる末尾の空文字列の要素が取り除かれる罠がある。たとえば ",,,,,".split(',') は空になる。論理的な結果が欲しければ第二引数に -1 を渡せばいい。nil を足し算してランタイムエラーを出すのを避けるには .to_s する方法があるけど、自分の好みは文字列埋め込みかな。明示的な型変換はダサいと思ってる。他には文字列と配列の明示的な .dup も書きたくないものの例。なんでだろうね。文法的なキーワード(これも書きたくないもののひとつ)と同じく、形式的で冗長で、必要ではあるかもしれないけどノイズであり、自分が書いているロジックとは無関係だと思ってるからかな。もっとも、アプリケーションドメインとソリューションドメインの対比で考えると、形式的だろうが冗長だろうが足下の物理的側面を無視すべきでない状況があるのかもだけど。■B 問題「Delimiter」。Ruby が入力を改行区切りで与えてくれるので reverse して出力するだけ。■C 問題「A+B+C」。予め全組み合わせを試して作れる和を列挙しておける制約。判定は Hash で。Hash も二分探索も使わないのは横着なのよ。■D 問題「String Bags」。なんの工夫もなく試行して答えを出して許される制約。何回の操作で何文字目まで作れたかの DP。■E 問題「Insert or Erase」。効率的な insert/delete ということで、SortedSet がない Ruby の頼りになる味方 BIT の影がちらつくけども、次の要素/前の要素をポイントするリンクリストを構成すればいい。■F 問題「Earn to Advance」。制約が小さく見えるけど制限時間が4秒。パラメータが多くなりすぎるのをどうすれば良いのか。位置(i,j)、待機した回数、パス上の最大の P、所持金。所持金は必ず P 未満になるはずで、待機した回数が増えるほど所持金も多くないと割に合わないというあたりで候補を整理できそうに思ったが、それでは TLE×20 が TLE×14 になっただけだった。Array#bsearch_index と Array#insert でソート列を維持する仮実装でそれなのでまだ改善の余地はあるのだけど、それで TLE が完全に解消されるのかどうかがわからない。実装をがんばるより頭を使うべきところなのではないか。■■■@2024-03-13 F 問題。ルートを逆順に見ていきながら、待機数と残コストのペアを候補として記録していく DP をした。ゴールまでの残コストがわかっているので、各マスで即座に待機数を決めることができて、パラメータリストから経路上で最大の P というパラメータを消すことができる。提出 #51184903 (WA×9 / TLE×6) のち 提出 #51185273 (AC)。WA の原因は 22 行目と 25 行目にあって、十分に待機してみる候補が不足していた。TLE の原因は 26 行目にあって、配列を比較するソートが遅い。■十分に待機しない候補とは何かという補足。最初に候補として考えていたのは、まったく待機せずにコストを先送りする候補と、ゴールまでのコストを賄うのに1回だけ少なく待機する候補。これは何かというと、(1,1) から最大の P に到達するまでのパスで、待機して得た所持金と負担したコストの差分次第では、最大の P で待機する回数を1回だけ節約することができると思ったから。そういう例外的なケースに注目するあまり、最大の P で十分に待機するという当たり前のケースが抜けていた。■気になるのは、各マスにおける候補の数がどれだけ膨れ上がるかということ。22 行目と 25 行目を見て上か左に1マス移動するごとに3倍になると考えるなら破綻する。実際には待機数が増えたなら残コストは減らなければいけないという選択が働くので、待機数0の候補も残コスト0の候補もそれぞれ1つだけしか残らない。3つの候補のうち2つがそういうものだ。大体は効率的な待機と効率的なパスによって淘汰されると期待しているんだけど、待機数0、待機数1、待機数2、……と、ゾンビのように目のない候補が列をなして処理コストを引き上げる懸念がないではない。最悪の場合はどうなっているだろうか。ゴールまでのパスの数だけ候補があるという最悪のケースがありうるだろうか。その数は 2N から N を選ぶ組み合わせみたいな数になるんだけど。それよりは P や R、D の上限から待機数とコストの種類数が 10^9 に制限されている方が先に天井になるが、それでも解説と同じ O(N^4) にはならない。候補数の上限が N^2 で抑えられて初めてそう言えるが……抑えられるんですか?■さっき「待機数が増えたなら残コストは減らなければいけない」と書いたけど、現在のマスで待機して得られる所持金が p だとして、「待機数が ds 増えるなら残コストは p*ds 以上減らなければいけない」と主張しても良いのではないか。提出 #51204120 (AC / 1666 ms)。マイナーチェンジを無視すると実質的な変更は 26 行目のみ。条件式が2つ増えている。最初の AC が 2167 ms だったから、まあまあ早くなった。個別のケースを見ると4桁 ms かかっていたケースが1つを除いてほぼ 10 倍早い3桁 ms になっている。最後に残った4桁 ms が 1666 ms だということ。けっこう効いたね。そして、自分の解法はハックケースによって撃墜されうるものだったと、詰めの甘さが明らかになったような気がします。テスターさんの想定嘘解法に入っていなかったのでしょう。