競プロっておいしいの?(仮)

ABC310-Dのフレンズさん解説で被らないってマジ?と思ったお仲間へ

これ被りません

どーも、Nafmoです。

ところで皆様はこの解説を見たときにこんなことを思いませんでしたか?

「これで被らず数え上げられるってマジ?」

そう、僕も思ってました。が、よくよく考えると、全然被らないのでそのお話を…………

 

と思ってました。が、僕が理解したなんとなくしかかけなかったのでチラシの裏です。参考程度にどうぞ………。厳密にはかけません。

 

被らないのってなぜなん?

小さい順に入れてるから、以上。

それじゃ元も子もないですよね。

 

組み合わせの話

(1,2,3),(1,3,2),(2,1,3)を同じと見ます!みたいなやつ

これなら全部ソートすれば(1,2,3)で1種類ですよね。

これと同じことをします。

では本題

今回はN個ある要素を部分集合 A,B,Cの3つに分けたとしましょう。共通部分はなく、AとBとCを合わせたものは分ける前と同じとします。

さっきの話で、A,B,Cそれぞれ、その構成要素をソートしておきます((2,1,3)を(1,2,3)にのように)

次に、A,B,Cの先頭の要素を見てソートします(それぞれ違うはずなのでA,B,Cを並び替えることができます)

これをすると、小さい数字から順番に属する集合を決めるとき、すでにある集合に加えるか、新たな集合を作るかの2択になると思います。そして、これはソートされた状態を保ったまま要素を追加できます。

ソートされた状態のものだけを数えておけば、重複は避けられそうですね〜という感じで何となく理解しました。

 

お願い

お気持ちしかかけませんでした…殴らないで………

もっと良い説明があったら教えてね

ありがとうございました。

ABC310 B - Strictly Superior 簡易解説

ABC310 - B の簡易解説

公式解説があまりにむずかしく見えたのでC++の実装方針と解説をおいておきます。

もし役立ったらTwitterでリンク共有するなりしてね、僕が喜ぶよ

問題概要

ざっくりいうと、ある商品Aに着目したときに、

  • Aの機能を全部持っていて、値段が安い商品
  • Aの機能を全部持っていて、Aと同じ値段なのに、Aにない機能を持っている商品

のどっちかの条件を満たす商品Bはありますか?という問題です。

つまり、(Aの値段)≧(Bの値段)であってほしいということですね。

値段が等しいときは機能を一つでも多くほしくて、安ければ機能は同じものが欠けなくすべてあればOKという感じですね!

方針説明

基本方針

今回は  N が 最大100 なので、 N^2 をしても間に合いそうです。

ということで、商品Aと商品Bを全探索しましょう!

ここで kind[i] とは i 番目の商品が何の機能を持っているかを集めたものです。 kind[i].size() で何個の機能があるかを知れるというものだとしましょう。(後ほど説明します。)

すると、問題文の入力変数をそのまま使ったとするとこんな感じになります。

for(int i = 0; i < N; i++){   //  商品Aは i 番目、
  for(int j=0; j < N ; j++){  // 商品Bは j 番目とする
    if(i==j)continue;         //AとBが同じ商品のときはスキップ
    if(P[i] < P[j])continue;  //Bの方が値段が高いときはスキップ

    bool f=true;
    // f=true  Aの機能のすべてをBがもってる
    // f=false Aの機能のうちBが持ってないものがある として

    // ここに Aの機能 を Bが全部 持っているか判定を書く

    if(!f)continue; // 条件満たさないので次へ
    if(P[i]>P[j] || kind[j].size()>kind[i].size() ){
      cout<<"Yes"<<endl;
      return 0; //見つかったのでプログラムをここで終える
    }
  }
}
cout<<"No"<<endl; //見つからなかったときだけここに来る。

機能判定のパート

Q, Aの機能をBが全部持っている判定をどうやって書くの?

  1. std::set を使って書きました。(僕はね)

std::setとは集合を表す連想コンテナ...難しいね。

どういうものかはちゃんと勉強してほしいけど、ひとまず std::set を使うと、ある数を持ってるか持ってないかを簡単に判別できます。これを使って実装すると以下の通り

// 先に以下をして i番目の商品のもつ機能を用意しておく
kind[i].insert(x);

