読者です 読者をやめる 読者になる 読者になる

hogecoder

つたじろう(Tsuta_J) 競技プログラミングの記録

CODE THANKS FESTIVAL 2014 B日程 G: 石取りゲーム

久しぶりに解説記事。またまたゲームの問題。

問題概要

原文 → G: 石取りゲーム - code thanks festival 2014 B日程 | AtCoder

 N個の石が積まれた山があり、 2人のプレイヤーが交互に石を何個か取っていき、最後の石を取ったプレイヤーが勝ちとなるゲームを行う。1手で取れる石の個数は、ゲーム開始時に先手が取るときは 1 〜 Pの範囲、それ以降は 1 〜 (前のプレイヤーが取った石の個数)  + 1の範囲である。 N, Pが与えられるので、両者が最善に行動した時の勝者を出力せよ。

解説

まず、solve(i, j)なる関数を考えます。これは、山に i 個石があり、1 〜 j 個の範囲で石が取れる時の勝者を bool 値で返します。

この問題で重要なことは、i と j が決まれば勝者が決まるということです。solve 関数同士の関係をみていきます。

  • 取れる石の個数の最大値が残りの個数以上である場合、全部取れるため必ず勝てる
  • 取れる個数を全て試して、その中でも一つでも false が返ってくれば勝てる
  • 全て試してもヒットしなければ、勝てるパターンが無いため負け

ということが言えます。2つ目の条件でなぜ false なのかというと、ここで参照しているのは前のターンの出来事であり、先攻と後攻の扱いが逆転しているからです。したがってもう少しシンプルに書くと

  • i <= j ならば true
  • i > j のとき、1から j の範囲まで solve を試し、どこか1つでも false ならば true
  • false が1回も返ってこなければ false

と判定できます。もちろん、メモ化が必須です。

ソースコード

int n, p;
int dp[510][510];

// 勝敗判定
bool solve(int rest, int range) {
    // メモ化 (すでに書いてあったらそれを返す)
    int &res = dp[rest][range];
    if(res != -1) return res;

    // range が rest を覆えるならば勝てる
    if(rest <= range) return res = true;

    bool ok = false;
    // 以下は range が rest を覆えない時の話
    // 範囲の中に一つでも false
    // (つまり前のターンで後手必勝) があるなら true
    // 取る石は 1 個以上 range 以下
    repq(i,1,range) {
        // 石は i 個なくなり、範囲は i+1 になる
        if(!solve(rest-i, i+1)) ok = true;
    }
    return res = ok;
}

signed main() {
    cin >> n >> p;
    memset(dp, -1, sizeof(dp));
    bool ok = solve(n, p);
    cout << (ok ? "first" : "second") << endl;
    return 0;
}

前にこのブログで紹介したゲームの問題の中にも、同じ方針で解けそうなものがありますね。ゲームの問題も奥が深いですね。

※追記: 前に紹介した問題たちは制約が大きいのでそもそもメモ化できないですね。同じような問題ですがこの解法は使えないです。難しいなあ・・・

DDCC2016 本戦 参加記

DISCO presents ディスカバリーチャンネル コードコンテスト 2016 本戦に参加しました。どこよりも早く、を目指して参加記書いてみます。

-N日目 (予選)

セキュリティミニキャンプ in 北海道(過去記事参照) の1日目の夜にDDCCの予選があったので、ホテルからコンテストに参加した。

A問題はすぐ解けた。B問題は日本語が難しかったけどAC。Cは制約をくぐりぬける方法が分からず、結局2完・・・。このときボーダーラインを把握していなかったので絶対通ってないだろうなあと思っていた。

あとあと調べて、自分の順位でも本戦の可能性があることを知った。結局、161位で通過してた。うれしい。でも前回のDDPCを見るにこのままだと本戦で玉砕されるので頑張らないとなあという気持ちになった。

0日目 (本戦前日)

本州に住んでいないので前日移動必須。東京到着が遅くなりそうだったので、空港でラーメンとビールを食べてから飛行機へ。なんか天気予報では雪が降るとか言われてて、飛行機飛ぶのかどうかちょっと怖かったけど無事飛んでよかった。22時くらいにはホテルについてまったりしていた。

1日目 (本戦当日!)

