math314のブログ

主に競技プログラミング,CTFの結果を載せます

ISUCON8で準優勝した

大体はchibieggが書いてくれているので落ち穂拾いです ISUCON8で準優勝しました « chibiegg日誌

ISUCON8の決勝で準優勝しました、優勝できず非常に悔しかったです。 競技終了直前では50,000点を超えていたものの、再起動後のチェックで31,000点程度と大幅に下げてしまいました。

メンバーと担当は予選と変わらず

  • chibiegg: インフラとコード
  • misodengaku: インフラとコード、エスパー
  • __math: コード

本戦のrepoはこちら、コミットログは例の如く雑です、8時間しか使われないので… github.com

時系列順

10:00

chibieggがansibleを書いている、sshの設定とかをしているようだが問題が公開されたので見る。

マニュアルが結構長い。misodengakuと同時に読み始めて、マニュアルを読み次第goのコードを読み始める。

SNSで拡散という項目をマニュアルでもコードでも見つけるが忘れる。

11:00 まで

とりあえずベンチマークを走らせてもらう、500点前後?

MySQLのslow logとnginxのアクセスログを出してもらう。

/info, /orders へのアクセスが大半の様子。

CPUは200%ガッツリ使っている。

帯域を頑張る問題には見えない。

流石に本戦でオンメモリ戦略をやるのはしんどいだろうということでMySQLは引き続き使うことにする。


DBとアプリケーションサーバを分離してもらう (misodengaku, chibiegg)

そうしている間にあからさまにLIMIT 1が必要なコードを見つけたのでつける。

ベンチを回すとそれだけで 5,000 点出る

12:00 まで

Sequel proをMySQLの本番環境に繋げると落ちて辛い。MySQLのバージョンが新しすぎて安定版では繋がらないのだろうという話になり、Sequel proの最新buildを使ってみると無事繋がる。

/info が支配的であることはわかる。ロウソクチャートを作るためのSQLが重たい事はわかるので、計算の仕方をちゃんと理解し始める。

理解が甘いまま高速化を始めたのでここでどうでもいいpull requestを出し始める

秒、分、時間チャートの情報を出すSQLのGROUP BYをしやすくするために CreatedAt だけではなく CreatedAtSec, CreatedAtMin, CreatedAtHou を追加している。

ちゃんとコードを読むと分かるのだがそこはボトルネックではない。

途中で気づいたものの、害はないのでそのままマージすることにする。

ここでEXPLAINした時にtableがpartitioningされていることに気づくがスルーする。実際はここでスルーすべきではなかった。

isucon.net 講評にかいてあるので詳細はこちらをどうぞ。

13:00 まで

なんか分からないけどGoLand上でisucoinが動かない、listenはしているようだが全てのリクエストにたいして404を返している様子。パソコンが何もわからない…

最終的にはロードバランシングが必要でしょうということでchibieggが準備し始める。

この時点でサーバ01でNginx+App、サーバ02でMySQL、サーバ03と04でApp、という構成に。

ただし、Initializeが全台に対して行われるための仕組みを作っていなかったので、いつでもロードバランスできる状態にはしておきつつ、一旦サーバ01だけで処理するようにしておきました。

ローソクチャート以外に他の人にやってもらえる作業としてisuloggerのbulk requestを挙げた、間違いなく8時間以内に上限に引っかかるので、今やっても後でやっても変わらない。(chibieggにしてもらう) 結果6,000点になった。

14:00 まで

なんか分からないけどGoLand上でisucoinが動かない、listenはしているようだが全てのリクエストにたいして404を返している様子。パソコンが何もわからない…(再)

もう諦めてGoLandはただのエディタとして扱う事を心に決める、結果本番環境以外無くなって構成がスッキリしたと前向きに捉える。

  • 初期化を全ノードに実行できる準備 #11
  • ロードバランスを再度有効化 #12

ベンチマーカーは実行開始前に一度だけ /initialize を実行します。

