振り返り【B問題】ABC378【灰】C++
Вставка
- Опубліковано 10 лют 2025
- 自分はどこで何を間違えていたのかを振り返る。
解説や他の方の振り返り動画を見ました。
数式だけだとわからない。
けれど、それ以前に何故その計算式の話になるのかがよく分からない。
こういう時は、自分自身の考えに何か間違いや勘違いがある。
問題を読み直し、図で考えながら修正。
正解かはわかりません(´・ω・`)イメージ
最初の問題文の文章を見て、なぜこの7日周期の中に余りの３が入るのか
これを問題文から導き出すだけの読解力は現在も獲得できていません。
図を何度か描きながら修正して【それっぽい】図を描いて
回答例のすべての条件が達成できるか？確認していきました。
現在のレベルでA・B問題合わせて30分で解けるようになるイメージは
まだ全く持てません(´・ω・`)
【AtCoder Beginner Contest 378】
atcoder.jp/con...
競技中の振り返り動画： • 【AtCoder】ABC378【灰】C++
アバター：nizima.com/Ite...
ボイスチェンジャー：www.roland.com...
歌唱曲 ――――――――――――
@otakara_BGM ： • 【フリーBGM / 歌あり】不屈の声【ガール...
BGM ―――――――――――――
なぐもりずの音楽室 ： / @nagumorizu
BGM えんぶらー ――――――――
the path of my life - mini album
bluembler.boot...
Ocean in Call - Embler 3rd album
bluembler.boot...
Eternity Ravine revelated Embler 1st album 完全版
bluembler.boot...
Embler
/ bluembler
つきこ
/ tsubaki_hachi
くーにゃん
/ maplevanilla30
rune
/ 0x0rune0x0
まめらー
/ mamera1129
Miu.
/ sr_miumiu
とーず
/ tomatoze_
乃葵
/ noa14236
Slushy
/ slusluslushy
www.foriio.com...
兎角Arle
arlequin.chiman...
A問題について、既に他の方の動画で振り返りをしていたら余計なお世話で申し訳ないです。
自分はまだ茶色コーダーなので、公式の解説放送やレッドコーダーの方の実況＆解説動画（おすすめは公式の解説放送見た上でこたつがめさん。どちらもUA-camにあがってる）があればそちらを見ることの方がおすすめですが、簡単に解説します。
A問題の制約で、A1～A4すべての入力が1以上4以下の整数とあります。そしてそれぞれの入力の回数を数えたいとき、基本的に（少なくともA,B問題ではだいたい）配列かmapを使います。前回の放送でWillowLogさんも配列を使用していましたが、少し使い方を変えることによってより楽に答えを求めることが出来ます。mapに関しては冗長になるので省略しますが、今回の問題についてはほぼ同じ形で使用できます。
vector a(5);
for(int i = 0; i < 4; i++){
int x;
cin >> x; (x--; を加えることで配列のサイズを4にすることもできる)
a.at(x)++; (a[x]++; でもよい)
}
こうやって数字が入力されるたび、配列の "入力した数字" 番目を＋１することで簡単に入力された回数を求めることが出来ます。この後は提出したコードと同様に、
for(int i = 1; i < 5; i++){
if(a.at(i)>=2) ans++;
if(a.at(i)>=4) ans++;
}
とすれば、答えを求めることが出来ます。
長文失礼しました。お互い精進頑張りましょう！
解説ありがとうございます‼️🙇🏻♂️
公式の解説まだかなぁと✅していたのですが、この時はまだ解説配信をされていない(見つけられない)ので、他の方のB問題は見に行ったのでA問題はまだ見ていません🥹現時点も
数学記号使ってる…とか思いながら見て、わかる様で分からなかったのでとりあえず自分の認識と、公式解説(記述)から確認しています💪😆💪
A問題、入力自体の数値を添え字？.at(x)にあてる発想はなかったので目から鱗がっ‼️
解説で別解として紹介されてなくて驚いたんですが、実はこの問題、
ans = (d-q-1-r)/q*q+r;
で、場合分けの必要なく一発で出ます。
この式だけ見ると意味不明だと思いますが、以下の3つの組み合わせです。
(1) d以下の数でdになるべく近いqの倍数を探す方法
ans = d/q*q;
(2) d「以下」じゃなくて「以上」で探してほしい場合
qで割る前にq-1を足してからやる
(3) qの倍数じゃなく、qで割ってr余る数を探したい場合
qで割る前にrを引き、qをかけた後にrを足す
今回は「d以上でdになるべく近い、qで割るとr余る数」が知りたいので、これら3つの合体技で計算できます。
この方法の欠点として、C++は負の数のint型割り算の仕様が数学的にバグっているので、C++で使う場合は負の数が関わらない確認が必要です。
今回はdがrより小さい可能性がありますが、q-1を足してれば負の数にはならないからセーフ！
今回は使いませんが、
(4) 以上か以下か問わないからqになるべく近いのを探してほしい場合
qで割る前に(q/2)を足してからやる
もセットでどうぞ！
最初の考え方は実は何も間違ってなくて競技中のイメージ図のq2が横に1つズレてるだけ……ってのは他の方も指摘してるので、私が深くつっこむ必要はなさそうですかねｗ
ば…場合分け⁉️ですか！
今は確認できませんが、帰ったら内容じっくり確認してみます😂
学習、投稿お疲れ様です！
お疲れ様です！😖🤯😖🤯
@WillowLog お仕事もがんばってね
すごいねー✨️✨️
よくこれ作ったね！！
頑張ってえらいよー👏
作る時間で何問過去問をやるたのか考えてしまいますが…何か掴めそうなので…ヨ…ヨシ…です😹
i tried math for B but i could not come up with a proper solution so i ended up using binary search in the end
Thank you for your comment!
At first, I thought a for loop would work. However, when I considered the constraints with a range up to 10^9, I realized it was impossible.
After the contest ended, I thought it might be solvable with binary search, but it seems that binary search didn’t work well either.
嗚呼！まだまだ分かってないですが🤒🤯
割り算の振る舞いがほんの少し掴めてきそうな…最後あたりの各質問の計算例から扱いが掴めてきそうな…きそうな…理解への…気付き…が…😖😵💫😵🤯溶ける…気が…🫠
考えやすい周期性のある問題の考え方、描き方を掴みたい
図は思考の助け…でも図だけでは割り算の振る舞いは掴めない🤯合わせてまた動画を見ながら振り返り…
これを書いてみて、問題Yで書いたプログラムにいろいろ入力してみると、割り算の振る舞いが見えやすいと思います。
また、問題Yに「100 7」を入力してみればABC378問題Bのゴミ出しルールと、公式解説の意味が理解しやすくなるかと思います。
問題X
整数aとbが与えられます。
「aの値」「q=a/bの値」「r=a%bの値」「b*q+rの値」
をスペース区切りで出力してください。
制約
0≦a
あ、1つ補足。
割り算のときにqっていう文字は通常「割った結果（quotient）」を表すのに用います。
でもABC378Bではなぜかqを「割る数」に使っていて、そのせいで若干話がややこしくなっています。
ABC378Bでいうqは、私の問題でいうbにあたります。
ans の様に、何かしらを表す変数名としてqは使われる事があるんですね😳
お疲れ様です。
どちらの考え方も正しいので、馴染む方で考えられればいいと思います。
「競技中のイメージ」でq2（クエリ5）が合わないのは、q1で最初に丸がついているのが「3のマス」なのに対して、q2では「2番目のマス」（=「1のマス」）だからですね。
あと0 ≤ r_i < q_iが表しているのは「Nで割ったときのあまりは0からN-1」ということだと思います（なので実際は0始まり）。
どちらも…正しい…‼️⁉️🤯正しい⁉️
割り算と余の…N-1の振る舞いが頭で分からないまま描いてると、よく分からないですが…
今回書いてみた質問5つ全体の計算から、使い方がつかめそうです…😖🤯😖🤯
競技中に質問5で計算合わなくなった原因分かったよー！
動画の一番最初に出てる分割イメージってやつでq1は最初の余り3を上の日付のメモリの3の値(０から4マス分)にしてるのにq2は余りの2を上のメモリの1の値(０から2マス分)にしてるのが原因。つまり、q2もq1と同じように上のメモリで余りの2の値(０から3マス分)にしてれば初めのやり方でも計算上手くいってたと思うよ！
仕事終わって改めて自分の動画を振り返ると…間違っています😱
図も数値も落ち着いて描きましょう…ですね😇
今、似た様な問題が出題されたら、苦しむ自信があります😼
直線でなく、円環で見るのもいいかも？
回収されるのは、ゴミ出しの今週か来週か？
円環何周か、という考え方！
考え方のバリエーションが増ですね！🎉
qで割ったあまりがrになるまで、日付に足すんですよね。
🥹図で書いだのを眺めて、どこでそれに気づけるか…問題がわからない時どういう視点で見るかを探してみます🥹