Відео

応援しています。

今回、A問題もB問題もややこしかった！ B問題、正規表現って処理で文字列を置換する方法もあるよ！ 正規表現の変換ルールの書き方が、これまたおまじない感半端ないので 全然覚えてないけど、単純な置き換えなら以下の通りでOK！ これを、コンテスト中に浮かばないのが我ながら残念ｗ ```cpp int main() { string S; cin >> S; // 正規表現で文字列全体に置換処理をおこなう "00"->"w" string T = regex_replace(S, regex("00"), "w"); cout << "S:"<< S << " "; cout << "T:"<< T << " "; // 置換の結果を確認して cout << size(T) << endl; // 解 } ```

あれ、衣装戻ったんだ

2完おめでとうございまーす！🎉 A問題もB問題も細かい罠がある問題でしたが、無事突破しているのはすごい！ こちら今回5完で、初めての青パフォ、初めての3桁順位達成でした。 willowさんの頑張りに触発されたおかげがとても大きいです。 これからもお互い頑張っていきましょうね！

私がコンテスト本番で使った解法、置いときますね。 多分こっちの方が簡単です。 queueの出番はないですが……。 最初に植物を植えるときは、高さ0に植えます。 植木鉢の高さを適当なvectorに追加していきます。 時間が経過するときには、植物のてっぺんの高さの変化を別の整数に計算しておきます。 で、追加で種を植えるとき、高さ0じゃなく、今植物のてっぺんがある高さに植木鉢を用意します。 植木鉢の高さを適当なvectorに追加していきます。 こうすると、全植物のてっぺんの高さが自動的に統一されます。 植物の長さは「てっぺんの高さ-各植木鉢の高さ」で計算できるので、日付の経過が1変数の更新で済みます。 刈り取るときは、植物の長さの条件を植木鉢の高さの条件に書き直します。 植木鉢の高さのvectorは自動的にソートされているので、二分探索でも前から順に確認でもなんでもいいので、どこまで刈るべきかはすぐ計算できます。

長時間の勉強お疲れ様です。解けない問題でも向き合い続けられるのすごい。 この問題、実はいくつかのポイントを押さえるとキューを用いさえすれば、難しいアルゴリズム無しに解くことができます。 ポイントは •クエリが進むほど時間はどんどん先に進んでいる(戻ることはない) •新しく植える植物は全部高さが0 •現在時刻と、植えた時刻さえあれば植物の高さが計算できる この3点に着目するのが大事です。 時間が進み続け、常に高さ0で植えるのだから、後の方にくるクエリ1で植える植物の方が背が低くなるはずです。 なので、キューに植物を植えて、その先頭をみた時、先頭が収穫できないならそれ以降も収穫できません(残っている植物のうち先頭がいちばん大きいから) これで3の収穫クエリについて全要素見る必要はなくなりました。先頭が収穫できないなら探索を止めていいわけです。 とはいえ、日が進んだときに毎回キューの中身に全部Tを足していると、植物が大量にある場合 (植物の数)×(日数経過クエリの数)の計算回数がいります。 植物を植えまくってから、日数経過だけを何回も繰り返されると時間がものすごいかかってしまいます。 TLEとなるテストケースはこれですね。 ここで、「植物の高さって実は管理しなくてもいいんじゃない？」と気付けるかが大事になります。 実は「現在の日付」と「植えた日付」さえあれば高さは逆算できるのです。 例として、現在4日目で1日目に植物を植えたとします。今の高さは(4 - 1) = 3になりますね。 このように高さの情報がなくても「現在の日付」と「植えた日付」さえわかれば計算で求められるのです。 現在の日付は日数経過クエリを足しあわせればわかります。 現在の日付さえ管理しておけば、キューの中には高さが入っていなくても「植えた日付」さえ入っていればキューに入っている植物の高さは求められます。 こうすると、1番のクエリは「日付をキューに入れる」、2番のクエリは「現在の日付にTを足す」だけになります。 あとは3番のクエリですが、入れるものが高さから現在時刻に変わっても上で触れた通り「先のクエリで入った植物の方が大きい」ので先頭が収穫できるかをwhile文などで繰り返せばよいです。配列でなくキューを使うことで、収穫したらもうその植物について調べなくてよくなりますね。 「全部の高さを操作すると時間が足りないからなにか工夫できないか？」 「先に入った方が背が高いなら先頭を見ればよくて、収穫済みなら取り出していいんだからキューを使うと楽になる」という発想に至るのがポイントな問題でした