23時半くらいに就寝を試みるも寝れず、睡眠が断続的になる。でも当日は5時に起きた。はやすぎ。前回のDDPC解いたりとかあがいていた。

少し早めに会場につくものの電源争奪戦に敗れる。パソコン2台もってきてよかった。Tシャツとシールをもらって「これがオンサイトか・・・」という気持ちになりテンションが上がる。

オープニングビデオがDDCC開会の合図。自分は北海道から来たのに「北は東北からお越しいただき~」みたいなアナウンスが入り笑ってしまった。開会式終わったらへんからめっちゃ緊張してきてやばかった (緊張のあまり手を震わせながらツイートしていた)。あと隣がやたらインタビューされてて大変そうだった。

そしていよいよ本戦スタート!

  • 1問目はEPS考慮したら逆にバグったりしてつらかった(たぶん自分のライブラリに問題がある?)けどAC。
  • 2問目は3つ目のケースがどうもうまくいかず唸ってたら部分点解法出すの忘れていた。結局満点取れなかったしつらさしかない・・・。
  • 3問目は見たけどやってない。4,5問目は見てすらいない。こうして私の初オンサイトコンテストは散ったのだった・・・(オンサイトの洗礼)

幾何っぽい問題と文字列で攻められたら途端に点数が全く取れなくなるのはダメですね。分野によって理解度にムラがありまくるので、もっと精進していきたい・・・。

コンテストが終わって昼食フェーズ(懇親会)に入る。フォロワーに何人か会えてとてもテンションが上がり、オンサイト最高という気持ちが最高潮に達した。他の大学の競技プログラミング事情とか、競プロサークル等に所属せず趣味でやっている人の話とかいろいろ聞けて面白かった。

特別講演で厚切りジェイソン氏のお話を45分間ほど聞いた。米国と日本の会社の体質の違いとか、厚切りジェイソン氏本人の経験などなど貴重な話をたくさん聞けて良かった。リンゴの話が一番なるほどなあとなって、今だけでなく未来も見据えたうえでベストな答えは何なんだろうということを常に頭に入れて動かないとなと考えさせられた。

表彰式後に、懇親会パート2が始まった。ここでもフォロワーの何人かとお話しできてとても良い時間を過ごせた。来年のICPCの話とかもしてて、来年は国内予選抜けてアジア地区でまたいろんな人に会いたいなあ・・・とか思ってた。

総括

今回が初オンサイトだった私は、問題が解けるかどうかももちろん不安だったけど、競プロerの輪の中に入れるかどうかが結構不安だった。でもそれは意外と何とかなってとても楽しい時間を過ごせたし、何より今回で競技プログラミングに対するモチベーションがだいぶ上がったので行けて本当によかったなあと思う。またオンサイトの機会があればぜひ行きたいし、行けるようにもっと頑張りたい。

こんなとこかな。次のオンサイトはいつだろう・・・。

競プロをやりはじめてから半年が経ちました

競技プログラミングを初めて、今日でちょうど半年です。(私が初めて使用したオンラインジャッジであるAtCoderの初AC日を、競プロ初日としています)

競技プログラミングはじめたいけど、なにからやればいいのかな・・・」とか、「この大会の準備期間短いけど今から頑張ったら間に合うかな・・・」とか、その辺の疑問にお答えできたらいいなあと思い記事を書くことにしました!特に初心者のかたは参考にしてください(プロはこわいから見なくてもいいですよ ><)

競プロ初心者がやるべきこと

入出力やSTL・簡単なアルゴリズムを勉強する

まず、プログラムが書ける状態までもっていかないと何も始まりません。まずは、図書館等で基本的なプログラミングの知識をつけましょう。標準入出力、for、while、if等使えるようになれば十分です。ポインタとかクラスとかは競技プログラミングではそんなに意識しなくてよいです(でもライブラリ作るときに必要になるかもしれないので勉強するに越したことはないです)

自分はそのへんどうだったかというと、競プロ始める前はCしか知らなかったためC++の記法を勉強するときはちょっと大変でした。とはいえ、毎日のようにプログラム書いてたらそのうち覚えるので頑張りましょう。ネットで検索したら初心者向けのスライドが転がってるので、そういうのも参考になりますよ。