ロードバランスするとこの初期化リクエストは1つのアプリケーションプロセスにのみ届きます。

その時点で、全てのアプリケーションプロセスを初期化する必要があるため、内部APIを用意し (/internalInitialize) 全てのサーバの初期化を行うように実装しました。

また、設定をsettingテーブルから都度参照するようになっていたのをやめ、グローバル変数に持つように改修することでDBへのアクセスを減らしています。

ちゃんと動作はするようになったものの、数百程度のスコア上昇しかおきませんでした。

大体書いて、何故か手元で動かないので本番でchibiegg達にdebug、bug fixしてもらう。

その間暇なのでuser tableを見ていたら不要なlockがあるので消す。

15:00 まで

みそでんがSNSシェアを有効にするフラグがあると発言。(さすがエスパー担当)

そういえばそんなものがあった気がしてきた、MySQL, Go App ともに負荷が少なくて不思議に思っていたところだった。

あまりにもtrueを返しすぎると、ユーザー増加に耐えられずタイムアウトが増えてしまうので、とりあえず1/8の確率でtrueを返すようにする。

スコアが1万点を超える リクエストが増えたことでボトルネックがわかりやすくなった

16:00 まで

実装が重たそうなので敬遠していたが、どうしても必要に見えたのでローソクチャートのキャッシュに着手した。

雑じゃないロウソク足のキャッシュ by chibiegg · Pull Request #16 · chibiegg/isucon8-final-app · GitHub

特にバグも無く動作したとchibieggは書いているが、コミットログを見ると、きちんとバグっていたので2回bug fixをコミットしていることが分かる。

雑な /info キャッシュ #15 雑じゃないロウソク足のキャッシュ #16

ローソク足は、直近のものは変化するが過去のものは変化しない ローソク足は、秒単位で更新されれば良い という性質もと、私が雑にレスポンス丸ごとメモリにキャッシュする実装、まーす先生が丁寧にロウソク足をメモリにキャッシュする方法をそれぞれ実装しました。

私の雑なキャッシュでも特に問題はなく、一気に25000点弱に。

まーす先生の丁寧なキャッシュもバグ無く動作したため、両方をマージしました。

これがちゃんと動いたので /order の RunTrade に手を入れ始める。とりあえず不要なロジックを消すと 30,000点弱になる。 remove some checks by chibiegg · Pull Request #18 · chibiegg/isucon8-final-app · GitHub

編集がコンフリクトしないであろうUserのアプリケーション側でのキャッシュをchibieggにお願いする。

多少改善したがやはりRunTradeのSQLが重たそうに見える。なんとなくだがRunTradeが走った回数と約定が発生した回数に大きな開きがあるのではと感じ始める。 実際にログを仕込んだところ、精々10%ほどしか実際に約定処理が行われていないことがわかった。

このあたりでGo Appのプロファイリングを行ったところ99%がbcryptの処理であることが分かった(もう少し早めにプロファイリングをするべきかもしれない…?)

bcryptを外すと怒られるのでbcryptのコスト(回数)を10から4に落としたものの大差なし。ISUCON8の講評にはこれが効くと書いてあるが… おそらく/orderか/infoの方がボトルネックだった為効果を実感出来なかった…?

17:00 まで

ユーザーの情報をメモリにキャッシュの実装(chibiegg)が終わって30,000点を超える

RunTradeは /orderのPost requestとは別に行うようにしたところ 37,000点程に上昇する。

17:30 まで

ここまで終わったところ、どうも/orderの高速化は頭打ちで/infoのアクセス回数も多いことからなんとかならないかと頭を捻る。

正直やりたくなかったのだが 最低売却/最高購入価格のキャッシュを入れたところ 50,000点を超える。 1秒キャッシュしてもよかったのか…

18:00 まで

ようやく再起動テストを始める。アプリに問題が発生する要素はないのでMySQLの対策。 MySQLを再起動するたびに35,000~40,000点になるのでMySQLを温めるコードをchibieggが書く。 実際にサーバーの再起動して確かめる時間は無かったのでこれは行わず。しかし実際はサーバー再起動が大きく影響を与えたようで、結果論になるがこちらに力を入れるべきだった。