おぉ！今、気がついた！ 今日、ようつべのアカをブラアカに変更して、なんかコメ消えてる？ってなってる。 登録したチャンネルとか大丈夫みたいなんだけどね あ、見るアカなんでなんもないですｗ D問題、キューだけでなく、今の時間は？って情報を持って、 植えたとき、今の時間をキューに突っ込んで 収穫のとき、キューの先頭から見ていって、今の時間ー植えた時間＝その植木の高さなので その植木の高さが H 以上だったら、キューからひっこ抜いて、収穫する感じかな？ 流石に時間的に、試してないから、できるかどうかしらんけどW

お疲れ様です！　ABC後にゆっくり見てください。 【ABC379 D問題】abc379/submissions/61140026 問題文通りに、経過日数に応じてそれぞれの植木鉢の植物の高さを増加させたくなります。 ですがそのままシミュレーションすると、見事にTLEします。 そこで、queueに入れるデータを植物の高さではなくて、植えた日を格納することにします。 高さチェックの際は、今日の日付と植えた日の日数差を計算することで、その植物の高さが計算できます！ 【キューは使わないけどおすすめ問題】ABC239 C問題 連想配列（mapのこと）　必須 連長圧縮　あると便利。abc259/submissions/61140548。abc329/submissions/61140583。 尺取法　強力な技だけど、難しいので今は後回し。二分探索がある程度わかってからのほうが理解しやすいので、二分探索とか累積和について理解を深めることを優先したい。 グラフは、簡単な教育的問題がごくまれにB問題で出題されているので、それは取り組んでもいいかも。 ダブリング　不要。

え、これqueue使う解法なんてあるの……？ 一体どこで使うんだ……？

解けなくても考えることは大事ですからね。ゆっくりじっくり焦らずに。

お疲れ様です 鉄則本おすすめですよ！！ これで体系的な知識が身に着けられると思います

おお、ちゃんと正しく理解できてますね！ 一度自分で書いたbfsのコードをコピペでパッと取り出せるようにしておくと、今後「あっbfsだ」で一瞬でAC取れたりします、おすすめ。 00:06:18 関数に切り出すと速かったのだとしたら、最適化がより進められたおかげなのかなと思います。 C++くんはコンパイルで機械にとってわかりやすい形に直すわけですが、関数に切り出すことでさらに機械にとって都合がいい形にできるようになったということですね。 まあ、「多分そう」レベルなので違う可能性もありますが。

探索について深堀りしていけてますね！ 幅優先探索の特徴として、辺の重みが一定の場合(この問題の場合上下左右に移動するのが常に移動コスト1なので重みが一緒) 初めて訪れたタイミングが結果的に最短距離を表します。 深さ優先探索は必ずしも最短路にならないので「重みなし最短距離を求める必要がある」ときは幅優先探索のほうが強いですね(頂点に操作しながら動く、みたいなときは移動をなぞる挙動をする深さ優先探索も利点があります) ちなみに、動画で学んだ通り幅優先探索ではキューをがっつり使うのでキューについての理解が深まると思います。 たとえば、ABC379のD問題ですがキューの知識と、ちょっとの工夫で解けるので頭の体操がてらおすすめです。