アルゴリズムに関しては「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」(通称: TLE本)や「プログラミングコンテストチャレンジブック」(通称: 蟻本)が非常に参考になります。最初に読むならTLE本ですかね、蟻本は初級編からけっこう難しいので・・・。TLE本がわかってきたら蟻本を読む、という流れが良いと思います。

オンラインジャッジで修行

初めのうちはコンテストに出るよりも、出題形式や提出方法に慣れるために、またアルゴリズムを学ぶために、問題を解きまくるのが良いです。例えばAtCoderの場合なら、AtCoder Beginner ContestのA・B問題が簡単なのでまずはそこから埋めていきましょう。で、だんだん慣れてきたらCとかDとかに挑戦して・・・という感じですかね。自分のレベルに応じて問題を選んでいってくださいね。

出題形式はコンテスト出る前に把握したほうが良いです。特にTopCoderがちょっと特殊で、main関数に処理を書くのではなくクラスのメンバ関数に処理を書くことになります。一度やっておかないとコンパイルエラー頻発でコンテスト中悲しい思いをするので、事前にやっておくことをおすすめします。

コンテストに参加する

ある程度経験を積んだらコンテストに参加してみましょう。私はコンテスト出たいマンなのでやたら参加してますが(5/19に初めて5/28にはもうコンテスト出てました。せっかちすぎる)、自分のペースで参加しましょう。というのも、コンテスト終了後に復習しないと出た意味がほとんどなくなるので、復習が可能なレベルで出る必要があります。

コンテストはTopCoderCodeforcesAtCoder等で行われています。AtCoderは日本語で行ってくれますが、ほかは英語ですね。最近Google翻訳が強くなったらしいので、英語に抵抗のある方も是非参加してみては・・・?

ライブラリを作る

上位を狙うなら必須です。上位行ったことない私が言うのもなんですが・・・。

ライブラリとは、「このアルゴリズム使いたいぞ!」となったときにすぐに使えるように、予め用意しておくものです。グラフ理論とか幾何でよく使いますね。

で、これを作ることによって解答速度が速くなって良いのは当たり前なんですが、それ以上に「そのアルゴリズムを自分の中で咀嚼できる」のが大きいと自分は思っています。意味を理解しつつライブラリを作っていくと、自分の中で考えが整理できてとても良いので、ちゃんと理解するという意味でもライブラリ作ったほうが良いです。

自分の話

いろいろ書きましたが、実際お前はどんな感じでやってきたねん、ということで振り返ってみます。

大学の競技プログラミングサークルに初めて見学に行った(5/19)。この日から競プロはじめました。AtCoderの問題を使ってバーチャルコンテストをしていたので、AtCoderはじめました。当時Cしか書けず文字列の問題で詰みまくっていたのでC++を勉強するとぞと心に誓う。その時はICPC出ないでおこうかなと思ってたけどなんだかんだで出ることにした。

ICPC国内予選に参加した(6/24)。競プロ歴まだ1ヶ月くらい。自分のチームは、他のメンバーも同じくらいの経験値だったけど3完した。正直これは運が良すぎただけ。だってまだC++に慣れてなさすぎて、setにある要素が入っているかどうかってなんの関数使えば分かるっけ?みたいなレベルだったので・・・。グラフや幾何、DPは全く歯が立たなかったので、これから頑張っていこうと思った。

ICPC後はTopCoderとかCodeforcesとか、やたらいろんなものに手を出した。Twitterのフォロワーが頑張ってるのを見ると触発されて自分も出ちゃうんだよねー。Twitterにいるプロがモチベーションの源でした。

夏休みからライブラリを整備し始めた。AOJにはverify時に大変お世話になりました。特に幾何のライブラリが潤って、ライブラリ使うだけ問題は対処できるようになった。しかし経験が足りない。

あとは、夏休み中に蟻本の初級中級はだいたい読んだ。でもまだフローがわからない、むずい。上級は未だに読めてないなあ、あかん。

9月10月、こどふぇすワンチャンあるかなと思って予選参加するも通らず。まあ、当たり前ですね。来年に向けて1年間精進するぞと思った。

11月、全く狙ってなかったけど DISCO presents ディスカバリーチャンネル コードコンテスト 2016 予選突破してしまった。正直行ってB3補正のおかげで通ったようなもんだけど、オンサイトのコンテストに行けるというのはやっぱり嬉しいですね。本戦が楽しみです・・・。