結果

30,000点程度に落ちて2位、無念。 MySQLを温めるスクリプトが足りていないだけでなく、MySQLの使うファイルがキャッシュに乗っていないのが大打撃となった模様。

感想

勝てなかった。もう少しちゃんとしていれば100,000点は本番中でも超えられたと思うので無念。

POST /signin のBanは実装していなかったがこれも実装すべきだった。

講評より

一方、競技時間中に最大スコアを記録し、惜しくも2位となった「takedashi」は上記で言うところの完全クリアまでたどり着いているようでした。

しかし、再起動試験においてエラーが多発し、1度目はtimeout多発によるfail、2度目はstatus codeが400で返ってくるという事態が発生し減点により結果を伸ばすことができませんでした。(htmlが返ってきていたのでアプリケーションの問題ではなさそうということしか原因はわかりませんでした。)

rebootによる再起動試験をしていたら、もしかしたら競技時間中に気づくことができたかもしれませんが、気づいたとしても対策できるような問題でも無い気がしますので、これもまたISUCONの面白さではないでしょうか?

"気づいたとしても対策できるような問題でも無い気がします" の部分に同意します。 取れる対策としてはもっと点数を上げることでしょうか…? 100,000点を超えていればエラー多発でも完走すれば50,000点は出ていただろうと思います。

またこちらも結果論ですが、userのbcrypt以外はmySQLは不要な問題だったと思うので、ISUCON名物のオンメモリ戦略を取るべきだったかなとも少し思っています。

ISUCON8予選をオンメモリ戦略で通過した

ISUCON8の予選に参加しました。運営の皆様お疲れ様でした、今年はオーソドックスな問題だった気がします。 isucon.net

結果 44,295点で全体8位、予選通過のようです。今年もよろしくお願いします。

メンバー

  • chibiegg: インフラとコード
  • misodengaku: インフラとコード
  • __math: コード
  • aki33524: 3人しか出れないので不参加 最近は太刀魚を釣っているらしい

以下箇条書き

  • Goは速いだろうということでGoを選択。pythonの方が慣れているがCPU勝負になったときに不利…
  • MacbookにGolandを入れていたが、Debuggerが起動せずに苦しんだ。なんか色々インストールする必要があるらしいが時間がないのでDebuggerなしでやることに
  • Goのアプリのプロファイリング用にpprofというものがあるらしい、でも結局使わず
  • misodengakuはリモートで参加。こちらの通話のみ聞こえており、misodengaku側がslackでのみ反応

競技開始

  • パスワードでログインは面倒なので各サーバーにpublic keyを置いてもらう
  • gitリポジトリを用意してもらう。GoのコードとDB初期化のコードはここで管理
  • トイレに行って閉め出される、一回休み
  • リバースプロキシはh2o、nginxじゃないの
    • misodengaku, chibiegg がよしなにしてくれた
  • アプリはGo + MySQLのシンプルなもの。フロントはjsで触るところはなかった。APIと何個かのhtmlを返すエンドポイントをいい感じにする
  • 取りあえずベンチマークを走らせる。