このC問題、BFSで解くのヤバい！ ず～とWAがとれなくて？？？？？ で気がついた！ 通常のBFSって水路に水を注いで広がっていくイメージを持ってて 当然、障害物は避けるから、障害物に囲まれる内と外は行き来できないことになる でも今回は、障害物(机)の上を加湿器の水蒸気が越えて来る！ 通常の感覚で書いた、障害物を避けるコードが邪魔して、ず～とWAだった！ 逆に、通常のBFS書くときは障害物を避けるコードを忘れずにw あと、なにげに"多始点BFS"ぽくなってるのもヤバいな！ 最近、多始点BFSで解く問題があったので、気がついたけど まあ、小さい範囲に２点だけなので別々にBFSやって、後でまとめるのもありだけど 多始点BFS思い出して、少しコードが少なくなったかな？ 結局、最終的なコードは、この動画と大差ないコードになったとさｗ

まだ見てない段階でのコメントですが…… これをbfsで解くって、同じ回のC問題（bfsの中でも比較的難しく、難易度800近くあったはず）のさらに応用の話になると思うんです。 大丈夫かな……willowさんの脳みそ爆発してないかな……？

お疲れ様でした☀ 怒涛の学習ラッシュ！ 視聴が追い付かないぃぃ

A問題、私と同じ解法！公式解説の2で割る方法より素直な解法だと思うよ！ B問題、２つの変数の値の交換には３つ目の変数を使うのは基本ですね c++にはswap関数があるので手抜きできますけどｗ a,bの変数の値を交換するなら 1)避難用の変数tを用意 2)t=a // aの値を避難 3)a=b // aの値を壊してbの値に変更 4)b=t // bの値を壊してt=aの値に変更 t,a,bでtを犠牲にして値をループさせる感じかな？ C問題、cからaへの辺を読み落として？？？ってなってました。戻るんか～い！w 脳筋コード書いておきます これも一応、O(N^3),N<=100なので十分間に合います 公式解法は、無駄を省くために事前にfor文で a<b<c となるように開始の頂点をいじってます 以下のコードでは a<b<cを直前で判定しているだけです ```cpp // 最初のおまじないと、repマクロ追加してください int main(){ int n, m; cin>>n>>m; // n:頂点数, m:辺数の入力 vector G(n, vector<bool>(n, false)); // 隣接行列(Adjacency matrix), n*n while (m--) { // 辺情報を m 個入力, 隣接行列を作成 int u, v; cin>>u>>v; // u<v u--; v--; G[u][v] = true; // u->v, u<v: uからvへの辺がある G[v][u] = true; // v->u, v>u: vからuへの辺がある, これがないと c>a の情報がとれない } int ans = 0; rep(a, n) rep(b, n) rep(c, n){ // 頂点 a,b,c を全探索 if (G[a][b] == false) continue; // a->b: aからbへの辺がない if (G[b][c] == false) continue; // b->c: bからcへの辺がない if (G[c][a] == false) continue; // c->a: cからaへの辺がない, a<b<c -> c>a の情報がほしい // a->b,b->c,c->aの３つの辺がある if(a<b && b<c) ans++; // 頂点間の大小関係があっていれば +1 } cout<<ans<<endl; } ```

A問題 2人の得票数をmaxとminに直して扱いやすくする、それをもう当たり前のようにスッとできたのは成長ですね！ B問題 もしかしてwillowさん、char型をstring型の亜種だと思ってません？ 昨日の復習枠でもそうなんですが、char型の変数に.at()をつけて怒られるシーンが何度も繰り返し流れているように見受けられます。 charとstringは根本的に全くの別物です。 ただ一部の演算や関数がchar型でもstring型でも同じ書き方で似たような結果を出してくれるだけです。 そういう一部の例外を除けば、.at()のようなstring型用のコードをchar型に使えば当然怒られますし、-‘A’のようなchar型用のコードをstring型に使ってももちろん怒られます。 「散々いろいろな書き方をしてやっとコンパイル通る解き方見つけたー」みたいにやってますが、実際はどの解き方でもちゃんと書けば正解できます。 ただwillowさんが.at()を偶然にも全部正しくstring型に使う幸運が発生するまでガチャしてるだけなんです。 ところで、この問題自体ですが、s.at(i)とかはchar型変数として扱えるので、実は swap(s.at(n1-1),s.at(n2-1)); とchar型変数同士の中身のswapで一発で済みますね。 C問題 難易度220完走おめでとうございます！ 加湿器全探索の経験が生きましたね。 今回の問題だけ見るなら確かに遠回りでしたが、今回のwillowさんの考え方が必要になる場面も今後多いですので気を落とさず。