//以下をさっきの条件判定のところに埋める
bool f=true;     //この下に書く想定
// i 番目の商品が持つ機能を1つずつ x に入れ込む
// for(int i=0; i<S.size();i++) S[i] なんちゃらー みたいな処理を書いている。
// 詳しくは範囲forで検索
for(auto x : kind[i]){
  // j 番目の商品の持つ機能の中で、xの数が0個だったら
  // つまり、xと言う機能を持ってなかったら
  if(kind[j].count(x)==0){ 
    f=false;  // fはfalseとなり条件をみたさない
  }
}

実装例

入力を含めた例をおいておく。

// 入力
int N,M;
cin>>N>>M;
vector<int> P(N);
vector<set<int>> kind(N);
for(int i=0; i<N; i++){
  cin>>P[i];
  int C;
  cin>>C;
  for(int j=0; j<C; j++){
    int F;
    cin>>F;
    kind[i].insert(F);
  }
}
// 入力終わり
for(int i = 0; i < N; i++){   //  商品Aは i 番目、
  for(int j=0; j < N ; j++){  // 商品Bは j 番目とする
    if(i==j)continue;         //AとBが同じ商品のときはスキップ
    if(P[i] < P[j])continue;  //Bの方が値段が高いときはスキップ
    bool f=true;
    for(auto x : kind[i]){
      if(kind[j].count(x)==0){ 
        f=false;  // fはfalseとなり条件をみたさない
      }
    }
    if(!f)continue; // 条件満たさないので次へ
    if(P[i]>P[j] || kind[j].size()>kind[i].size() ){
      cout<<"Yes"<<endl;
      return 0; //見つかったのでプログラムをここで終える
    }
  }
}
cout<<"No"<<endl; //見つからなかったときだけここに来る。

コンテスト中の僕の実際のコード

atcoder.jp

おわりに

今回は愚直に書けますか?が問題のポイントでしたが、機能を全部探すというのが大変だったかもしれません。

vectorで全部確かめても間に合うのかな?その辺の検証はしてないけどこんな感じでsetが使えるといいよねというお話でした。

便利なのでぜひ身につけてみてね。

ここまで見てくれてありがとう。良ければなんか反応してくれると嬉しいよ

それではまたどこかで。

あ、忘れてた。宣伝です。作問したのでよければ来てね。

mma-contest.connpass.com

MMA Contest 015 運営後記

MMA Contest 015 完

お疲れ様でした!ひとまずコンテストの破綻なく終わることができ、大きな事故なく終わることができたのかなと思います。

というわけで、運営情報です。各大学のサークルさんやオンサイトやりたい人、運営の裏側を覗きたい人、アンケートの返事を見たい人。誰でもどうぞ。

運営としてのお話、僕の意図と願い、コンテスト本体の話とかをする予定です。

コンテスト開催までのお話

コンテストを開こうと思ったきっかけ

一言でいうと

「オンラインでコンテストを開けるWriterがそこにいたから」

です。今回のメインWriterのsepa,yktrは1年生ながらMMA ContestをMojacoderで14回も開いています。
これをサークルの力でオンサイト化したらもっと規模のデカい、いい企画になると思って動き出しました。

とはいえ、僕はもう4年生なので、でしゃばりすぎるのは良くないんですけどね。

Gigacode2019で運営に助言したというところから4年、やっと競プロオンサイトを主催できました。長かった

qiita.com

なんとなく僕がやった手続き