09/16 10:18:47 レスポンスが遅いため負荷レベルを上げられませんでした。/
09/16 10:18:48 レスポンスが遅いため負荷レベルを上げられませんでした。/
09/16 10:18:49 レスポンスが遅いため負荷レベルを上げられませんでした。/
09/16 10:18:50 レスポンスが遅いため負荷レベルを上げられませんでした。/
09/16 10:18:51 レスポンスが遅いため負荷レベルを上げられませんでした。/
09/16 10:18:52 レスポンスが遅いため負荷レベルを上げられませんでした。/
09/16 10:18:53 レスポンスが遅いため負荷レベルを上げられませんでした。/
...
  • "/" が遅いらしい サーバの負荷は
  PID USER      PR  NI    VIRT    RES    SHR S  %CPU %MEM     TIME+ COMMAND
 7525 mysql     20   0 1633596 260344   9480 S  77.7 25.6   1:56.13 mysqld
 7784 isucon    20   0  268432 145580   4720 R  31.3 14.3   0:38.41 torb
  • とりあえずmysqlがネックらしい?コードを読む
  • エンドポイントを洗い出す
  • "/admin/" 以下になんかある?"/"以下と同じくらいの実装量のページ?
  • table多い
  • "/"がすごい量のSQLを吐き出している。localのGo + 本番サーバー上のMySQLで動かすとなんとレスポンスに40s+かかる。明らかにクエリを減らす必要がある
    • ssh -L でトンネルを作って接続していた。全てのdev環境が本番DBを参照する素敵仕様
  • ついでにサーバのスペック確認してもらう
CPU: 2
メモリ : 1GB
  • メモリ少ないっぽい
  • MySQLとGoがCPU/Memoryを食べあうことになりそうなので早めに分離。

アプリケーションサーバを3、DBを1にしました