本戦とかがかかったコンテストで勝つには、最低でも半年は必要な気がしますね。相当センスある人だったらもう少し短くても行けるかもしれないけど、経験が物を言うところがやっぱり大きいですからね・・・。

というわけで、ざっくり言うとこんな感じで取り組んでました。もっといろんなコンテストで結果出せるようになりたいですね。

目標とか

さて、競プロ歴1年を迎える前に達成しておきたいことをまとめておきますかねー。

  • レートあげたい

AtCoderCodeforcesTopCoder全部そうなんだけど、青色になりたい。もう少しがんばれば到達しそうな雰囲気はあるから、このまま頑張っていきたい。

  • ライブラリ充実させたい

ジャンルによってライブラリの充実度が違いすぎるので、どの分野も充実させたい。あとライブラリのバグ発見したい。

  • 蟻本読み進めたい

もう難しいところしか残ってないし、なかなか読み進めるのが大変だけど、なんとか乗り越えたい。

こんなところですかね。次の半年間も実りあるものにしたいですね。精進します。

セキュリティ・ミニキャンプ in 北海道 2016 参加記

セキュリティ・ミニキャンプ in 北海道に参加しました。セキュリティ関係の勉強会は初めて行ったのでついていけるか不安でしたが、グループ議論や演習が充実していて私でも楽しめました。今後セキュリティ・ミニキャンプへの参加を考えている方の参考になればと思い記事を書くことにしました。とはいいつつもめっちゃ真面目に書くつもりはないのでフランクに書いてます。

0日目

このイベントの存在を知ったのは大学の講義中に教授が紹介してくれたのがきっかけ。セキュリティのセの字も知らない状態の私、せっかく近くでこういうのがあるなら行ってみようかなーということで、参加することにした。

その後セキュリティの講義で共通鍵とか公開鍵とか基礎的なことはやるものの、依然としてついていけるかどうか不安のまま・・・。(今思えば心配することなかった)

1日目

実はミニキャンプ当日の6時までラウワンオールしてて、そのあと5時間くらい寝て行きました()
人間がんばれば何とかなるものです。まあ、そんなことはさておき・・・

最初はセキュリティ・キャンプ全国大会の紹介。聞けば聞くほど魅力的な大会だなあと思った。もうちょっと知識つけて出たいなあ、予選は知識なくても通るチャンスはあるといえども、ちゃんと勉強したほうがより大会楽しめそう。セキュリティの資格取りに行くつもりで頑張ったら達成できるかなあ、とかいろいろ考えてた。

次は地域IoTの話。予算がない中でやりくりしなきゃいけないから大変らしい。安全な実装とか、メンテナンスとかどうすればいいかについてグループ議論したけど、取り上げている話題がそれなりに解決困難なのでいい答えは出ず。もっと頭良くなりたいと思った。

その次は演習。HTTP Request / Responseをいろいろいじくって、ムリゲー仕様の携帯ゲームを、脆弱性を突いてクリアしてしまおうというもの。いろいろ見てたら、敵からの攻撃を表すRequestを破棄すればダメージを受けないことが判明してクリア、自分がいたグループが一番早くできたので嬉しかった。でもこれは想定解ではなかったようで、講師側も悔しがっていた。というか想定解思いつかなかった・・・。やっぱり演習形式は、このアプリケーションの何がダメなのかとかが具体的にわかるから好き。

ここで夕食休憩。私からしたらいつもの学食だけど、やっぱり他の大学や高専の人にとっては新鮮なようで、学校の立地について話が弾んでいた 笑

最後は情報学に関する法律の話。自動運転に関する問題が出されて、それぞれの意見を言っていくんだけど、けっこう意見割れてた。どっちの意見もなるほどという感じで、考えされられた。

札幌市民だけど「ホテルが用意されているので泊まっていって!」、ということで、ありがたく宿を利用することに。その後DDPCに出るも2完で無事死亡。上に有資格者何人いるかしらんけどたぶん通らんだろうな・・・。(追記: 通った。ビックリ。本戦終わったらまた記事書きます)

2日目

ホテルで朝食を食べて会場へ。雪めっちゃ降っててつらかった。