良いクリスマスガウン着てますね。 【ABC262　B問題】abc262/submissions/61086968 Nが100以下という制約から、3重ループも平気と考えた。 Ui<Viという制約から、入力はきれいな順に入ってくることを認識して、それを踏まえてsetに(u, v)の順で格納。 i,j,kをそれぞれa,b,cに見立てる。a<b<cを表現するために、j=i+1から、k=j+1からとしている。

二本立てじゃないですか！ムリの無いようにね 最後のシュミレータは面白い！でもコンテスト中にはなかなかやらないかな？ そろそろマクロとか使って、入力ミスを減らしたり、見通しをよくしたりすることも考えてもよいかも？ 関数で分けるのも見通しがよくなります やりたいことを関数で分けて実装してみました ```cpp // 最初のおまじないは省略しましたので追加してください // repマクロ使ってますので APG4b など参照して追加してください // (APG4bの最後の方に書いてある, "付録4.ループの裏技repマクロ") // rep(i, n) と書かれた部分は for (int i = 0; i < int(n); i++) と置き換えられるというマクロです using P = pair<int, int>; // <h,w>: P と pair<int, int> は同じ型として扱われる vector<P> floors; // 加湿できるか調べたい床の座標を収集しておく // マンハッタン距離を求める int mh(P p1, P p2) { return abs(p1.first - p2.first) + abs(p1.second - p2.second); } // p1, p2 に加湿器を置いたときに加湿される床を数える int count(P p1, P p2, int d) { int c = 0; // 加湿される床の数 for (P p : floors) // 床 p が加湿されるか調べる // 床 p が、加湿器 p1,p2 の少なくとも一方から加湿されるなら +1 する c += mh(p1, p) <= d || mh(p2, p) <= d; return c; } int main() { int H, W, D; cin >> H >> W >> D; vector<string> S(H); rep(h, H) cin >> S[h]; // ここまで、データ入力 rep(h, H) rep(w, W) if (S[h][w] == '.') floors.emplace_back(h, w); // 調べたい床の座標を収集 int ans = 0; for (P p1 : floors) // 床 p1 に加湿器を一つ置く for (P p2 : floors) // 床 p2 に加湿器を一つ置く // 二つの加湿器が別の位置にあるなら、加湿される床を数える // if (p1 != p2) ans = max(ans, count(p1, p2, D)); // (p1,p2) = (a,b),(b,a) と同じ意味の処理を二回するが間にあう // p1 < p2 -> a<b とすると (p1,p2) = (a,b) のみ処理される if (p1 < p2) ans = max(ans, count(p1, p2, D)); // ans = max(ans, count(p1, p2, D)); // ちなみに判定なしでも問題なく十分間にあうｗ // 加湿される床の数は、二つの加湿器が同じ位置にあるなら、一方を別の位置に移動させれば、 // 同じ位置のとき加湿される床の数より、少なくとも +1 した数になるので、同じ位置の場合は max になることはない cout << ans << endl; } ```

予定合わなくてスルーしたんですが、何この激ムズコンテストｗ 正解者0人の問題が複数あるし……

