Відео

find、イテレータが帰ってくるんだよね。 あと、Bみたいなのは範囲外参照が怖いから、そういう部分は自分の中でこういうふうに書くのが良いって決めて、ほぼ暗記的に書くのが良いよね。将棋で言う定石みたいに、ほぼ頭使わなくても書けるように。

いろいろ難しく考えすぎたようですね B問題の読み落とし私もです。そのせいで時間がかかってしまったW A問題、８方向の図を書いた時点で、WillowLogさんのACコードのように愚直に書けばもっと早く回答できたと思う find()を使おうとしたことが悔やまれる あと、２つのベクタを使う場合でも、よくわかってないfind()を使わず、 for文で回して、一致したら解を出力して終わるか抜ければよいので、混乱せずに済んだと思う B問題、SのシートにTのシートを重ねて、パターンが同じにできるならYesという感じのイメージで Sの各マス(N*Nマス)全てについて、判定する Sの(a,b) のマスをTの左上角(i,j)=(0,0)のマスとしてM*Mマス調べて 全マス同じならtrue、１つでも異なればfalse ４重ループの混乱を避けるため、判定という大きな一塊の処理を関数にして簡素化する 以下にコード書いときます 範囲外参照対策に公式のコードでは、a,bの範囲に工夫がありますが 以下のコードは工夫はせずに、判定時に範囲外参照をfalseとして返してます ```cpp // おまじないとrepマクロを追加 int N, M; string S[50], T[50]; bool same(int a, int b) { // S[a][b] を左上角として T と同じか判定 rep(i, M) rep(j, M) { int k = a + i; // S の index int l = b + j; if (N <= k) return false; // 範囲外 if (N <= l) return false; // 範囲外 if (S[k][l] != T[i][j]) return false; // 同じでない } return true; } int main() { cin >> N >> M; rep(i, N) cin >> S[i]; rep(i, M) cin >> T[i]; rep(a, N) rep(b, N) if (same(a, b)) { cout << a + 1 << ' ' << b + 1 << endl; return 0; } } ```

ありゃ、B解けませんでしたか。 ざっと飛ばし飛ばしで画面に見えたものから判断するに、無駄に難しい方向に突っ込んで行きましたかね？ AHCは、最低限AC可能（ただし超低得点）なサンプルコードは問題に掲載されているので、それをほんのちょびっと改良するだけとかでも参加できます。 ABCとは競技の方向性がかなり違っていて、楽しいですよ。

B問題ですが、誤差の出ない有理数ライブラリを使うという方法もあります。 前提として、有理数ライブラリの使い方を知っている必要がありますが… 実際にboostの有理数ライブラリを使った回答例がこちらになります。 abc390/submissions/62120667

今回は難しかった...単純なforや出力だけで解ける問題がなかった。 ひとひねりしないと回答できない... 自分はABまでしか解けませんでした... あと、タイトルがABC389ですよ