やってるの、メール送って告知してるだけなんだけなので、誰でもできます!(ほんと?)

  1. 事前に調査をした(Twitter)
  2. 部会承認
  3. 諸届と企画書を作成
  4. 顧問承認を得る
  5. 課外に企画書を提出(1ヶ月前くらい)
  6. 1ヶ月前になったら教室確保
  7. ゲストWiFi申請用メールを顧問に依頼
  8. HP掲載を課外に依頼(メール
  9. HP乗ったら広報にバナー空き確認(メール
  10. バナー画像作成後提出
  11. 大学パンフなど依頼(広報へメール)
  12. 人を集めて事前準備
  13. 会場関係の手続きをする
  14. (設営はなんとなく)
  15. (当日も気合)
  16. 後片付けや様々な返却をしっかりする

有り余る実力でなんとかしてしまった感じがあるのでいい加減ドキュメント化して引き継ぎをしたい。

オンサイト化をゴリ押した理由

ここに僕の願いがかなり詰まっています。

予選のないオンサイトコンテストを開いて、色んな人に競プロやってる仲間と交流をする機会を提供したいという願いがあって初中級者向けと宣伝しました。このへんは後でちゃんとお話しますが、実態はひどかったですよね、ごめんなさい。

これは別記事でしっかり書きますが、情報オリンピックの本選にオンサイト参加できたことが「Nafmo」という人間を作り上げました。そこで交流したり、競プロTwitter界隈やAtCoderを教えていただいたことを含め、とてもかけがえのない経験で、今も大切な宝物なんですね。

でもその経験は予選を通過できる実力を持つ人にたくさんの機会が回ってきます。レートや実力帯が予選通過をするのに足りない人たちにもそういう機会を提供したいし、雰囲気を味わって欲しいという願いがありました。もちろん、コンテストができればそれでいい!って人もいると思いますが、そういう人たちは僕みたいな運営側が意識しなくても楽しんでくれると思っていたので、少し優先度が低かったりします。運営内の人間で僕くらいは「レート低いから行くの怖いなぁ」とか、「こんな弱小でもいいのかな」という人達に寄り添うことを意識していてもいいのかなと思っています。

少し自分の話ですが、CombNaf開催発表時は茶色でしたし、イベント当日は緑だったのに。発表者側には鉄則本を書いた「E869120」を含め自分より高レート帯の人が...という状況を経験しているので、レートを気にする気持ちはわかります。ただ、今回の参加者は(少なくとも僕の前では)、レートを気にしていた人たちも楽しんでいただけたようで良かったです。

nafmo.dev

当日の話

運営の話

僕の悪い癖で、一人で全部ぶん回そうとしてしまうところがあります。そのため、意思疎通がしっかりできていなかったところがありました。僕がTwitterに上げたルートとは別の道順を誘導してしまった、というのがかなり印象に残っています。もう少し運営側も練習が必要ですね。

加えて、教室の広さを優先して教室内で食べれない教室取っちゃって申し訳なかったです。1Fロビーは食べれるので、次回も1Fロビーをご活用ください。

コンテスト本体

問題難易度のチェックを怠ったことを本当に反省しています。申し訳なかったです。彼らは14回もコンテストをやってるので大丈夫だろうと思って解いていませんでした。tester忙しくてできてなかったんですが、解説聞いてたら僕も2問で終わるかなぁとなってしまいました。

次回はちゃんと問題をときますね。あと初心者向け詐欺してごめんなさい。僕が普段予選を通ることがない層にもオンサイトの機会を!とか言ってるのに問題セットがこれでは、救われないですよね。本当に申し訳ないです。

ところで、こんな意見もあるのでこれを胸に抱いて逃げていきたいと思います。

正直な話をすると、オンサイトとなると問題に触れる人数がいつもの10倍くらいに膨れ上がってると思っていて、やっぱりたくさんの人の目につくとまだまだ我々のコンテストは「荒削り」なんだなぁと思いました。少ない人数だとそこまで大げさな指摘はこないしね...精進します。

僕の当日スライド解説載せておきます。 MMA Contest 015(Nafmo).pdf - Google ドライブ

僕の問題

A問題:DDCC文字列のペナを配れていい感じのA問題だったかなと(ABC準拠できたかな~)

B問題:stoiの2進変換、繰り上がりがなければXORなどを伝えられてよかったかなと

H問題:半分全列挙をだしたのですが、Pythonに気を使ったら定数倍が軽く6乗全探索が通るらしい。下手くそでごめんなさい

アンケートに対しての個人的な返答

僕の考えであって他2人の考えとは違う可能性があることをご了承ください

  • 交流できて楽しかった
  • オンサイト初参加で楽しかった
  • 集まって問題解くのが楽しかった

この辺は素直にありがたい感想です。ありがとうございます

  • 大人数さばくの大変だったと思うのでありがとうございました
  • 100人規模でわいわいやれて楽しかった
  • 大人数で集まれてよかった

大変でしたがやってよかったです。次回はもっとスムーズになるように頑張ります。

  • もう少し灰~茶の問題がほしかったです。
  • 初心者向け...?な問題セットだったとおもいます

次回は問題セットを見直します。初めてオンサイトということで見逃してください

  • 解説がスライドと黒板で統一感がなかった
  • 黒板解説で文字が見にくかった
  • 予備校の授業を受けに来たわけではないのでスライドがほしい
  • 講義みたいで面白かった
  • 黒板解説、好きです ぜひ次回も
  • しっかり用意されていたようなので、必要十分な解説だったように思います。
  • もう少し長く解説を聞きたかったです。

意見割れますね、この辺はもう少し準備したいと思います。

終わりに

次回の話

8月とかにやりたいなぁと思っています。ぜひ

yukicoderさんへの感謝

3倍、本当にありがたいです。

またyukicoderにお世話になる可能性が高いです。よろしければぜひ、よろしくお願いします。

緑Coderが取り組む検索エンジンの高速化(Yahoo Internship2022)

(この記事は社員さんに確認していただき、守秘義務的に問題ない範囲の情報のみの記載となっています)

はじめに

お久しぶりです。定期的にアウトプットしなければと思う反面、なかなかできておりません。

今回は久々にアウトプットするべき経験を積んだので、書いていきたいと思います。

例によって長いので飛ばし飛ばしで見てね

Yahoo Internship2022 参加記

Yahooさんのインターンに参加させていただきました!

正直びっくり。通ると思っていなかったので。参加記をまとめていきます。

インターンに参加するまで

流れの話

  1. 面白そうなコースがあるのに締め切り当日に気づく
  2. ギリギリに申し込んでコーディングテスト
  3. 面接
  4. 採用

という流れでした。自分の大学同期が「君の知ってる人でもコーディングテストで落ちてる人結構いるよ?」といってたので面接までたどり着けて満足という感じでした。コーディングテストだけ通って面接落ちるパターンに慣れすぎて、また落ちるのに結果先延ばしやとか思うくらいにはなっていたかも。でもYahooは難しかった。正直落とされると思ってたからびっくり。

参加コース

検索エンジンアルゴリズムの分析・性能改善を通して検索エンジンの高速化検証の過程を体験」

というコース。

必要な経験/スキル:C++の開発経験&データ構造とアルゴリズムに関する基礎知識

競プロでC++書いてきた人が嬉しい要求で即Goしました。

about.yahoo.co.jp

参加が決まってから

正直バイトばっかりやってました。他社インターンや謎のセミナーのチューターなど、休みが全然なくてしんどかったです。連絡受けた8/15が夏休み開始日でしたので、本当に夏休みは労働に溶けましたね...

手続きたくさん、PCが届いたり、ランチ会のご飯予約をしたり、色々ありましたね。締切は守りましょう。

もらったもの

ステッカー、PCにペタペタはりました(Yahoo以外も貼ってる...)
技育博での企業さんが多いのでアレ

https://pbs.twimg.com/media/Fdgv-kFakAEG0MJ?format=jpg&name=large

Tシャツ(ここ以外で着れない)

https://pbs.twimg.com/media/FdQGae_aEAADIC9?format=jpg&name=large

家にトートあふれるようになりました。ノートとボールペンとスマホリング

https://pbs.twimg.com/media/FdgxLyBagAArPS8?format=jpg&name=large

ノベルティたくさんマジで嬉しい。ありがとうございます

やったこと

インターンの課題のお話から

ざっと概要

前半3日:改善
後半4日:発表資料とデータ整理
最終日:成果発表

ほとんど資料に溶かしました。学会発表とか輪講とかやってるとなれるらしい。経験値の差が出てしまいました。

検索エンジンアルゴリズムの分析・性能改善

これは何をするかというと、ソースコードを読みました。そこから考えます。

競技プログラマ特有の計算量の考え方とか、ボトルネックの考え方から二分探索に目をつけ、いい感じにしました。「\ボンッ/グオーーーー!」しないようにしましょうね。え?古い?

競技プログラミングは役に立つ」といったところでしょうか

いい感じがどこまで言っていいのかわからないので難しい...

二分探索の最大比較回数が  \log_2(N) *1 なので、それを利用した改善を行いました。

実際どうだったかと言うと、時間が半分くらい早くなって最高となりました。自分のコードで早くなるのを見るのは気持ちいいね。

自分用にベンチ用意してくれたり、結果見やすいように環境加工して頂いたメンターさんには感謝しかなかったです。ありがとうございました。

加えて、「検索の仕組み」みたいなものも学べました。知らなかったので新鮮でした。面白い。ただ、やっぱり高速化改善Onlyと言った業務はなく、色々な分野が絡まり合ってできてるなというのを感じた。幅広くできる人材になりたいね。

チーム開発の気づき

「コードは書くより読むほうが多いから」

という発言は結構自分の中でずっしりきました。自分も読んで改善点見つけてるしね。

コーディング規則でコンパイルが通るコードがエラーになったりするのチーム開発環境って感じがしていい経験値だった。あれすごいなぁと思いました。

C++で助かったぁになってます。PythonC#だったら、脳から直接コーディングが出来なくて時間かかったと思ってるので。

あと授業ちゃんとやっててよかった、Linux触れたのとSSH configとか触れたの良かった。授業と合わせてMMA入ってて良かったポイントですね。

朝会の話

参加任意ではありましたが、僕はこれにしっかり全部でました。 参加した方がいいと個人的には感じました。うちのチームだったからかもしれないですが、チームの社員さんが取り組んでることの共有やこれからやること、問題など、どんな感じで動いてるかを知れる場所になっていました。

インターンは調整されたレールの上をある程度歩けるけど、朝会にいると実際の業務でやってることがわかりました。自分がやってることが一部でしかないというのを実感できて最高でした。(いろんなことが絡み合ってるなーと言うのを目の当たりにしてよかった。)

自分の課題を解決するだけ、ではなく実際に仕事がどう動いているかを直接見れる機会なので僕は良かったと思いました。

1on1の話

ここには書けないあれやこれ、課題に関する話やなんでも色々お話できて良かったです。

やっぱり学生の目線でない人と話すのは色々な気づきが得られるので面白いですね。なかなかそういう立場の人と話すことがないのでいい機会でした。

成果発表会の話

いやマジで良かったです。

自分の配属チーム以外のところから来てくださった方は、自分のところとの違いをお話してくださいました。自分がやってたことを客観視できてなかったのですが、コメントで他と違うことをやってることを第三者視点で俯瞰できるような、見通しを良くしていただけるコメントを頂けました。うちのチームではあなたのやってたことは出来ないけど、配属されたチーム「らしさ」がでててよかった...とのこと

俺のやってたことはそんな意味が...となるコメントだったり、OSSやってみたら?など新たな指針も...あと単純に成果出しててすごいというお褒めの言葉も、自信になりました。

正直僕はよくある「素人質問で恐縮ですが...」とかそんな感じでボコボコにされるのを想像してたので、褒められてすごく安心というか、不安が消えホッとしました。

これも資料添削や事前練習に付き合ってくださったチームの社員さんのおかげです。よかった。自分の資料作りの感覚はまちがってなかったなぁと自信になりましたね。

懇談会的なやつの話

初日のランチ会と最終日の懇親会がありました。 ランチでうなぎ一匹まるごととか色々豪華な物が食べれました。

初日のランチは写真をきれいに取り忘れましたが...懇談会にはこんな感じのディナーセット。良すぎる。9月なのでみたらし団子もセット。(サトウのごはんとお茶とジュース(酒セットを頼まなかったから)もあったよ)

https://pbs.twimg.com/media/FdQmeTmaEAEoSbB?format=jpg&name=large

ところで酒が飲めないので、お酒2本セットは頼めませんでした。30%(果汁)なのに安く済ませてしまいました...

どちらもチームの人たちとのレイドバトルだったので僕はチームの人とお話できて嬉しかったのですが、食べる暇が本当になくて、時間足りね~になった。

当たり前ですが、1人の社員さんが喋っている間、他の社員は食べれますからね...社員同士の雑談を聞く会にはならないよねぇ。

感想

悔しみがすごいありますね。流石に資料作ってる時間の方が長いのは悔しいですね。

仕事としてはこれくらいの割合になるのかもしれないという意味ではいい経験値なのかもしれません。

B3でのインターンは珍しいらしく、上手くできるか心配でした。それでも優秀と言っていただけて嬉しかったなぁと思います。M1には勝てないと思ってたのですが、一つでもお役に立てたなら良かったです。

企業の雰囲気を感じた

あまりここには書きませんが、会社で働いてる人、そして文化、勤務の雰囲気が見えるのはインターンの収穫として大きいですね。

6社も面接受けてると面接だけでもかなり雰囲気わかるようになって、逆質問もやりやすくなるんですが、実際に参加すると違いましたね。

一緒に(同じ作業をしていると言う意味ではなく)働くことによる解像度の上がり具合がとてもいい経験になりました。労働の一つの形が少しわかってよかった。

あと設定漏れでログインできないの当たり前なのに打ち間違えか~ って何回もログイン失敗してセキュリティアラート踏んで連絡来たの会社や...ってなった。ご迷惑おかけしました。

反省点

フィードバック面接をしていただき、振り返りをすごく大切にしている会社なんだなという風に思いました。ここまでコスト掛けるのも学生のためだったらいいなぁとか、将来の日本のため(Update Japan)とかだったらいいなぁと思います。採用のためというのももちろんあるとは思いますが。

時間の使い方が下手くそで、ゴールが見えないのがすごく不安でした。これを解消するべく資料を作ったら結構時間をかけてしまい、本題の改善にかける時間が少なくなってしまったなぁと思いました。 メインの課題がどちらなのか、を重視するべきでしたね。お陰様で、かなり伝わるプレゼンはできましたし、それはそれで良かったと思うのですが...悔しい。

次はもっと挑戦的に行きたいと思います。1回失敗したら次はやらかさないので...。次どこでお仕事するかわからないですけど、学生なので失敗をもっと恐れず挑戦してみようと思います。

おわりに

やっぱり実際に見てみると変わりますね。

コルブの経験学習モデル 、すごい大事にされていたのを覚えています。こうしてアウトプットして忘れないようにしているのもその一つです。ちゃんと振り返って自分の中の成長の材料として消化しきりたいですね。

自分を受け入れていただき、いい経験になり、たくさん勉強できました。ありがとうございました!!!!!!!!!!!!!!

Yahoo! インターン、自分にとっては最高の経験になりました。やりたいことがあるならオススメです、是非来年以降チェックしてみてくださいね!

蛇足

今思い返して、インターン選びに関する少しの後悔の話。

面白そうなものを片っ端から出して、1つ1つに関して目標とかゴールとか、何を得るために行くんだろうというのを考えてなかったなと思いました。業務の雰囲気を知りたいとかそんなふわっとした理由で出しまくってもいいことないなぁ...と。

インターンに参加した人が偉いわけでもすごいわけでもなく、そこで何を得たか、何をなせたか、そこにしかない機会を掴め取れたかというのが大事だと感じました。インターンに参加しているその時間で、参加してない人でも同じくらい濃密な時間を過ごすことは難しくないのかもな...と思いました。

そこでしか出来ない経験をどれだけ掴み取れるかゲームみたいな部分があると思います。そういうものを取りこぼすともったいないなと感じて、できることを最大限やってきたつもりです。

何がしたくて、自分がどうなりたくて、成長するための機会が欲しくて、だから参加したいんだみたいなものが明確になってると、「インターンだから得られた」ものをより最大化できそうだなと思いました。

ゴール設定とそれが満たされたかの振り返りが大事だと教えてもらえた気がします。なんとなくを減らしたいね。

以上蛇足でした。

*1:最後違う場合は+1とかなるかも?(厳密な話ができず申し訳ない)

ABC271 D - Flip and Adjust

DはDPのD

アウトプットのオタクになります。

僕が考えたことメモなので解説ではありません。悪しからず

DPを考える

ナップサックみたい解いてあげれば出来ます、あんまりよくない復元の仕方してるかもしれないけど出来たのでヨシ!

REを踏んだんですけどこんな感じでいけました

REP(i,N+1){
   REP(j,S+2){
   if(j>=a[i]){if(dp[i][j-a[i]]!="x")dp[i+1][j]=dp[i][j-a[i]]+'H';}
     if(j>=b[i]){if(dp[i][j-b[i]]!="x")dp[i+1][j]=dp[i][j-b[i]]+'T';}
  }
}

なんかできました。

dp[i番目までカードを使ったとき][合計j]=それを満たす裏表の文字列

みたいにしてあげました。えいやっってやったら通ってしまったのでヨシ。

個人的ポイント

ナップサックの亜種に見えたのでなんかうまいこと使えないか考えてみるとできました

ABC 243 D - Moves on Binary Tree から考える競プロでのクソデカ数

(210)100の処理ってなんだよ(笑)

雑感です. 解説ではないのでわかりにくくても許してね.振り返りを記録してるだけなので....

最初に取った方針

+1 の前に出てくる ×2の数(U(-1),LR(+1)で処理したもの)と後に出てくる×2の数を使って+1が出てくるごとに何倍すればいいか(or 足さないか)を記録する

→多分できるんだろうけどバグる

※誰か実装できた人教えてください,僕は無理でした

いわゆるゴリ押しってやつ

クソデカ数がでてきたときの気持ち

  1.  O(N) の操作(ループ・配列)ともにしない!
  2. 直接シミュレーションしないで規則性を見つける!
  3. 圧縮できる情報は圧縮する!
  4. Pythonを使う
  5. 文字列として扱い数字として見ない!←今回はこれ

long longに収まらない桁の足し算掛け算とかはstringで筆算すればできますよね....授業でやらされたの思い出しました.

正解解法

ということで1時間考えたのでAtCoderの解説読んでいいでしょうと言う感じでサクッと正解しました.解説読みゃ一瞬でしたね.どうやって思いつくんだ....(勘の鈍りを感じる)

文字列で考えるがわりかしこの解法にたどり着きやすそうだなと思いました.

  1.  Xを2進数で表して,string Tに入れる(高々60桁)
  2. Uが来たらpop_back() *1
  3. Rが来たら0を,Lが来たら1を追加する
  4. 最後にbitを10進数に直して出力
    1. 直し方はans*=2と(+T[i]-'0')を繰り返すだけ

できました.この問題から得ることはそこまで多くないので振り返って次にいこうと思います(1hくらいかけてしまった......)

*1:C++stringに末尾消すって関数あるの初めて知った

ABC242 C - 1111gal password から見るDPの話

CはDPのC(え?)

お久しぶりです. 最近AtCoder ABCのC問題にDPがさらっとでてくるようになってきていて,競プロ界隈のレベルの上昇度を感じます.Nafmoといいます.

古の競プロerを自称しているNafmo(2017-2018)ですが,最近落ち着いたのでまたやろうかなと思ってやっています.リハビリ状態というのと,全盛期でもできたか怪しいDPを解いて楽しくなったので記事を書きたいと思います.

【注意】久々の記事なので温かい目で見守ってください.間違いを見つけた場合は優しく教えていただけると大変助かります.よろしくお願いします.

(私マンボウなので鋭くなくても雑なまさかり受けると再起不能になるので優しくお願いします....ユルシテ)

なぜ記事を書こうと思ったのか

単純に私が試行錯誤して解けた経験を共有することで,他の誰かの役に立ってほしいと願うからです(自己満ですね)

ABC242 C - 1111gal password

問題概要

この条件を満たす整数Xの個数を998244353で割ったあまりは?

条件(ちょい雑)

  • N桁整数
  • 整数Xのすべての桁は1-9
  • 整数Xはある桁を見た時,その次の桁との差の絶対値が1以下

正解解法への過程(Nafmoの場合)

なんとなく書いていきます.

最初は全探索から考えよう
  • 深さ優先探索で各桁3種類ずつ遷移しようとした
    • つまり,その桁が3なら,次の桁は2,3,4というような感じで
    • N桁潜れたらans++して行く
  • 計算量爆発( O(3^ N) )
    • 桁ごとに選択肢が3倍になっていくのでそれはそう...
    • 全探索だしね
計算量改善しよう

一桁ずつ決めていくから,前から順番に数えていけば良さそう!

今,n桁目を見ているとします. x_in桁目がiの時の条件を満たしている整数の数だとすると,n+1桁目は (x _ {i-1}+x _ i+x _ {i+1})個だけあることになり,一つ前の状態がわかっていれば求めることができる事に気づきました(添字がはみ出た場合は0とします)

したら後はループを回せばいいよねってことで以下がソースコード

// X:次の状態,x:前の状態
    ll X[]={0,1,1,1,1,1,1,1,1,1,0};
    for(int i=0;i<N-1;i++){
        ll x[11];
        REP(k,11)x[k]=X[k];
        X[1]=(x[1]+x[2])%MOD;
        X[9]=(x[9]+x[8])%MOD;
        for(int k=2;k<=8;k++){
            X[k]=(x[k-1]+x[k]+x[k+1])%MOD;
        }
    }
// X[1]~X[9]の和が答え

配るDPともらうDP,メモ化再帰と漸化式ループDP

なにそれという方向けに,けんちょんの記事を

qiita.com

今までの私はメモ化再帰しか書けませんでした.

しかし,この問題をACしたときはナチュラルに漸化式のような考え方ができています.(公式解説はこれを二次元配列にしたものなので...)

これ,精進していない謎の成長でした.メモ化再帰で配るDPが書きにくい(※要出典*1 )(個人の感想)から生まれたものな気がしています.

どういうことかと言うと,自分のメモ化再帰の癖で return dp[i-1][~~~]+dp[i-1][~~~] のような1個前(複数前)の状態から求めたい結果を導くというように書く癖があります.これが100%悪いとは思っていませんでしたが,これだと今回のような配るタイプは難しく感じました.

実装してみてわかったこともあって,配ったりもらったりを漸化式立てて脳死ループを回す方が,再帰の境界処理と遷移を考えるより楽ということです.式立てられれば終わりなので...

先ほど貼った記事の漸化式ループDPのメリットが出てますね.できるようになりたい!という感想セクションでした.

話題になった桁DPと言われているもの

今回の問題はそんな難しく考えなくても,注目している桁とその前の桁だけ見れば良いので大丈夫だったりします.なのでこの問題に限っては,桁DPという名前を意識しなくてもいいのかなと思います.

でもコンテスト終了時に名前を見るときになりますよね.(???「私,気になります」) そこでなぜ名前が上がったのかを考えてみました.

考え方が似てたからなんだろうな(ド直球)というのと,桁(に注目して操作する)DPと言いたかったのかな?と思いました.


桁DPってなんだよという方は,私はこのサイトが分かりやすかったので参考までに.

桁DPの痒いところに手が届く解説 - Qiita

以下のような分け方で中学受験の問題解いた記憶有りませんか?私はあるのですっと入ってきました.

Qiitaに乗ってた@pinokions009 さんの説明画像

つまりどういうことかと言うと,1桁ずつ決めていく過程で,ここがこの数なら残り全部オッケーっていう場合と,そうじゃない場合を分けて考えるということをしたいという話です.未満(smaller)フラグについてもわかりやすかったですね.個人の感想ですが...

参考2 ココも好きでした.合わせて見てみるといいかも・・・?
桁DP(Digit DP) を考え方から問題例まで徹底解説! | アルゴリズムロジック


さて,話をもとに戻します.

私の考えとしては,上位陣(?)はこの問題は桁ごとに操作をして行くことを伝えて桁DPといえば解説が住んじゃうような問題だったからそうなったのかなと思いました.

今の私(緑)には桁DPの理解よりも自分の実力適性帯を早く解ければそれでいいと感じました.

問題から見た振り返りおしまい.

終わりに

この記事は大学の仲間に「桁DPわからんから説明してほしい」とこの問題の出題後に言われたから書きました.25日遅れですよ! ...ごめんなさい.定期試験とか挟まったし(言い訳やめてください)

桁DPの解説をしてほしいという話だったのに結論が桁DPとかいいからこの問題が解けるDPの考え方がわかればヨシ!(画像略)という結論なの悲しいですね.

気が向いたりしたらまた書きます.面白かったりなにか得るものがあったら嬉しいですし,それをTwitterに書いてくれたりStar付けてくれたりするとモチベが上がるのでまた書く可能性が上がります.よろしくお願いします.頑張って2018全盛期の自分を超えたい!これからも競プロがんばります!

それではまた.(1時間もかけたのやばいな,普通に1問解けるやんけ)

*1:でもけんちょんの記事にはそう書いてある