朝はクラウドの講義。AWSちょっといじったことはあるけど詳しいことは何もわからないので新しい知識をたくさん得た。個人レベルでどうつかうかとかしか考えたことがなかったので、いちサービスとして提供する側に立った時に何を気をつけなければならないかについてはもう少し日頃から考えていかないとなあと思った。あとでメモ見返したい。

その後はRaspberry piを使った演習。高専生が強いのでサクサク進んだ(ありがとうございます)
あの小さい中にOSが入ってるなんてすごい。前に実験でArduinoを触ったことはあるけど、あれはOS入ってないのでなおさらびっくりした(まあ、ArduinoはOSが載ってない分ハードウェアをフルに使えるのがいいところなんだけどね)
頑張ったらいろいろできそうだし、もうちょい調べてみようかなあ・・・。

これで日程は無事終了。早かったなぁ。

まとめと雑感と

初めて参加したけどすごく楽しめました。来年も参加したいなあという気持ちになってる。

Markdown周りを整えていたおかげでメモがとてもとりやすかった。勉強会でるなら環境つくっておいたほうがいいかも。

あと、高専生つよい。大学よりもはるかにレベルが高そう(主観)なので、あぐらかいてられんなあと思った。

色々と刺激もらったので、これからに活かしていきたいなと思います!!内容のない記事でしたけど最後まで読んでくれてありがとうございました。

Sublime text + Pandoc で Markdown を PDF, Word 形式等に出力 (Linux)

競技プログラミング関係ないです。MarkdownをじゃんじゃんPDF化してSublimeを使い倒しましょう。Linux向けの記事があまり無いように感じたので書いてみました。

※筆者の環境はUbuntu MATE 14.04 LTSです。環境によって設定が微妙に異なる場合があります。

MarkdownをHighlight + プレビュー(数式もOK!)

Sublimeを愛用している私は、ふと「SublimeMarkdownを快適に編集できたらうれしいなあ・・・」と思いました。

調べたら、ありました。 ↓

Sublime Text で Markdown を快適にする3つのパッケージ - 情報系大学院生のWebメモ

この記事を参考にすると、Markdownが色付けされてなおかつブラウザでリアルタイムプレビューもできちゃいます。素晴らしいですね。

でも物足りない私は、「数式も反映されないかなあ・・・」と思いました。

調べたら、できました。↓

$\LaTeX$ Support in OmniMarkupPreviewer | Timon Wong's Blog

OmniMarkupHighlighterのUser-Settings部に、

{
    "mathjax_enabled": true
}

を書くだけ。おいおい、神かよ。これでMarkdown編集し放題じゃない。これは素晴らしい。ということで、一時は満足しました。

Markdown を 他の形式で出力する

ここからが本題です。まだまだ物足りない私は、「これPDFにできないかなあ・・・」と思いました。調べてもなかなか出てきません。なんとか頑張ったらできたので、書いてみます。

Pandoc のインストール

Pandocをインストールしますが、2種類あります。

まずは、sudo apt-get install pandocでインストールするPandoc。Sublime上だけに限らずコマンドラインでも使えますね、いろいろできますよ。詳しい使い方はググってね。

そして、SublimeのパッケージであるPandocもインストールします。こちらは、Package Controlをインストールした状態(インストールがまだならすればいいじゃない!)のSublime上で"Ctrl + Shift + p" → "Package Control: install package"と入力 → "Pandoc"と入力 → クリック でインストールできます。ほかのパッケージのインストールの方法と全く同じです。

インストールが終わったら、次はSublimeのパッケージ側のPandocの設定変更です。Preferences → Package Settings → Pandoc → Settings - Defaultと進み、中身をSettings - Userにコピペしてください。そして、14行目の"pandoc-path"のところを次のように変更します。

"pandoc-path": "/usr/bin/pandoc"

これでPandocのpathが指定出来ました。環境によってパスは違うかもしれないので、その場合はwhich pandocとかwhereis pandocとか叩いてみてください。

さらに、62行目からの"PDF"の"pandoc-arguments"を次のようにします。この設定をすることで、日本語に対応できます。(lualatexが入っていなければ、インストールしてください)

"pandoc-arguments": [
    "-t", "pdf",
    "--latex-engine=lualatex",
    "-V", "documentclass=ltjarticle"
]

PDF出力でエラーが出たら・・・