全探索問題の中でもかなりややこしい問題でしたが、理解できたのは素晴らしいですね！ あとはこれを、問題を見て30分くらいでコードまで書けるかどうかですね（高いハードル） 2:16:27 ゲーミングトナカイさん！？ 2:41:30 もしかして： temp1 = floorCells.at(i); でいい 2:58:30 わかる 3:27:22 これ、間違って逆に認識しちゃってませんかね？ バグったコードをよく書いちゃう人ほどatをいっぱい使うのが正解です。 atは、[]とほぼ同じだけど何かおかしかったらエラーで教えてくれる機能と思えばいいです。 つまり、atじゃなく[]にしたらエラー吐かなくなったというのは、「ここバグってるよ」と教えてくれてたのが（ここバグってるけど黙っときゃwillowさんにはバレへんか）になっただけ。 バグが直ったわけじゃないです。 稀に、しょうもないタイポしてたみたいなミスが、書き直したおかげで本当に直る場合もなくはないですが（今回もこれに近い）。

これはむずい！X'masコンは苦しみますコンｗ

メリークリスマス🎄✨

復習しっかりやってるの偉すぎます！ グリッド問題はある程度パターンが決まっているので，慣れれば得点源になりますね！ 364B-Grid Walkで自分だったらこうするな～っていうのを書いてみたので，良ければ参考にしてみてください． 提出# 61044922

setをすごい使い方してるコードですね（もちろん正解であることには間違いない） 「この問題で set<pair> 使うっていったら多分こういうことじゃない？」っていう385Bの解答を本日21時28分57秒にAtCoderに提出しましたんで、よろしければご参考まで。 2:45:11 ﾐﾃﾙｿﾞ 作業用BGM代わりに流しながら、時々「へー、そういう視点もあるんだなあ」なんて思いながら、等倍速で最初から最後まで見させてもらってます。

あ... result、global と local に作ってたｗ 変数は {}の内側から外側の変数は使えますが、外側から内側の変数は使えません 同名の変数は内側が優先です なのでここでは local の result が使われます ここでは global,local のどちらか一方の result の宣言を消して実行してもACのはず？ set_intersection() は、自分も余り使わないので、c++ のHPからコピペしました(覚えられないｗ) 集合の積では、各集合を home = {a,b,c} <- a,b,c: 家の座標 visited = {s,t,c,u,v,a,z} <- s,t,c,u,v,a,z: 訪問した座標 とすると home ∩ visited = {a,b,c} ∩ {s,t,c,u,v,a,z} = {a,c} となり (家があり、かつ、サンタが訪問した)座標の集合となります {a,c} が result に求まるので、その大きさが訪問した家の数になります

配列が0インデックスだから入力の時に-1、出力の時に+1しないといけなかったのは中々に罠でしたね。自分もサンプル見て気づけました。

かわいい...

maxとmapを間違えいます😢

最初は、プログラミング言語の習得（記法や標準ライブラリ、どんなデータ構造があってそれをどう使うか）を学ぶのと、競プロ的思考の習得を別にしたほうがいいかもね。算数でもそうだけど、四則演算しながら文章題解くのは難しいしね。aojとか、そう言うのでまずデータ構造とアルゴリズムを学ぶのが良いのかもしれない。

お疲れ様でした！ 鬼畜サンタさんマジ鬼畜…… （こっちもD問題で沼って4完以上の連続記録ストップ） 初めてのsetさんがset<pair<int,int>>なのはきっついなあ……と思いながら見てたら、さらに難解な方向へ向かっていって笑ってしまったｗ 時間かかったとはいえ、この方針で完走しきった腕力には脱帽。 今回地図をvector<vector<char>>で管理してましたが、実はvector<string>でほぼ同じことができますね。 二次元配列よりも扱いやすくなる（気分の問題で）のでおすすめですよ。

今回はちょっと実装が大変な問題ばかりでしたね。考えれば上手くいくかもしれないですが、色々考慮すべきところがあり時間が足りなさそうでしたね。

まだまだこれから！。私も灰色茶色いったりきたりです！

