やねうらお(競プロ用)

競技プログラミングはじめました。Kaggleもやるよ。
伝説の(これから伝説になる)ショートコーダー。

いいね＝RT＝賛同

本垢 : 将棋AI垢 :

[やねうらお(競プロ用) @yanecoder]

私が将棋AIのためにDual Xeon機8台で教師生成してた時は月の電気代が10万円超えてて「わりとかかるんですよー」と知人（添付写真の人）に話したら、「うちは一ヶ月300万円ですけど？」とか言われ、10万円ぽっちで騒いで正直すまんかったと思ったものだが、電気代が月10万円ってわりと高いほうだよね？

[やねうら王 @yaneuraou]

thunderさんが探索アルゴリズムの入門書を執筆されたそうでご恵贈いただいたから、レビュー記事書きました。

https://t.co/zt35aBzITX

[やねうらお(競プロ用) @yanecoder]

AtCoderのABCの終了直後、ツイッターのTLには「レート上がった」とか「入茶しました！」などという喜びの声で溢れてて、全員が100万円の特別給付金もらえたぐらいの騒ぎになってるのを見てるとほっこりする。😊

[佐藤裕也 @satoyuyapyaa]

TLでセグメント木26本生やすっていうのを見たんだけどABCの後半問題ってそんな能力バトル漫画みたいなことになるの？

[やねうらお(競プロ用) @yanecoder]

ABC285
A:a*2==bと書いて1WA(正しくはa==b//2)
B:Sk≠Sk+iをSk≠Sk+j(0<=j<=i)と読み違えて1WA
C:A=0,B=1,..とみなして26進数→10進数変換してしまい1WA
D:str型用のUnionFind自作してたので5分でAC
E:見たことないタイプのdpっぽいのでパス
F:公式解説の1つ目の条件で必要十分だと思っていた。
4完🤮

[やねうら王 @yaneuraou]

いた単語を選別してまた1万枚生成して(「単語選別～1万枚生成」を1世代とする。人力遺伝的アルゴリズムである)、20世代ほど繰り返したところ、ついに可愛いしか生成されなくなった。100%みーんな可愛い。😍

// 添付画像のように同じpromptで4枚ずつ生成している。

つづく

[やねうら王 @yaneuraou]

お正月から画像生成AIで遊んでるんだけど、prompt書いて狙った画像を生成するのはわりと難しい。

私はそれは早々に諦め、ともかくひたすら“可愛い”を生成しようと思い、よさげな単語(表情の描写や状況の描写など)をランダムに散りばめて1万枚生成して、そのなかでいい感じで生成された画像に含まれて

[やねうらお @yaneuraoh]

こんな世界でお金を儲けようと思うと、IQ 150がIQ 80のためのコンテンツをせっせこ制作し続けなくてはならない。

以前は、IQ 110ぐらいの人がIQ 90から110ぐらいの人向けに制作してそれでうまく回っていたようなブログも、もういまや検索にも引っかからない。

[やねうらお @yaneuraoh]

それに対して、インターネットユーザーの平均IQは年々下がり続けている。これは、スマホを子供でも持つようになり、インターネットで可処分時間を多く持ち合わせている層が一気に低年齢化したことが原因である。

いまやインターネットのマジョリティはIQ 80ぐらいしかない。

つづく

[やねうらお @yaneuraoh]

レコメンド機能が十分に発達した現在のインターネットでは、IQ150ぐらいの高い知性を持った人の発言ばかりがTLに流れてくる。

IQ100の人のツイートなんてそもそも他の人のTLに表示すらされない。YouTubeの関連動画でお勧めに出てくるのも、IQ150ぐらいの人達が作ってる動画ばかりだ。

つづく

[やねうらお(競プロ用) @yanecoder]

AtCoderのレート分布からすると、ツイッターのTLは灰色と茶色で溢れてて、「ロリハ？俺はショタ派っすわ。ロリ派とは相容れないかな」とか言うレベルの人らで溢れててもおかしくない(?)と思うんだけど、実際はTLには暖色系の人らのツイートばかり流れてくるの、なんなん？発信力の差なん？ほんま？

[やねうらお(競プロ用) @yanecoder]

@maspy_stars あー、なるほど…。modの値を変えることばかり考えてましたが、base変える方が簡単でした。教えていただき、ありがとうございます!!

[やねうらお(競プロ用) @yanecoder]

Rolling Hashのようなhash値に全幅の信頼を寄せる手法(hash値が一致した時に本当に一致するかは確かめないものとする)、偶然一致する確率が天文学的に低かろうと嘘解法ではあるので、自作ライブラリを公開して、そこで使ってるmod値だとWAになるテストケースをジャッジに仕込まれたら困ってしまうな😅

[maspy @maspy_stars]

@yanecoder AtCoder のみ（事前に定まったテストケース群を AC する）なら base を定数にする攻略も可能だと思います。

一部の海外コンテスト等では、他人の提出が不正解となるテストケースを見つけて攻撃する（hack）をプレイヤ同士で行うルールが採用されていて、敵対的入力への安全性という問題が出てきます。

[maspy @maspy_stars]

@yanecoder Rolling Hash は、mod, base というパラメータに依存しており、mod が定数であっても base が実行ごと乱択すれば、どのような敵対的な入力に対しても十分な確率で期待通りの結果になることが証明できます。
ので、mod を定数として base を乱択する実装が上位層では一般的だと思います。

[やねうらお(競プロ用) @yanecoder]

これ実装してて、Rolling Hashは、これで計算した２つのhashを結合するconcatみたいなメソッドがあると少し便利だと思った。(添付図のコード)

おわり。

[やねうらお(競プロ用) @yanecoder]

■　Rolling Hashでsuffix array求めるやつ

普通はどうやってsuffix array求めるのか私は知らないんだけど、Rolling Hash使うと簡単に(?)求まるようだった。

つづく

[やねうらお(競プロ用) @yanecoder]

また、この解法がそのまま使える問題がARC50Dにあった。(この問題の解説ではRolling Hash使っていないようだが。)

Rolling Hashを使って提出したら確かにACになった。

https://t.co/GdsTxd4LiP

[やねうらお(競プロ用) @yanecoder]

昨日のABCで危うく茶色に戻るところだった。いっそ茶色まで戻して再度入緑することで、けんちょんさんから２回目の「よっしゃ！おめでとうございます！」がもらえるのか試してみたいぐらいだった。

次回、「けんちょんさんは、すでにおめでとうございますしたかフラグを持っているのか」お楽しみに！