さて、ここまできたらSublimeで適当なMarkdownファイルを開き、もう一度"Ctrl + Shift + p"でウインドウを開き、そこに"Pandoc"と入力してみましょう。Enterを押すと、出力するファイル形式を尋ねられます。PDFとかWordとか選べて便利ですね。

で、Wordとかは問題なくできるはずです。が、PDFがダメなときがあります。こんな感じでエラー出たら、次の対処をしてください。

Error when running:
/usr/bin/pandoc -f markdown -o /tmp/tmpqof5of.pdf
pandoc:Error producing PDF from TeX source.
! Font T1/cmr/m/n/10=ecrm1000 at 10.0pt not loadable:
Metric (TFM) file not found.
<to be read again> relax
l.100 \fontencoding\encodingdefault\selectfont

細かいことはさておき、どうやらフォントが無いようですね。ということで、以下のコマンドを実行します。

sudo apt-get install texlive-fonts-recommended

フォントインストールするとこのエラーは出なくなります。

環境によってはまだエラーが出ます。

! Package fontenc Error: Encoding file `eu2enc.def' not found.

こんなことを言われたら、sudo apt-get install xetexを叩きましょう。euencはxetexパッケージに含まれているらしいです。これらの設定を踏めば、PDFエクスポートできるはずです!!

簡単にメモったりしたものがTeXの形でPDFで出力できるとは胸熱ですね。有効活用していきたいです。

何か不明な点があればコメントお願いします。では。

AtCoder Regular Contest 009 C: 高橋君、24歳

問題概要

原文 → C: 高橋君、24歳 - AtCoder Regular Contest 009 | AtCoder

長さ Nの順列 aを並び替えたとき、 a_i \neq i (1-indexed)となる要素が k個になる組み合わせは何通りか。1,777,777,777 (素数) で割った余りを出力せよ。

解説

まず、 a_i = iとなる要素をどこにするかを決めます。これは n個の中から (n-k)個を選ぶ組み合わせであるため、 {}_{n} C_{n-k} = {}_{n} C_{k}と同値です。1,777,777,777を法として計算するため、この計算をするためには逆元の知識が必要ですが、それは他のサイトに委ねます。階乗の計算すると思うけど再帰で書いたらダメですよ、もれなくスタックオーバーフローします。

問題なのは、 a_i \neq iとなるような長さkの順列が何通り作れるかを求めることです。漸化式を求めれば解けそうな雰囲気はしますが、どんな漸化式になるでしょうか。

最初に、長さ n = 1, 2の場合を考えましょう。

長さ1で元と異なる位置に置く組み合わせは当然存在しないので、0通りです。

長さ2では、[1, 2]に対して[2, 1]と変えることで条件を満たせます。これ以外には存在しないため、1通りです。

それでは、長さ n \ \ (n \geqq 3)ではどうなるでしょうか。これは n番目の要素で iを選択したとき、 i番目の要素で nを選択するかどうかで場合分けをすれば求まります。文章で言ってもわかりづらいので、図で(パソコンで書くのめんどくさいので手書き)示します。なお、長さ nの順列でこれを満たす組み合わせの総数を c_nと置いています。

f:id:tsutaj:20161102011904j:plain

ちなみにこのような順列は「完全順列」と呼ばれ、完全順列の総数をモンモール数と呼びます。フランスの数学者、ピエール・モンモールにちなんで名づけられた、らしい。

ソースコード

int const MOD = 1777777777;

ll fact_mod(ll n, ll mod) {
    ll f = 1; repq(i,2,n) f = f * (i % MOD) % MOD;
    return f;
}

// 繰り返し二乗法 (再帰バージョン)
ll mod_pow(ll x, ll n, ll mod) {
    if(n == 0) return 1;
    ll res = mod_pow((x * x) % mod, n / 2 , mod);
    if(n & 1) res = (res * x) % mod;
    return res;
}

// 組み合わせ nCr を求める (modあり)
ll combination_mod(ll n, ll r, ll mod) {
    if(r > n-r) r = n-r;
    if(r == 0) return 1;
    ll a = 1;
    rep(i, 0, r) a = a * ((n-i) % mod) % mod;
    ll b = mod_pow(fact_mod(r, mod), mod-2, mod);
    return (a % mod) * (b % mod) % mod;
}

signed main() {
    int n, k; cin >> n >> k;
    int ans = combination_mod(n, k, MOD);
    int dp[555555]; dp[1] = 0, dp[2] = 1;
    repq(i,3,k) dp[i] = (i-1) * (dp[i-1] + dp[i-2] % MOD) % MOD;
    ans = (ans * dp[k]) % MOD;
    cout << ans << endl;
    return 0;
}

数学に強くなりたいね・・・

Codeforces Round #378 C: Epidemic in Monstropolis

問題概要

原文 → Problem - 733C - Codeforces

サイズ nの配列 aと、サイズ kの配列 bが与えられる。配列 aに対して、隣り合う要素が自分より小さい場合、自分にその要素の値を加算し、その要素を削除する操作(つまりマージ)が可能である。この操作を繰り返して配列 aを配列 bと一致させることは可能か。もし可能な場合、操作の過程(何番目の要素を左or右とマージさせたか)も出力すること。

解説

この問題はコーナーケースが多く、気をつけないとWAやTLE祭りになってしまいますね。私もwhileループ抜けずにTLE問題に直面しました。

まず、 \sum_{i=1}^{n} a_{i} = \sum_{i=1}^{k} b_{i}を満たしていなければ、明らかに達成できません。この判定は最初にすべきでしょう。

これを満たしている場合、配列 aを適当な k個の区間に分けることを考えます。具体的に言うと、 i個目の区間の要素の総和が b_iと等しくなるように分けます。(このような分け方が存在しなければ達成不可能です)

区間内でどことどこをマージするかですが、区間内で値が最大の要素で隣とマージ可能な要素を選んでマージするのが最適で、なぜならそうすることでその要素が常に区間内max(しかも単独トップ)を保ち続けるからです。そのような要素がなければ残念ながら達成不可能なため、 \verb$"NO"$を出力する必要があります。ちなみに、区間内の要素が1になるまでマージし続けてから次の区間に行ったほうが簡潔に書けます。

達成不可能な条件が多いのでまとめると、

  • 配列 aの総和と配列 bの総和が異なるとき
  • 配列 aを適当な区間に分け、 i個目の区間総和を b_iと等しくする方法がないとき
  • 区間内最大の要素で、隣とマージ可能な要素がないとき

となります。1つでも当てはまれば達成不可能です。

ソースコード

signed main() {
    int sum_a = 0, sum_b = 0;
    int n, k; cin >> n; vector<int> a(n);
    rep(i,0,n) {cin >> a[i]; sum_a += a[i];}
    cin >> k; vector<int> b(k);
    rep(i,0,k) {cin >> b[i]; sum_b += b[i];}
    if(sum_a != sum_b) {
        cout << "NO" << endl;
        return 0;
    }

    vector< pair<int, char> > ans;
    int x = 0;
    rep(i,0,k) {
        int temp = 0;
        vector<int> v;
        while(x != n && temp < b[i]) {
            v.pb(a[x]);
            temp += a[x++];
        }
        if(temp != b[i]) {
            cout << "NO" << endl;
            return 0;
        }

        while(v.size() != 1) {
            bool ok = false;
            int ma = *max_element(v.begin(), v.end());
            rep(j,0,v.size()) {
                if(v[j] == ma) {
                    if(j != 0 && v[j-1] < v[j]) {
                        v[j-1] += v[j];
                        ans.pb(make_pair(j+i, 'L'));
                        v.erase(v.begin() + j);
                        ok = true; break;
                    }
                    else if(j != v.size()-1 && v[j+1] < v[j]) {
                        v[j+1] += v[j];
                        ans.pb(make_pair(j+i, 'R'));
                        v.erase(v.begin() + j);
                        ok = true; break;
                    }
                }
            }
            if(!ok) {
                cout << "NO" << endl;
                return 0;
            }
        }
    }
    cout << "YES" << endl;
    rep(i,0,ans.size())
        printf("%lld %c\n", ans[i].fr+1, ans[i].sc);
    return 0;
}

ちなみにこれはコンテスト終了後に書きなおしたもので、終了直後にACしたものはもっと汚いです(下のリンク参照、こりゃあ間違い誘発するわって感じ・・・)

バグを誘発させる事のないように書くことって大事ですね。

Submission #21956334 - Codeforces