B問題がんばったね！ 公式解説が一番楽だとは思うけど、set と pair で書いて見ました ```cpp // 最初のヘッダ等は削除してます // unordered_set に pair は基本使えない,。手段はあるらしいけどめんどくさそう set<pair<int, int>> home, ok, visited, result; int main() { int h, w, x, y; cin >> h >> w >> x >> y; for (int i=0; i<h; ++i){ string si; cin >> si; for (int j=0; j<w; ++j){ if (si[j] == '@') home.insert({i, j}); // 家の座標を集合へ if (si[j] != '#') ok.insert({i, j}); // 移動可能な座標を集合へ } } string t; cin >> t; x--, y--; visited.insert({x, y}); // サンタが訪問した座標を集合へ for (char c : t) { x -= c == 'U' && ok.count({x - 1, y}) > 0; x += c == 'D' && ok.count({x + 1, y}) > 0; y -= c == 'L' && ok.count({x, y - 1}) > 0; y += c == 'R' && ok.count({x, y + 1}) > 0; visited.insert({x, y}); } set<pair<int, int>> result; // 集合の積を求める, home ∩ visited set_intersection(home.begin(), home.end(), visited.begin(), visited.end(), inserter(result, result.end())); int cnt = result.size(); cout << x + 1 << ' ' << y + 1 << ' ' << cnt << endl; // puts("ok"); // for(auto[x,y]:ok) cout<<"("<<x<<","<<y<<"), "; // puts(""); // puts("home"); // for(auto[x,y]:home) cout<<"("<<x<<","<<y<<"), "; // puts(""); // puts("visited"); // for(auto[x,y]:visited) cout<<"("<<x<<","<<y<<"), "; // puts(""); // puts("result"); // for(auto[x,y]:result) cout<<"("<<x<<","<<y<<"), "; // puts(""); } ```

お疲れ様でした！ エラーメッセージがたくさん表示されても、それにひるまずにエラー解決する力が以前より格段に上がっていてびっくりしました。 2:08:30 エラーたくさん出たときに、エラーの先頭が探しにくい場合、ターミナルを一度スッキリさせると見やすくなります。 ターミナルに『clear』と入力してEnterすると、ターミナルの記述内容が消せます。 その後、もう一度実行してエラーメッセージを出力させるとエラーメッセージが読みやすくなります。 2:40:00 単語の上でダブルクリックすると、その単語が選択できます。 普通コピーするときは、コピーしたい範囲を選択後にCtrl+Cするのですが、 VScodeの場合、ある行をコピーしたいときは、その行にカーソルがある状態でCtrl+Cすると、その行がコピーできます。 そしてそのままCtrl+Vで貼り付けることができます。 同様に、ある行を削除（切り取り）したい場合、その行にカーソルがある状態でCtrl+Xすると、切り取りできます。

お疲れ様です！ もちろんクリスマスもやりますよね😒

for distinct houses in B, put the houses santa encounters in: set<pair<int, int>>, like set_name.insert({x, y}). since set<> only maintains unique elements, for printing answer we can do: cout<<set_name.size(); this way even if santa encounters the same house twice and we insert in our set, the duplicate entry does not get created.

ABC385お疲れ様です。 A問題、とても図がわかりやすくていいですね。こういうの、むずかしい問題で欲しいときがあるのでうらやましい。 B問題、いろんなアプローチがありそうですね。ペアを使うのも感覚的にはしっくりする実装でいいと思います。 今回はサンタの移動する範囲がせまいので、真面目に配列で管理するのもいい方法ですね。 どうやって家を訪れたか管理するんだろ？というアイデアに関してなんですが、自分は結果的に「サンタが訪れた家(@)は更地(.)にされてしまう」という解法でやりました(こうすれば、サンタが同じ家を2回以上訪れてももう家がない。破壊サンタ) この考えだと更地にした家の数が答えですね。 ペアで管理する、のアイデアはDで近しい方法で解くことができるので大事な発想だとおもいます。

頭が良くて、可愛くて

bit全探索と深さ優先探索(再帰関数)って本質はほぼ同じだった気がします