B問題「前割る後ろが常に同じ」という結論に至れたのいいですね A問題、実際にやる方法が取れるとよかったですね。 「配列の要素を入れ換える」 →「チェックする」 →「もとに戻す(最初と同じ場所を入れ換える」 入れ換える候補はi番目とi + 1番目になるから、計4回これをする感じです。 配列の要素を入れ換える関数の使い方(もしくは作り方)は調べれば出るので、知らない場合は調べていきましょう。 ちなみに、他の方が言っているBの式変形は紙に式を書きながら確認してみると納得が出来ると思います。 たとえば、「2,4 ,8,16」や「200,100,50,25」のような等比数列、「2,3,4,5」のような等比数列でないパターンで書いて見ると納得できるはずです。 B問題で出てくる、 x/y = a/bを 意味の等しい x * b = a * y に変える工夫は便利なので、「少数やだなあ」と思ったときに思い出しましょう

式変形になれるために、中学一年生の数学の教科書などからはじめてみてはいかがでしょうか？ willowlogさんの動画は時々拝見しますが、数式へのアレルギーみたいなものをめっちゃ感じます。 A問題、B問題で使うような式変形は中学一年生の最初の単元ができるようになるだけでもとても分かりやすくなるので試して見てくださいね！

A問題、肝心な一行抜けてて沼てっしまったW WillowLog さんが提出されたコードでWAとなるケース書いときます i:1 2 3 4 5 A:5 2 3 4 1 ans=No これが Yes になってWA iとA[i]を比較すると、隣り合ってなくてもcountしてしまう！ あくまで隣と比べないとダメ A問題考えてるとき、swapを口にしてて惜しい！ 隣り合う組は(a1,a2)(a2,a3)(a3,a4)(a4,a5)だから これらを入れ替えたら[1,2,3,4,5]になるか判定すればいい！ B問題、公比が実数になるパターン忘れてて、入力例３で？ってなったｗ 入力例２の説明のとこみて、判定方法に気がついて通した 数学の問題だから、前提知識が必要 a:b=c:d とか書いてるのは比を表していて、a対bはc対dと比(割合)が同じということ このとき a/b=c/d と式にできる このままでは実数になってしまうので a*d=c*b と式変形して判定に使う 等比数列では A[2]:A[1]==A[i+1]:A[i] となれば A[2],A[1] と A[i+1],A[i] の比は同じ これが全ての i と i+1 に言えれば等比数列と言える このとき A[2]/A[1] が等比数列の公比 r になっているはず A[2]:A[1]==A[i+1]:A[i] これは A[2]/A[1]==A[i+1]/A[i] と書け A[2]*A[i]==A[i+1]*A[1] と式変形できるのでこれで判定 あとは i+1 を範囲外にならないよう気をつければよい って感じでやりました 実数で処理すると誤差でやられるので、式変形で逃げるのはあるある！

A[i+1]/A[i] = A[i+2]/A[i+1] から A[i+1]の2乗 = A[i] * A[i+2] に変形される部分 左の式の両辺にA[i] * A[i+1]を掛けると右の式になります。

お疲れ様でした。 今回難しかったですよね。 B問題が、「double型の欠点を知ってないといけない」+「その回避には等比中項という話をしらないといけない」のコンボでwillowさんにはちょっと厳しかったかもしれませんね。 Aは、油断で足を掬われましたかね？ そして、C問題がグリッド問題だったので、willowさんには一番楽だった説。

聞いてー✨️✨️ 入茶しましたー🤎🤎🤎 やったー✨️✨️✨️

あー、残念。というか今回は難しかったですよね。 私もA問題とB問題で1回ずつWAしてしまいました。 A問題：問題文に「隣り合う 2 つの項」とあるのに「隣り合う」を見落としていた。入力が "2 1 3 4 5","1 3 2 4 5","1 2 4 3 5","1 2 3 5 4"のうちいずれかであればYes、そうでないならNoでした。 B問題：前項で割り算して答えがすべて同じならYesだと思っていたら除算に伴う誤差でWA。これはWAしたときに気づいた。B問題にしては難しくないか？ C問題：これは普通にできた。 D問題以降、まるで歯が立たず・・・でした。 お互いがんばりましょう。

お疲れ様です！ Tは3文字。T = C1C2C3とする。 C1,C2,C3の小文字をそれぞれc1,c2,c3とする。 (i) C3 == 'X'の場合 c1,c2がこの順でSに含まれているならばtrue (ii) C3 != 'X'の場合 c1,c2,c3がこの順でSに含まれているならばtrue 文字列Sを先頭から1文字ずつ走査していって、文字c1と合致するか判定する。 合致すれば、照らし合わせる文字をc2にする。

おつかれさまでした。序盤でsetの沼に入ってしまったのが敗因でした。

いろいろ迷子になったり変な道を爆走したりしていたようなので、アシストっぽい内容をいろいろ。 4:20 素晴らしいとこその1。 自分ができない問題を、きっとできないとわかっていても挑戦するって、意外と難しいんですよね。 一番成長につながることだとわかっていても、どうしても腰が重くなる……。 それをこんなにも当然にこなせるwillowさんの心の持ち方を、私含めみんな見習うべきですね、本当に。 17:15 悩んでたとこその1。 部分列は、「適当にいくつかの文字に印をつけて、それらの文字だけ前から読む」くらいのイメージがわかりやすいでしょうか。 定義で間隔についての言及がないというのは、間隔についてはどんな様子でも構わないということです。 今回の問題をわかりやすく言い換えれば、 「Sの文字列の中で3つの文字に印をつけて、それらを左から順に読んで大文字化することでTに一致するものを作れますか？あるいは（以下略）」 という問題だったわけですね。 部分列の例もいくつか挙げておくと、 “willow” の部分列には “wil” とか “iw” とか “willw” とか “o” とか “ww” があります。 定義上、全部印をつけた “willow” と、印を1つもつけない “” も部分列です。 元々ない文字を含んでいる “wa” や、元々の個数を超えている “www” や、順番を変えないとできない “wlwl” などは部分列ではありません。 n文字の中の部分列を全探索すると、個数の制限がなければ O(2^n)、r文字の部分列に限るなら O(n^r)。 いずれの場合でも単純に全探索すると計算量が爆発しがち。 今回はr=3なので、部分列を全部作ってみるのはO(n^3)になって御陀仏です。 28:30 悩んでたとこその2。 vector<char>はおそらく使いどころがないです。 少なくとも私は、水色昇格までに一度も使ったことがないです。 vector<char>でできる処理はおそらく全部stringでもできるので、わざわざ下位互換を使う理由が……。 31:25 やらかしその1。 重複がなくなっちゃうのはダメですね。 同じ文字が2回目や3回目に出てきたところを使う必要があるかもしれないからです。 例えば “willow” に対して “ILL” や “IOW” が空港コードの条件を満たすかどうかは、どちらも正しくはYesですが、重複を消すと誤ってNoとしてしまいます。 今回のWAの大半はこれが原因じゃないかな？ 36:20 やらかしその2。 unordered_set はソートしない、の意味を誤解していますね。 ソートしないというのは、順番に関する作業と保証を全て放棄するという意味です。 C++くんの気まぐれ順に並べられると言い換えてもいいと思います。 willowさんの手元のC++くんは完全な逆順にしがちだったようですが、AtCoderの方でも同じ挙動になるかどうかは不明です。 1:53:13 素晴らしいとこその2。 10^5が、1重ループは回せても2重ループは回せないという感覚を持っているのはすばらしいですね。 まだTLEと戦った経験量が少ないうちからその感覚を持てるなら、3完常連もそんなに遠くないかもしれませんね。 今回も、目の前にぶら下がってる超単純な3重ループを最初からスルーしてますけど、灰色でそれできる人はそう多くないと思います。 2:06:00 悩んでた（？）とこその3。 差分の吸収だけが目的なので、大文字に揃えても小文字に揃えてもいいです。 短い分Tを小文字にする方がいいと考えられたのはセンスあり。

「お！これ簡単そう」ってことで、サクッとコードを提出して WA でしたW 雑すぎる～ 公式解説のpythonのコードcppで書いてみました ```cpp 先頭のおまじない追加してください using namespace std; bool check(string S, string T){ int n = size(S); int pos = 0; // S の検索位置 for(auto t: T){ t -= 'A' - 'a'; // 大文字と小文字の差分から、大文字を小文字に変換 while (pos < n && S[pos] != t) pos++; // t と同じ字が見つかるまで前進 if(pos == n) return false; // 途中で尽きた pos++; // 見つかった位置の次から、次の t を見つける } return true; // 全部探せた } int main(){ string S,T; cin>>S>>T; if (T[2] == 'X') T.pop_back(); // 3文字目が X なら、判定の必要がないので if(check(S,T)){ puts("Yes"); }else{ puts("No"); } } ```

おつかれさまです！ そういえばこのチャンネルで貪欲法って登場したことなかったですね。 BFSとか尺取法なんかよりずっと前に習得すべきものな気がしますがｗ 貪欲法の解説、いります？

WillowLog さんの思い描いた処理を再帰で実装すると、こちらのようになると思います(解説のコードをベースに作成)。 abc384/submissions/61882926 ポイントは、名前と点数を再帰関数の引数にすることと、結果をグローバル変数に push_back することです(結果を戻り値で返すのは大変なので)。

C問題は知っているかどうかの知識問題でしたね。

視聴後に改めて気付いた点をコメント A問題 1:50:51 willowさん「char型をint型に変更して……」 コードくん「char型に変更して……」 実は、int型変数にデータを格納する時に型が違ったら自動的にcastしてくれるので、自分が手を動かして型変換の指示をする必要はなかったり。 ここで型の変換先を間違えたのも、こっそりその機能に救われてますね。 B問題 32:29 デバッグログ表示コードのcerrに吐き出すところに手を入れて、デバッグログはデバッグログと自分で区別できるようにしておいた方がいいかもしれませんね。 あるいは、chromeのプラグインを導入して、入力例を自動でテストしてから提出してくれるようにするとか。 1:55:16 21!以降は、Xの値の制約に入り切らないんです。 階乗はビックリするくらい一気に値が増えるので。 とはいえ、具体的に20が限界とはわからなくても「まあ100は行かんやろ」でwhile文回す作戦も十分あり……というか、多分そっちが多数派じゃないかと思います。 C問題 1:26:12 入力例2に惑わされちゃいましたね。 出力がないケースがある→coutをするかしないかを何かで判定しないと！ と思ってしまったのでしょうが、実はそんな必要はありません。 ただ出力を求めるクエリが一度も来なければ何も出力せずに終わりますが、それが正常動作ってことで間違いありませんよと言ってるだけなので……。 勉強法の話 chatGPTはあくまで自然な文章を創作してくれるAIであって、正しい情報を伝えてくれるAIではないですからね。 関連する（可能性が高い）キーワードを出してもらう、くらいまでにとどめた方がいいかもしれませんね。 自分の理解が正しいかどうかは、それを使う簡単めな問題に自力ACできるかで確認してみるのがいいと思います。 理解が間違ってるのにACはできるなんてことは滅多に起こりませんし、実際に使ってみる練習にもなりますし。 まあ、解いたことがない問題だけどそれを使うことがわかっている問題ってのを探してくるのが難しいんですけどね。 Aizu Online Judge だと使う技法をタイトルにしてくれてる問題集があるので、そういう勉強には向いてます（私もそれでやりました/今でもやってます）。 ただ、問題ごとの難易度がよく分からないのと、サイト自体がちょっと使いにくいのがなあ……。

B問題、O(N) 相当のコードでAC！おみごと！ 自分は、O(N^2) 相当のコードで通してましたｗ ansを出力せずに提出してたのは残念！もったいない！ C問題、おしいね！ k番目のヘビの頭 -> k-1番目のヘビの尾 と言い換えればまとめやすかったかな？ 尾の座標はヘビの長さの総和だからね 先頭から削除しないとすると、 ヘビを追加する度にそこまでの長さの総和を計算しておけば、 k番目のヘビの頭の座標 = k-1番目のヘビの尾の座標 = k-1番までの長さの総和 で簡単に求められる そこから、削除を考えると、 ベクタから先頭を削除するのが時間的に厳しいので ”どこまで”いらないか（どこまで放したことになっているのか）を持っておいて、 差分から解を計算する で、なんだ累積和を使った範囲和か！ってなる って感じかな？ 累積和は最初にベクタに 0 を入れといて、1 番目から追加するようにしておくと いろいろ嬉しいことがあるよ！ まぁ、終わってから考えをまとめるのは簡単だけど、 コンテスト中は、私も結構時間かかってとおしたからねｗ ちなみに、queueでは厳しそうだけどdequeueだと意外と簡単に実装できたりする これも、コンテスト中は思いつかずに普通にベクタで実装したけどねｗ

おつかれさまです！ 2完はもう余裕ですね！ 動画待ちの間にwillowさんの提出結果を見てましたが、C問題、おしかったですね。 queueっぽく見せかけてvectorを使わなきゃいけない、までは正しい方向に進んでいました。 あとは、「vectorのここからここまでの和を出して」を大量に処理しなきゃいけないときに使う「累積和」というテクニックさえ知っていればワンチャン3完でした。 明日にでも、累積和の勉強をしながらAC目指せるところに充分たどり着いていると思います。 ぜひ頑張ってみてください！ 以下、自語り。 E問題（正解者566人）を解いて5完だったのに、それより簡単なF問題（正解者998人）が間に合わなかったせいでABCDFの5完の人より順位が下なの納得いかねえ……。

自分の未知のものをChatGPTに聞くのは真偽の判別が出来ないので危険ですね

イテレータはポインタ"のようなもの" -> ポインタ(メモリのアドレス)ではない！ 配列は全てをメモリ上にまとめて配置されるので、ポインタで管理できる。 ベクタは要素の追加を容易にするため、その全てがメモリ上にまとまって配置されるとは限らない。 イテレータは、あたかもポインタのように要素が並んでいるかのように扱えるようにする仕組みで、 使っている側からはポインタとの違いを意識せずにすむ。 って感じで覚えてるんだけど？ホントのところは本職に任せるｗ あと lower_bound と upper_bound の違いは以下のような感じで覚えてる また幅がズレてるので、エディタにコピって確認してほしい ```cpp int main() { // index: 0 1 2 3 4 5 6 vector<int> A = {1, 2, 3, 3, 3, 4, 5}; // l u <- 挿入したい位置 // ↓処理単位で {} で囲めば、その中の変数宣言は {} の外からは見えない // 例えば (1) と (2) で it を変数宣言してもお互いは知らん顔で問題なし { // (1) // 3 を挿入するとしたら、どこへ挿入するか？を返す // ただし, 同じ値があれば一番左に挿入したい // auto it = lower_bound(begin(A), end(A), 3); auto it = ranges::lower_bound(A, 3); if (it != end(A)){ // int index = distance(begin(A), it); int index = it - begin(A); cout << index << " "; // 2 cout << *it << " "; // 3 } } { // (2) // 3 を挿入するとしたら、どこへ挿入するか？を返す // ただし, 同じ値があれば一番右に挿入したい // auto it = upper_bound(begin(A), end(A), 3); auto it = ranges::upper_bound(A, 3); if (it != end(A)){ // int index = distance(begin(A), it); int index = it - begin(A); cout << index << " "; // 5 cout << *it << " "; // 4 } } } ```

とりあえず尺取り法まとめ部分を拝見。 今度は正しく理解できていると思います！ （倍数は2倍の数という意味ではないことを除けば） 私の提出コードはwillowさんと同じく上の餅ベースで考えて尺取り法をしてたので、そっちを使ってくださればご自身のコードと比較しやすかったでしょうにｗ

コンテストおつかれさまでした！ C問題、問題の引っ掛けや読み落としもなく、チェックできてましたね RLEに方針が流れてしまったのが残念 公式のしゃくとり法でも解けるの文言から、コード考えて見たけど... 私も「これもしゃくとり法？」ってなりました（公式とほぼ同じコードになったんでですけどねｗ） WillowLogさんの提出見させてもらいました C問題、ACとれてましたね！ しゃくとり法で提出したコードについては、j のループを毎回 i+1 から始めるときつそう O(N^2) かな？ ループの外で j=0 にして、毎回更新後の j から始めれば、それだけでいけるのでは？ ```cpp int j=0; for(int i = 0; i < n-1; ++i){ for( ; j < n; ++j){ ... ``` あと、TLEの件って、もしかしてデバッグを吐き出しまくってた？ 使ったことないから挙動を知らないんでわからないけどｗ

willowさんの尺取法の理解がちょっと違うので、二分探索もあわせて探索法を簡単に解説しますね。 willowさんの方針に合わせて、それぞれの餅が何個の餅の上に載せられるかを数えて合計する方針で考えます。 今回、下の餅は大きすぎて困ることはないので、「この餅はOKだけど1つ手前の餅はNG」という餅を見つければ、載せられる餅の個数はすぐにわかります。 この「この餅はOKだけど1つ手前の餅はNG」という餅を、以下「ギリOK餅」と呼ぶことにします。 (1) 線形探索 0番の餅を載せられるかどうか、0番から順に試します。 最初に載せられたやつが、ギリOK餅です。 1番の餅を載せられるかどうか、0番から順に試します。 最初に載せられたやつが、ギリOK餅です。 以下、n-1番までギリOK餅を探します。 理屈の上では正しく答えが出ますが、試しに載せてみる行為の回数がとても多いです。 餅が100個なら1万回、1万個なら1億回、50万個なら250億回の試し乗せが必要です。 実行時間はO(n^2)で、間に合いません。 (2) ちょっと工夫した線形探索（willowさんが尺取法と誤解していたやつ） 自分より大きい餅以外は載せてみる必要がないので、スタート地点を工夫します。 0番の餅を載せられるかどうか、1番から順に試します。 最初に載せられたやつが、ギリOK餅です。 1番の餅を載せられるかどうか、2番から順に試します。 最初に載せられたやつが、ギリOK餅です。 以下、n-1番までギリOK餅を探します。 工夫なしよりは半分に減っていますが、TLE対策では半分ごときじゃ焼け石に水です。 餅が100個なら約5000回、1万個なら約5000万回、50万個なら約125億回の試し乗せが必要です。 これでも実行時間はO(n^2)で、間に合いません。 (3) 二分探索 ギリOK餅を探す方法を工夫しましょう。 何も、馬鹿正直に前から順番に探す必要はありません。 最初にいきなり、真ん中の餅に載せられるか試します。 載せられるならギリOK餅はそれより左に、載せられないならギリOK餅はそれより右にあることがわかります。 次に、可能性がある範囲の真ん中の餅に載せられるか試します。 載せられるならギリOK餅はそれより左に、載せられないならギリOK餅はそれより右にあることがわかります。 このように繰り返すと、線形探索よりはるかに早くギリOK餅を見つけられます。 （例えば餅が7個の場合で試すと、餅1個あたり3回で見つけられることがわかりやすいと思います） lower_bound()を使うのもいいですし、時間無制限なら何かを参考に見ながら自力で一度書いてみるのもいい勉強になります。 試し載せの回数は、餅が100個なら700回（1個あたり7回）、1万個なら13万回（1個あたり13回）、50万個なら950万回（1個あたり19回）です。 実行時間はO(n*logn)で、今回の制限なら余裕で間に合います。 （willowさんの3回目の提出が2回目よりたくさんTLEしてるのは、おそらく二分探索とは別の何かのせい） (4) 尺取法 0番の餅を載せられるかどうか、0番から順に試します。 最初に載せられたやつが、ギリOK餅です。 ここまでは線形探索と同じですが、次が尺取法のポイントです。 1番の餅を載せられるかどうか、「0番に対するギリOK餅」から順に試します。 最初に載せられたやつが、ギリOK餅です。 以下、n-1番までギリOK餅を探します。 上の餅がさっきより大きいのに、ギリOK餅がさっきより小さくなることはありません。 それを利用してjを再初期化せずに前回のゴール地点から探索を続けることで、爆速で探索できます。 （iとjがどこを見ているか、その変化をお絵描きすると、iとjの間が尺取り虫のように伸びたり縮んだりする様子がよくわかると思います） 試し載せの回数は、餅が100個なら200回、1万個なら2万回、50万個なら100万回です。 実行時間はO(n)で、今回の問題ではおそらく最速です。 二分探索の練習問題は、他の方が挙げていたのでそちらを。 尺取法の練習問題は、ABC326Cとかがいいですかね。 二分探索でも解けちゃいますが。 （というか、尺取法の問題のうち二分探索で代用できないやつは高難度なものしかないので、二分探索を先に身につけた方がいいという話も）

2分探索のコードがTLEとなった原因は、コードの先頭の以下の文です。 #define _GLIBCXX_DEBUG // 空のコンテナに対する操作した場合実行エラーを出す こちらを入れると実行が遅くなるので、削除することをお勧めします。 (vectorの要素アクセスにvector::at()を使うのであれば、こちらを入れる必要はありません)

お疲れ様です！ 【C問題】abc388/submissions/61563992 lower_boundを使って解きました。 （upper_boundは1ミリも思い浮かびませんでした） 答えが見つからない場合が怖かったので、両端に番兵を置きました。 lower_boundって最初不思議ですよね。 - X.begin()をしないとイテレータが返ってくるところが。 // index、添字 int l = lower_bound(X.begin(), X.end(), left) - X.begin(); int r = upper_bound(X.begin(), X.end(), right) - X.begin(); // イテレータ auto l = lower_bound(X.begin(), X.end(), left); auto r = upper_bound(X.begin(), X.end(), right); 【類題】鉄則A11、鉄則B11、ABC231C

初４完できたー！！ やったー✨️✨️✨️💕💕💕

おつかれさまです！ 2完するまでの時間もだいぶ短くなりましたね！ そろそろ問題の中身次第で初の3完も期待できそう。 C問題のしゃくとり虫くんの参考コードどうぞ abc388/submissions/61568626

修正前のソースで、具体的に問題が起こるケースを追いたいなら、以下の入力例はいかがでしょうか。 3 1 . S G こんな感じで動作するのが分かるかと思います。 ・最初にqueUDに(1,0)が登録される ・queUDの先頭(1,0)を処理して、queLRに(2,0)と(0,0)が登録される(queUDは空になる) ・queUDが空なので、stateを0から1にする ・queLRの先頭(2,0)を処理するが、左右とも壁なのでqueUDに値が入らない ・queUDが空なので、stateを1から0にする ←ここが問題 ・queLRに(0,0)が登録されていて空ではないので、ループ先頭に戻る ・stateが0なので、queUDの先頭を処理しようとするが、queUDが空なのでエラーで落ちる 念のため、私が修正してACとなったソースを載せておきます。 abc387/submissions/61407187

D問題、ACおめでとう！しかも queue 2本を連携するとは！この発想はなかった。むずかしい！ 例によって、脳筋コード書いときますｗ 公式解説のように、市松模様の i+j の偶奇とか、距離の偶奇で、上下｜左右を指定するかわりに 最初だけ、上下｜左右どちらへ移動するか指定し、以降、上下｜左右を交互に指定するようにしました ```cpp // いつものおまじない追加してください int H, W; // bfs の引数手抜きのため global におく string S[1000]; int INF = 1e9; int sh, sw; // 開始位置 int gh, gw; // 終了位置 vector<vector<pair<int, int>>> dirs{ {{-1, 0}, {1, 0}}, // dirs[0]: 上下に移動 {{0, -1}, {0, 1}} // dirs[1]: 左右に移動 }; int bfs(int si) { // si: 開始位置から 上下|左右 どちらに移動するか vector dists(H, vector<int>(W, INF)); // 距離を初期設定 dists[sh][sw] = 0; // 開始位置の距離 queue<tuple<int, int, int>> que({{sh, sw, si}}); // 開始位置の情報を初期設定 while (size(que)) { // 終了位置に未達の場合, que が空になり抜ける. 未達 -> 終了位置の距離 INF // h,w: 移動元の位置 // i: dirs を選択し, 移動元から 上下|左右 どちらに移動か決めるため // 距離が +1 する毎に 0|1 (上下|左右) が入れ替わるようにする auto [h, w, i] = que.front(); // 移動元の情報取得 que.pop(); // 移動元の情報削除 if (S[h][w] == 'G') break; // 終了位置で抜ける int next_dist = dists[h][w] + 1; // 移動先までの距離 int ni = 1 - i; // i=0 -> ni=1, i=1 -> ni=0, 移動先から 上下|左右 どちらに移動か for (auto [dh, dw] : dirs[i]) { // dirs[0]: 上下, dirs[1]: 左右 int nh = h + dh, nw = w + dw; // nh,nw: 次の位置 if (!(0 <= nh && nh < H && 0 <= nw && nw < W)) continue; // 範囲外 if (S[nh][nw] == '#') continue; // 障害物 if (dists[nh][nw] <= next_dist) continue; // すでに next_dist 以下で訪問可能 -> 再訪問不要 dists[nh][nw] = next_dist; // 移動先 までの距離を記録 que.emplace(nh, nw, ni); // 移動先の情報を追加 } } return dists[gh][gw]; // 終了位置までの距離を返す } int main() { cin >> H >> W; for (int i = 0; i < H; i++) cin >> S[i]; for (int h = 0; h < H; h++) // 開始位置 (sh,sw), 終了位置 (gh,gw) を取得 for (int w = 0; w < W; w++) { if (S[h][w] == 'S') sh = h, sw = w; if (S[h][w] == 'G') gh = h, gw = w; } int dist = min(bfs(0), bfs(1)); // bfs(0): 開始位置から上下に移動, bfs(1): 開始位置から左右に移動 cout << (dist != INF ? dist : -1) << endl; } ```

おお、ACおめでとうございます！ queue2つを交互に使う難しい方で完走するとは。 これができるなら、次にグリッドで「最短距離を求めなさい」が来たら本番中のACも狙えそうですね！ あとは「ゴールできるかどうか」もいけるかな？（これはBFSでもDFSでもどっちでもいい） 一応、当日挑戦でのコードで、「この辺あやしいぞ？」って思った箇所を2点挙げておきます。 1つめ、未探索マスかどうかのチェックにkashikaの中身を調べているように見えます。 で、このkashikaをきちんと管理できていれば多分問題ないんですが、ここについでに距離を数字として表示しようとしていたのが悪さをしているように見えます。 というのは、距離が10以上だと、文字数が増えるせいで迷路の壁が全部ずれると思うんですよね。 最後に走らせたときに、10を超えて初めて右移動しようとしたところでバグっていたのは、これが原因じゃないかと思います。 というか、そもそも、探索済かどうかは距離が1e9かどうかを見ることで話が済んでいるので、kashikaをチェックすることに意味はありません……。 2つめ、モード切り替えのif文の中身が怪しそうに見えます。 横方向のqueueが空になっていたら、というif文を縦モードのときもチェックしてませんかね？ これにより、 横queueが空になったので縦モードになりました！ →縦モードのqueueの先頭は上下とも調査不要でした！横queueには何も追加しません！ →横queueが空なのでモード切り替えをします！ →縦queueの中身が残ってるのに横モード開始 という動作をするように見えます。 横queueが空なので、何もせずにまた縦モードに戻って表面的にはバグらなさそうな気もしますが、本当にそうなのかは自信はありません。 何にせよ、このモード切り替えみたいなことをするときは、以下の2つをした方がいいのかなと思います。 今回なら、少なくともどっちかがやってあれば何も問題はなくなるはずです（もちろん両方やるのが最も安全）。 if(今0番モードかどうか&&0番モードから1番モードに切り替える条件) のように、現在のモードと切り替え条件の両方を確認する。 モード変更を、bit反転ではなく「0番にする」「1番にする」と明示的に書く。

あけましておめでとうございます C問題をサクッとパスして、D問題にかかったのは懸命だったね！ 私は、C問題に執着して、結局解けなかったよｗ コンテスト後に、D問題みたら、方針すぐに決まって、ちょっと時間かかったけど解けたよ。もったいない！ 解けない問題に執着するクセ直さないとねｗ

あけましておめでとうございます。

This time, the level for C was way higher than B (id say it was higher than D was well). To solve C you either need to be familiar with math (combinatorics) or used to Dynamic Programming (Digit DP to be precise) problems to solve it. DP is a fairly complicated topic so i was surprised seeing it used in problem C. For D, graph traversal algorithms for shortest distance (BFS, Dijkstras) can help, but you also need to remember the last direction in which you moved (left / right or up / down), so the next step can be in the opposite axis. Good luck with the practice!

新年初のABCは2025とヘビの問題が多かったですね。D問題はできたけどC問題ができず・・・それでも過去最高のパフォーマンス1129（レーティングは632）を叩き出すことができました。茶色コーダーの自分語り失礼しました。

お疲れ様です！たぶんD問題の８合目ぐらいまで来てると思います。movesのあたりは、上下移動か左右移動を表現していると思います。

そうそう、DFSをやりたいなら、グリッドじゃないですがABC213Dが典型問題ですのでぜひ。 ただ、先にグラフ理論の基礎的なことをやらないと厳しいかも……？

あけましておめでとうございます！ C問題、難しかったですねえ。 willowさんのランクだと、ABの早解き勝負になってたでしょうね。 こっちも、AB合わせて3分、Dに5分、Cに85分かかりました、危なかった……。 D問題見た瞬間、「willowさんがC飛ばしてDやることに気づけばワンチャン！？」と思ったのですが、流石に難しかったですか。 ちょっとグリッドBFSのコード内に手を入れないといけないので、 ・グリッドBFSの仕組みをしっかり理解している ・問題に合わせた実装変更をできる力がある の両方必要で厳しかったですかね。 多分willowさんにとって一番簡単なのは、以下かなと思いますので、再挑戦でぜひ。 ・queueに次を追加するときに、現地点のスタートからの距離が偶数なら横移動のみ、奇数なら縦移動のみを追加するパターンをやる ・偶数奇数逆にしたパターンもやる 関数に0か1を渡せるようにして、「距離+渡された値」の偶奇で挙動を切り替えるようにすると実装しやすいかなと思います。 別解： 迷路を2回建てにして、1階からは横の隣マスの2階に行ける、2階からは縦の隣マスの1階に行ける、というルールでスタート2ヶ所（1階と2階）の3次元グリッドBFSをする。 手元に持ってたBFSのコード次第ではこっちで一瞬。

良いお年を✨

応援しています。

今回、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問題で出題されているので、それは取り組んでもいいかも。 ダブリング　不要。