2024/09/26 AtCoderのC問題埋め
t6o_o6t.icon
やったこと
図を書いた
https://scrapbox.io/files/66f4ee1a4e2588001db786d5.png
わかったこと
問題への考察が誤っていた
総和も$ 10^8で割れば良いのなら、累積和の計算過程でつねに$ 10^8で割り続ければ正しいのだが..
今回は、各
次にやること
累積和を正しく計算する（s[i + 1] = s[i] + a[i]）
累積和を正しく取り出す
取り出したい区間を図示すると良さそう
やったこと
考察
全体をソートしたあと、低い金額から順番に見たとき、それが売り手なら売り手を1人増やし、買い手なら買い手を1人増やす。
わかったこと
考察できていない箇所があった
買い手のときは1足した値を出力しなければならない。
なぜ？
主要な想定解とは異なっていた
二分探索をする方法がある気はしていたが..
次にやること
解説の論理構造に着目する。
考察
DFSで、既に見た点に到達したとき、DFSの呼び出し元を遡り、帰りがけの点を記録していく。そして、記録した点のリストを逆順に出力する。
考察できていなかった箇所
すべての点から辺が1本だけ延びる。
あらゆる点から1本の辺が生えている。このことから、どの点とも繋がらずに存在している孤立したノードは存在しないことがわかる。
また、端となる点も存在しない。
必ず何かの点と繋がっており、端が存在しないことから、あらゆる点は何らかの閉路に接続しているといえる。
したがって、1番目の点から探索するように決め打ちしてもこの問題は解ける。
ただし、1番目の点が閉路内にあるとは限らない。辺がN本しか存在しないことから、N回移動すればかならず閉路内に到達できる。
以降は閉路をたどって記録すれば、この問題を解くことができる。
解説AC
（数週間前に解説を読んでいた）
考察
出力したい数を2で割ると、0, 1, 2, 3, 4で構成された数、すなわち5進数が得られる。
今回は2番目が1でなければならないので、Nから1減じて、5進数に変換し、2を乗じることで、出力したい数を得ることにした。
考察出来ていなかった箇所
一般的に進数変換のときはwhile(n > 0) n /= x;のようなループを書くことが多いが、
入力値がN=1のとき、Nから1減じるため、Nが0になる。このためループが一度も走らない。
N=1のときは0を出力しなければならないということを考察できていなかった。（本当はメモするのを忘れていた）
次にやること
必ず気になった箇所はすべてメモしておく。メモしたことは提出前に必ず確認しておく。
最小値の境界値チェックは必ずやっておく。
考察
全体の総和が変わらず、かつ全体の差を均すような操作をしているので、$ A_iは平均に近くなることが予想できる
ただし、最終的な$ A_iは平均そのものにはならない。なぜならば、平均は必ずしも整数値にはならないが、$ A_iは制約より必ず整数であるため。
例：$ A_n=(1, 6)のとき、最終的には$ A_n'=(3,4)となる。しかし、平均は3.5である。
初期状態：1, 6
1回目：2, 5
2回目：3, 4
$ \frac{\sum_{i=1}^N|A_i - \overline A|} 2が答えになるか？
平均が小数の場合、$ \overline Aについて切り捨てた場合と切り上げた場合それぞれで$ |A_i-\overline A|を計算して、小さい方を選択すれば良いだろう
総和が2の倍数にならない場合は..？
$ A_n=(1,8)のとき、平均は4.5
初期状態：1, 8
1回目：2, 7
2回目： 3, 6
3回目：4, 5
$ A_n=(1,7)のとき、平均は4
初期状態：1, 7
1回目：2, 6
2回目：3, 5
3回目：4, 4
次にやること
提出前に一度メモを読み返すことを忘れない。