ちなみに、今回データがa~eの5つしかないので、脳筋5重ループでも解けます！ 要は、a~eを各々解くか解かないかの二択をすればいいわけです データが多いときは再帰かビット全探索といったとこでしょうか？ 以下、脳筋5重ループのコード書いときますw ようつべの都合上、 ハッシュと書いてあるところはハッシュ記号に置き換えて考えてください ```cpp ハッシュinclude <bits/stdc++.h> using namespace std; ハッシュdefine rep(i, n) for (int i = 0; i < (n); ++i) int main() { int a,b,c,d,e; cin >>a>>b>>c>>d>>e; vector<pair<int, string>> ans; rep(i,2) rep(j,2) rep(k,2) rep(l,2) rep(m,2){ int tot = 0; string s = ""; if (i==1) tot+=a, s+='A'; // i==1 -> A問を解いた, i==0 -> 解いてない if (j==1) tot+=b, s+='B'; if (k==1) tot+=c, s+='C'; if (l==1) tot+=d, s+='D'; if (m==1) tot+=e, s+='E'; if (tot==0) continue; // 全て解かないことはないので無視 ans.emplace_back(-tot, s); // -tot とすると得点も文字列も昇順にsortすればよくなる } sort(ans.begin(), ans.end()); for (auto [_tot, s] : ans) cout << s << ' '; } ```

bit全探索では、1つ変数を1つの集合とみています "bits" を集合をあらわす変数とする bitsの二進数の各桁で集合の各要素の有無を表す bitsのある桁が 1なら、それに対応する要素は集合に含まれる 0なら、それに対応する要素は集合に含まれない bit全探索では、要素数は20個ぐらいが限度です 二択が20個あると 2^20 > 10^6 通りになるためです 全体集合の要素数が5個の場合 0 <= bits < (1<<5)=32 がbit全探索の基本的な範囲になります 例 bits = 00000 : 要素がなにもない＝空集合 bits = 01101 : 0,2,3桁目に対応する要素が集合に含まれている bits = 11111 : 全ての要素がある＝全体集合 今回、1つは問題を解いているということなので 空集合はいりませんので、本問の範囲は 1 <= bits < 32 となります digitは2進数の各桁を最下位を0として順番に表し、 集合の要素の"位置"を表してもいます 1<<digit で、ある特定の要素を表します 例 1<<0 = 00001 : 0桁目の要素を表す 1<<1 = 00010 : 1桁目の 1<<2 = 00100 : 2桁目の 1<<3 = 01000 : 3桁目の 1<<4 = 10000 : 4桁目の bits & (1<<digit) は集合から特定の要素のみを取り出します 例 bits = 01101, digit=2 01101:bits 00100:(1<<digit)=(1<<2) ----- 00100:bits & (1<<digit) -> 2桁目の要素は含まれるとわかる 例 bits = 01101, digit=1 01101:bits 00010:(1<<digit)=(1<<1) ----- 00000:bits & (1<<digit) -> 1桁目の要素は含まれないとわかる プログラム言語によっては bits & (1<<digit) == (1<<digit) と判定を書く必要があるようです。これは、集合で書くところの A∩B=B : BはAに含まれる(A⊇B) A∩B!=B : BはAに含まれない(Bの一部が含まれる場合は、今回はないので) と言ったところでしょう

49:30 1<<i と i<<1 を混同しているような？ 1<<i は、1（つまり00001）を用意して、i桁左シフトする計算です。 willowさんが書いた表は、4段目が01000、5段目が10000、となるのが正しいですね。 一方で、i<<1 は、iを用意して、1桁左シフトする計算です。 willowさんが書いた表の1段目を00000にしたものになりますが、この問題では関係ないものですね。

図が綺麗ですごい地頭良さそう！