misodengaku [11:12 AM] slowlog的にはここで全件取ってそうでやばそうぐらいしか見えない e.GET("/admin/api/reports/sales", func(c echo.Context) error { rows, err := db.Query("select r.*, s.rank as sheet_rank, s.num as sheet_num, s.price as sheet_price, e.id as event_id, e.price as event_price from reservations r inner join sheets s on s.id = r.sheet_id inner join events e on e.id = r.event_id order by reserved_at asc for update")

chibiegg [11:14 AM] リクエスト的には GET / GET /api/events/10 GET /admin/ POST /api/events/11/actions/reserve が重い (合計時間的な意味で)

  • MySQLに格納されているデータを見る。
  • INSERT/UPDATEのないテーブルは起動時にメモリに載せればいいよね
  • sheets はもうちょっとなんとかなるでしょ
  • …ていうか全部合わせても100MBいかなくない?
  • 基本全部Go側でデータ持てば良くない?MySQLはデータの永続化にのみ使用して、起動時にデータ全読み込みでいいよね?
  • 2018/09/17 追記 アプリケーションを1つしか起動しなくてもパフォーマンス十分出るよね?
  • ISUCONだからね
  • INSERT/UPDATEのないテーブルは改造するのに難しい点はない。半分がメモリ上のデータ、残り半分がSQL発行してデータ取得しててもベンチマークは通るし通らないとバグっていることがわかる
  • 一方INSERT/UPDATEがある場合は結構複雑、色々考えたけど競技時間が8時間しかないということで以下の方針で行くことにした

reservationテーブルと例に上げると、 1. 起動時にDBから全reservationデータを取り出す

var (
    reservationStore = make([]*Reservation, 0)
    reservationMutex = new(sync.Mutex)
)
// main内と /initializeで呼ばれる
func initReservation() error {
    rows, err := db.Query("SELECT * FROM reservations")
    if err != nil {
        return err
    }
    defer rows.Close()

    reservationStore = make([]*Reservation, 0)

    for rows.Next() {
        var reservation Reservation
        rows.Scan(
            &reservation.ID,
            &reservation.EventID,
            &reservation.SheetID,
            &reservation.UserID,
            &reservation.ReservedAt,
            &reservation.CanceledAt)
        reservationStore = append(reservationStore, &reservation)
    }

    return nil
}
  1. SELECT/INSERT/UPDATEは全てreservationStoreのデータを参照/追加/更新する
  2. INSERT/UPDATEは、アプリ/マシンの再起動に備えてMySQLにもデータを流す。ただしアプリは起動時以外一切データを見ないので非同期でSQLを発行
   // mutexで保護しつつ reservationStoreのデータを追加

    go func() {
        res, err := db.Exec("INSERT INTO reservations (id, event_id, sheet_id, user_id, reserved_at) VALUES (?, ?, ?, ?, ?)",
            reservation.ID, reservation.EventID, reservation.SheetID, reservation.UserID, reservation.ReservedAt.Format("2006-01-02 15:04:05.000000"))
        if err != nil {
            log.Println("error happened on Exec")
            return
        }
                // 追加のエラーハンドリング
         }()
  • メリット
    • 実装途中でも負荷が少なければそれなりに動く。例えばSELECTはメモリ上のreservationStoreを参照、INSERT/UPDATEはSQLを同期的に発行しつつreservationStoreも更新という実装でも一応動く
      • でもtransactionとか消えてるから死ぬときは死ぬ。多分ベンチマークは通らない
      • GoだとSQL発行の同期/非同期の切り替えがとても簡単。非同期にしてバグったら最悪同期に戻すことでベンチマークを通すことが出来る
    • 完成してしまえばMySQL依存は無くなる。場合によってはN+1問題が発生していた箇所は放置しても爆速になっている可能性すらあるので他の改善に時間が使える
  • デメリット
    • 全部実装し終えないとベンチが通らない
    • MySQLにindexを貼ったりcolumnを整理した方が早くなる場合が大半なので慎重に考える
    • goroutine内(非同期)でSQLを発行することに気をつける。UPDATEは気をつけないとおそらく死ぬ
    • NG
   event := eventStore[id]
    // eventの更新

    go func() {
        // NG 実行されるgoroutineの順番によっては最新でないeventを元にしたUPDATEが発行される恐れがある
        if _, err := db.Exec("UPDATE events SET public_fg = ?, closed_fg = ? WHERE id = ?", event.PublicFg, event.ClosedFg, event.ID); err != nil {
            log.Println(err)
        }
    }()
  • SAFE
   // eventStoreの更新

    go func() {
        // OK 実行されるgoroutineの順番によらず、最新の状態を元にUPDATEが発行される
        // どのeventStoreの更新よりの後に実行されるgoroutineは必ず一つ以上あるので、実行中にKillされない限りMySQL内のデータもいずれは最新の状態になる
        event, _ := getEvent(eventID, -1)
        if _, err := db.Exec("UPDATE events SET public_fg = ?, closed_fg = ? WHERE id = ?", event.PublicFg, event.ClosedFg, event.ID); err != nil {
            log.Println(err)
        }
    }()
  • ISUCON以外でやろうとすると怒られる。indexを貼ってもMySQLでパフォーマンスが満足できないなら次はRedisを試すのだろうか?

  • sheetボトルネックではないけど、他の箇所の編集と競合しづらいだろうと考えchibieggに頼む

  • INSERTがあるけど、reservationが減れば嬉しいだろうと考えてなんとかしようとする
  • eventもでかいけど後回し
  • 11:30 くらいからみんなで着手し始めた
  • このあたりでsheet関係のSQLが無くなったのでベンチマークを走らせたら"座席がランダムではありません"と怒られる。ランダムじゃないとだめなのか…
    • Fisher-Yatesのシャッフルを実装したら通った。スコアは変わらず
  • 13:30くらいになってreservation周りの半分くらいSQLを消す。この時点で半分がメモリ上の情報のみを参照して残りがDBの情報を参照する
  • 残りのreservationは私がして、chibieggとmisodengakuにuser周りをなんとかしてもらうことに
  • 多分14時くらい getEventsが爆速になった(local 40s -> 1s未満)のでlocalでのデバッグが捗る
  • 15:00 全部reservation周りのSQLが全部消えたのでテストするけどfailする。多分UPDATEが悪さしてる
  • なんかuserもバグってるらしい。reservationの方が動かないとスコアは上がらないのでchibieggにdebugを頼む
  • INSERT時にMutexで保護する範囲を広げたり色々直す
  • 15:34 30000点を超えて1位になったので喜ぶ f:id:math314:20180917191711p:plain
  • Goがだいぶ分かってきたのでこの調子でeventも剥がすことに。次のボトルネックを探してた気がするけど何だったか忘れてしまった
  • gzipで圧縮してみたら?ってことでやったらスコアが下がる
  • 16:47 eventを剥がし終わったのでもっかいベンチを走らせるも25000点。topで見るとCPUを使い切っている
  • どうせ帯域は余裕があるしgzipを切る
  • 40000点を超える
  • CPUがボトルネックだしh2oも別サーバに移動で良くない?
  • そんなに変わらない
  • そろそろ残り1時間ちょっとだし、予選は突破できそうなのでベンチガチャを開始することに
  • 17:14 最高得点(44295)が出る。何も変えてないのに2万点弱ブレてびっくりする f:id:math314:20180917192755p:plain
  • 目標は予選突破であって1位ではないのでこれで撤収。ホワイトなISUCONだった

感想

  • MySQLからデータを剥がしてスコアが上がるのは面白い、結局今回はindexを使わなかった気がする
    • ちゃんとindexを貼ってもスコアは上がったらしい?こっちの戦略でも良かったかな…
  • プロファイリングが必要な段階まで行けなかったのは心残り
           From(reservationStore).Where(func(c interface{}) bool {
                r := c.(*Reservation)
                if r.EventID != event.ID {
                    return false
                }
                if r.CanceledAt != nil {
                    return false
                }
                return true
            }).ToSlice(&reservations)
SELECT event_id FROM reservations WHERE user_id = ? GROUP BY event_id ORDER BY MAX(IFNULL(canceled_at, reserved_at)) DESC LIMIT 5
  • After
       From(relatedReservations).GroupBy(func(c interface{}) interface{}{
            r := c.(*Reservation)
            return r.EventID
        }, func(c interface{}) interface{} {
            return c
        }).OrderByDescending(func(c interface{}) interface{} {
            values := c.(Group).Group
            maxTime := From(values).Select(func(c2 interface{}) interface{} {
                r := c2.(*Reservation)
                if r.CanceledAt != nil {
                    return r.CanceledAt.UnixNano()
                } else {
                    return r.ReservedAt.UnixNano()
                }
            }).Max().(int64)

            return maxTime
        }).Take(5).Select(func(c interface{}) interface{} {
            eventId := c.(Group).Key
            return eventId
        }).ToSlice(&eventIds)
  • 普段使わないlaptopで苦戦した。IDEのインストールとかは事前にするとよさそう
  • branch名を間違えてreserveのつもりがreverseになっていた。英語…
  • 面白かったです

Størmerの定理

前書き

$2^{n} - 3^{k} = 1$ を満たす正の整数 $(n,k)$ をすべて求めなさい。

いきなりですが、上記の問題が解けるでしょうか?

まず小さい数を代入していくと、$(n,k) = (2,1)$ の時は $2^{2} - 3^{1} = 1$ となってこれを満たすことがわかります。 それ以外の解は見つかるでしょうか? 何となく無さそうですが確証は持てないですね…

こういう問題は 指数型の不定方程式 とか呼ばれているそうです。受験で出てきそうな見た目をしていますが、この問題は凶悪なのか解法は見たことがないです。 この問題、解きたいですよね?

今回は Størmerの定理(Stormerの定理) と呼ばれている定理を用いて、$2^{n} - 3^{k} = 1$ を満たす正の整数  (n,k) は $(n,k) = (2,1)$ のみであることを証明します。

今回の証明は http://kam.mff.cuni.cz/~klazar/stormer.pdf を要約したものとなっています。

続きを読む

Windowsで、実行ファイルを書き換えずに既存の.Netアプリケーションのメソッドを置き換える話

動機

昔、箱庭XSSという問題がSECCONで出題されました。 どのような問題だったかは他の方のブログを見て頂ければ分かるかと思います。

nash.hatenablog.com

問題作者のスライドはこちらです。

【XSS Bonsai】 受賞のご挨拶 by @ymzkei5 【SECCON 2014】 - Dec 08, 2014

このアプリケーションは.Net製で、

  • 難読化
  • 既存のdecompilerでは C#, VB.Netのコードに変換出来ない(大体落ちたり例外が発生する)
  • デバッガでattachすると挙動が変わったり、答えが変わる
  • バイナリを書き換えると、checksum一致処理に引っかかる

という特性があります。

webの問題として解いてほしいらしく、作者さんのスライド曰く

f:id:math314:20170122002615p:plain

とのことなので、チートで解こうと考えました。

今回要求される要件は

  • debugger検知に引っかからない
  • 実行ファイルを書き換えない
    • checksumが変わるため

の二つです。

disassembleしてみると、「正規表現で文字列を置換している処理さえ潰せればフラグを取れるのでは?」と思ったので、「Regex.Replaceの挙動を変更する」ことを目標にしました。

しかし箱庭XSSのみに特化したプログラムを書いても面白くないので、もうちょっと大きく出て「.Netアプリケーションのメソッドを、実行ファイルを書き換えずに挙動を変える」ということにしましょう。

(なおこれ以降箱庭XSSは出てきません、手段と目的は往々にして入れ替わります)

実装

github.com

に置いてあるのでご自由にどうぞ。(英語でコメント書こうとして挫折した後がありますね) とりあえず試してみたい人は https://github.com/math314/DotNetInjection/releases/tag/v1.0 から Release.zip をダウンロードして試してみてください。動かし方はreadmeに書いてあります。

続きを読む

ARC059 : F - バイナリハック / Unhappy Hacking

追記3:

yosupoが最新版の解説を書いたようです。こちらを見ましょう。

yosupo.hatenablog.com

以下は旧記事です。

AtCoder Regular Contest 059 で出題された F - バイナリハック / Unhappy Hacking の O(n)解法です。

解説はコードに埋め込みました。 カタラン数云々は http://www.mtholyoke.edu/~jjlee/Teaching/Intro_to_Catalan.pdf を見て下さい。

atcoderの提出はこちら Submission #839457 - AtCoder Regular Contest 059 | AtCoder

追記:

今回使ったA126087 - OEISにある漸化式ですが、 Conjectureだそうです。一応 n <= 3000まで正しい事は確認しましたが、気になる方がいるようなので追記します。

追記2: magicを使わなくても解けたようです。

Submission #839587 - AtCoder Regular Contest 059 | AtCoder

解説

以下は旧コード

#include <bits/stdc++.h>

using namespace std;
#define FOR(i,n) for(int i = 0; i < (n); i++)
#define sz(c) ((int)c.size())
#define ten(n) ((int)1e##n)
using ll = long long;

const int MOD = ten(9) + 7;
const int N = ten(4);

// O(N)
ll inverse[N];
void init_inverse() {
    inverse[1] = 1;
    for (int i = 2; i < N; i++) inverse[i] = (MOD - MOD / i) * inverse[MOD%i] % MOD;
}

// O(N)
ll fact[N], infact[N];
void init_fast_fact() {
    init_inverse();
    fact[0] = fact[1] = 1;
    for (int i = 2; i < N; i++) fact[i] = fact[i - 1] * i % MOD;
    infact[0] = infact[1] = 1;
    for (int i = 2; i < N; i++) infact[i] = infact[i - 1] * inverse[i] % MOD;
}

// O(1)
ll fast_nCk(int n, int k) {
    if (n < 0 || k < 0) return 0;
    if (k > n) return 0;
    ll ret = fact[n] * infact[k] % MOD * infact[n - k] % MOD;
    return ret;
}

//O(1)
ll pseudo_catalan(int a, int b, int c) {
    if (c == a - 1) b--, c--;
    if (c == b - 1) a--, c--;
    ll ret = fast_nCk(a + b - 2, a - 1) - fast_nCk(a + b - 2, c - 1);
    if (ret < 0) ret += MOD;
    return ret;
}

int solve(int n, int m) {
    // O(n) にできるが、今回は十分に大きい定数回回している
    init_fast_fact();

    // https://oeis.org/A126087
    // magic[i] = i回タイプした時、文字列が空になるようなキーの押し方の個数
    // O(n)
    vector<ll> magic = { 1, 1, 3 };
    for (int i = 3; i <= n; i++) {
        ll tmp = 3 * (i + 1) * magic[i - 1] + 8 * (i - 2) * magic[i - 2] - 24 * (i - 2) * magic[i - 3];
        magic.push_back(tmp % MOD * inverse[i + 1] % MOD);
        if (magic[i] < 0) magic[i] += MOD;
    }

    // 2の累乗
    // O(n)
    vector<ll> power_of_2;
    power_of_2.push_back(1);
    FOR(i, n) power_of_2.push_back(power_of_2.back() * 2 % MOD);

    ll ans = 0;
    FOR(s, n) {
        // ループ内はO(1)
        //
        // |------|X|-------|
        // <------>^<------->
        //    |    |    |
        //    s    | rem - 1
        //         s回目(0-indexed)
        //
        // 前半s回のタイプ後、文字列の長さが0
        // s+1回目、最初の文字を打つ
        // 後半、s+2回目以降は、文字列が空にならないよう注意しながらタイピング
        // こうすると重複せず数え上げられる
        //
        // 前半はmagicに係数が入っているので、後半のs+2回目以降のタイプの仕方について数え上げればよい

        const int rem = n - s; //後 rem 回タイプ出来る
        if (rem < m) continue;
        if ((rem - m) % 2 != 0) continue;

        const int B = (rem - m) / 2; // s+2回目以降のバックスペースの回数
        const int A = rem - B; // s+2回目以降タイプする文字列 (= {0,1}をタイプする回数)

        const ll a1 = B == 0 ? 1 : pseudo_catalan(A , B + 1, B); //カタラン数の計算方法と同じやつ
        // バックスペースで消される文字列は{0,1}のどっちでもいいので、 2^B  を掛ける
        const ll s_ans = a1 * power_of_2[B] % MOD * magic[s] % MOD;
        ans += s_ans;
    }

    return int(ans % MOD);
}

int main() {
    int n; cin >> n;
    string s; cin >> s;
    int m = sz(s);
    int ans = solve(n, m);
    cout << ans << endl;

    return 0;
}

n以下の素数のsumを高速に計算する

目次

  • 動機
  • 問題概要
  • 準備
  • 計算量
    • \(1 \le p_b \le n^{1/4} \) の時
    • \(n^{1/4} \le p_b \le n^{1/2} \) の時
  • 素直なプログラム
  • 最適化したプログラム
  • 余談

動機

Project Euler で、n以下の素数の合計を求める問題がありました。 Problem 10 - Project Euler

この問題は2*106以下の素数の合計を求めるだけなので簡単なのですが、Lucy_Hedgehog さんという方が面白いアルゴリズムをpostしていました。

せっかくなので、なるべく初心者にも分かりやすいようにアルゴリズムの概要を説明したいと思います。 アルゴリズムとか計算量とかどうでもいい人は、

optimized_prime_sum.cpp · GitHub

のプログラムをコピペして使って下さい。

問題概要

競技プログラミングで以下のような問題が出た場合、どう実装すればいいでしょう?

\(n\)以下の素数の合計を出力して下さい。ただし、n <= 106

エラトステネスの篩を使えばn以下の素数の列挙は \( O(n \log\log (n)) \) で出来るので、このアルゴリズムで十分だと思います。

では次の制約の場合はどうでしょうか。

\(n\)以下の素数の合計を出力して下さい。ただし、n <= 1012

答えは 64bitに収まらないので、109 + 7で割った値を答えて下さい。

アトキンの篩を使えば 計算 \( O(n / \log\log(n)) \) , 空間 \( O(n^{1 / 2}) \) で計算出来る(らしい)ので、これで十分かも知れません。 が、今回は計算 \( O(n^{3/4}) \), 空間\( O(n^{1 / 2}) \) で計算出来る方法を紹介したいと思います。

続きを読む