C問題ネタバレ注意 二進数よくわからないマン向けの31人の名前の用意の仕方を紹介します。 多分、コンテスト中にwillowさんが目指していたことにかなり近いんじゃなかなと思います。 手順1: 空っぽの vector<string> v を用意します。 手順2: 空の文字列をvにpush_back()します。 手順3: 現在のvの要素数をint tmpに格納します。 手順4: 現在のvの要素全てに対し、「後ろにAを書き足したものをvにpush_back()」します。 （このとき、vのサイズがforループの最中に変わってしまうので、i<v.size()で止めようとすると失敗します。必ずi<tmpで止めましょう） 手順5: 現在のvの要素数をint tmpに格納します。 手順6: 現在のvの要素全てに対し、「後ろにBを書き足したものをvにpush_back()」します。 手順7〜12: C、D、Eについて同じことをします。この繰り返しをforループで書けそうならそれでも可。 手順13: 今回は全問不正解者はいない話なので、先頭にいる空文字列をどうにかして削除します。あるいは、名無しさん含めた32人で順位を調べて、出力時に名無しさんだけ出力を飛ばしても可。 （vectorで先頭からの削除は難しいので、reverseして末尾から消すか、名無しさんを出力時に消す方法が現実的かなと思います） ビット全探索（解説でやってる二進数を使うアルゴリズム）は、二進数の性質を利用してこれを素早く行っているだけです。 言い方を変えれば、ビット全探索を使えと言われてる問題はこんな感じの方法でも全部解けます……時間的なリスクさえなければ、ですが。 今回は、後半の作業もあるので、vector<string>のかわりにvector<pair<int,string>>で点数計算も一緒にしちゃうよう改造すると全体が楽になりますね。 あと、再帰関数で解く方法もなくはないので、再帰関数を使おうとしたwillowさんはちゃんと正解です。 かなり複雑な引数渡しをしないといけないのでビット全探索より難度が跳ね上がりますけども。

お疲れ様でした！ もう2完は十分に射程圏内ですね！ レーティングくん「レーティングです。ディじゃないです。名前だけでも覚えて帰ってね！」 WAしたのを黄色のまま残してあるみたいですが、数日経ってから再挑戦してAC取れるものは緑にしといた方がいいかもしれませんね。 あんまり黄色があると、「うわぁ復習しなきゃいけないの山盛りだぁ」で1つも復習しなくなる未来が見える気がします。 数日後にAC取れたなら、実際に要復習問題ではなくなってるわけですし。 C問題の解説にあるvector<pair>のsortは、基本的な道具のみの組み合わせでありながら、使いこなせるとめっちゃめちゃ便利です。 前半の数学的あれこれがわからなければ31人分全部書く脳筋コードを書いてでも、後半のやり方をここで身につけられると嬉しいですね。

お疲れ様です✨

お疲れ様でした！ A問題とB問題は両方ともスムーズに問題文の意味を把握できていて順調！ C問題で一番難しいのは、参加者名簿を作る箇所だと思います。 31人の参加者というのは2の5乗-1の数です。 2^5 = 32 0人の参加者というわけにはいかないので、1だけ小さくなっています。 各問題の正解者数が全て16だったのは、32/2 = 16とリンクします。 （今回の場合、解説の冒頭にあったように、力技で31名の名簿をコピペして作る、 という手で対処するのもありだったかも） 名簿を作るためには、「ビット全探索」という考え方を使います。 簡単のために長さ3文字、使える文字種　A, B, C　で説明すると、 「A」を使うか、使わないか 「B」を使うか、使わないか 「C」を使うか、使わないか 以下のコードをmainに貼り付けると動きます。 普段ビット全探索ではfor文内でi=0開始することが多いのですが、今回は空ではない文字列を作りたいので、1開始にしています。 int M = 3; for(int i=1; i<(1<<M); i++) { string S; for(int j=0; j<M; j++) { if((i>>j)&1) { char ch = 'A' + j; S += ch; } } cout << S << endl; } 【ビット全探索を使う問題】ABC321C、ABC289C

お疲れ様ぁ くっ喋り方が可愛すぎる．．．