2022-09-04

NECプログラミングコンテスト2022 (AtCoder Beginner Contest 267)

競技プログラミング

NEC プログラミングコンテスト2022 (AtCoder Beginner Contest 267)に参加しました。

結果

A,B,C,Dの4問正解でした。

A,B問題は聞かれていることは簡単だけど実装が面倒な問題だった印象。

Cはいつもよりちょっと難しかった？ちゃんと考えたら最初に思ってたよりは簡単だったけど。

D問題はいつも通りDPの問題だった。DPは慣れてきたから頭で漸化式立てて実装してたけどちょっと失敗だった。何回かWAしたから手計算して、落ち着いて漸化式を整理したらすぐに解けた。

CとD問題でちょっと時間を使いすぎてWAを出しすぎた。

A - Saturday

問題文の通り実装する問題。

何曜日かを英語で入力されるから土曜日まで何日かを出力する問題。 switch文で処理するのが一番スッキリすると思う。C++のswitch文どうだっけと数瞬迷ったので、調べる手間を惜しんでif文のコピペで実装した。

曜日の英語は問題文からコピペしてきたけど、1箇所半角スペースもついてきたのに気づかなかったせいで１WA。ちょっともったいない。

文字列の内容比較とか条件分岐とかができるかを聞いている問題なのかなと思う。

B - Split?

ボウリングのピンがスプリットになっているかどうかを答える問題。

聞かれていることは割りと単純だけど実装が面倒くさかった。
どのピンが同じ列かは問題文で示されているから、列ごとに全部のピンが倒れているかどうかを確認して、
ピンが残っている　－　ピンが全部倒れている　が1列以上連続している　－　ピンが残っている
という状態になっているかどうかを確認して答えた。列の数も7列だけなので3重ループで確認した。

ちゃんと考察したらもう少し簡単で賢い実装方法があるのかなあと思いながら解いた。

C - Index × A(Continuous ver.)

いつものC問題よりは難しい気がした。（いつもなら問題文読むとすぐに解き方が思いつくけど今回はちょっと悩んだから）

数列Aから連続した項を連続部分数列Bとして取り出して $i \times B _ {i}$ を計算して最大値を答える問題（Bの項数は指定されている）。ぱっと問題を読むと連続部分列の開始位置 $A _ {i}$ が動くと全部計算し直さないとなあと思いつつ、そんな事すると計算量が $O(N ^ {2})$ になってTLEになると予想できるのでどうやって解こうかなと考えた。

$A _ {i}$ を開始位置として数列Bを作ったとすると数列Bの和は $1 \times A _ {i} + 2 \times A _ {i+1}+・・・+M \times A _ {i+M-1}$ になる。これをもとに $A _ {i+1}$ を開始意図したときの数列B和を計算することは可能で、 $A _ {i}$ から $A _ {i+M-1}$ までの和を引きつつ $M \times A _ {i+M}$ を足せば求められる。

例えばM=3の時 $A _ {i}$ を開始位置とした時の和は
$A _ {i} ＋ A _ {i+1}＋ A _ {i+1}＋ A _ {i+2}＋ A _ {i+2}＋ A _ {i+2}$
となるが、開始位置が1ずれて $A _ {i+1}$ を開始位置とした時の和は
$A _ {i+1} ＋A _ {i+2}＋ A _ {i+2}＋ A _ {i+3}＋ A _ {i+3}＋ A _ {i+3}$ となる。この2つの和の差は $A _ {i}、A _ {i+1}、A _ {i+2}$ が1つずつ減っていて、 $A _ {i+3}$ が3個増えている。

一般化すると、 $A _ {i}$ を開始位置とした時の数列Bの和が求まっているときに、 $A _ {i+1}$ を開始位置とした数列Bの和を求めるには $A _ {i}$ から $A _ {i+M-1}$ の和を減らして、M $\times A _ {i+M}$ を足せば求められることになる。

累積和と $A _ {1}$ を開始位置としたときの和を求めておけば、ループ1回で全通り分の和を計算できる。あとは計算しながら和の最大値を控えておいて、最後にその値を出力すればいい。

D - Index × A(Not Continuous ver.)

C問題と似ているけど数列Aの項が連続していなくても良いパターンの問題。

解き方がぱっとは思いつかないので少し考えた。

ある項を数列Bに加える・加えないの判断をすると見なせばbit全探索で全通り確認すれば手っ取り早いなあと思った。けど、項数が最大で2000なので $2^{2000}$ 回処理することになってTLEするのは計算するまでもないので、bit全探索は使えない。
最大値を求めたいのでソートして大きい順に採用すればと思ったけど数列Bは数列Aの部分数列なので順番は重要。ソートして順番をぐちゃぐちゃにするのはまずい

とかを数秒で考えたけど、これならできるというアルゴリズムではなかった。

少しメタいけどD問題はDPで解く問題なことは最近は多いのでDPが使えないかなあと思ったら解けそうな気がした。(よくよく考えたらbit全探索で $2^{N}$ 処理するのならDP[N][x]でも処理できるから、たしかにDPで解ける。)

漸化式もそれほど難しくなと思ったので頭で考えて実装してみたらWA...
何回かデバッグ実行してDPの途中経過を確認してたら思ってたのと違うなあとなり、結局紙に手計算して、漸化式を整理して、改めて実装し直してみると1回で直った。

その上DPの初期値を何も考えずに0にしていたせいで $A _ {i}$ が負の場合にDPがおかしくなってWAした... ちょっと詰めが甘かった...

丁寧に解くのは大切だなあと思った。

E - Erasing Vertices 2

時間がなかったから問題文を読んだだけ。

以下は問題文を読んで数分で考えたこと。後でちゃんと解いておきたい。

愚直に解こうとすると $O(N^{2})$ くらいでNは最大で $2 \times 10 ^ {5}$ なのでTLEしそうだなと思った。
N回操作を繰り返すから $O(N)$ は必須で、各回で平均 $N/2$ 個の頂点を処理することになるので $O(N^{2})$ になる計算。厳密には平均の隣接頂点数がさらに掛けられると思う。

隣接する頂点数を初めに数えておいて、操作を1回するたびに残っている全頂点分の隣接頂点数を $O(1)$ で更新できれば $O(N)$ で解けるとは思った。一括更新があるならセグメントツリーかなと思った。更新するものがある区間じゃないから使えない気もするけど。

よくよく見ると実行時間制限が4秒と長めだったのでちょっと重めの処理でも間に合いそう。(ループの各回で $O(N log N)$ くらいかなあ。 $O(N ^ {2} log N)$ とかも実は間に合うのかも。)

F - Exactly K Steps

これはコンテスト後に問題文を読んだだけ。

頂点と距離が指定されるから指定された頂点から指定された距離の頂点数をどれか1つ答えるというのをQ回行う問題。

Q回とも頂点が異なる可能性があるので距離の計算は全対地間分が必要そう。なのでN回ダイクストラ法を実行するとかワ－シャルフロイド法で全対地間分を事前に計算しておくのかなあと思いつつ、頂点数が最大 $2 \times 10 ^ {5}$ なのに対してワーシャルフロイド法は $O(N ^ {3})$ なのでTLEしそう。

N回ダイクストラ法を実行が思いついた中では有力だけど、経験則的にN回ダイクストラ法だと事前計算の場合はメモリが確保できなくてエラーになることが多いので多分REになる。頂点と距離を受け取るたびにダイクストラ法を実行するとTLEになりそう。

これも後でちゃんと解いて見ようと思う。(多分解けなくて解説見ることになると思うけど。)

2022-08-13

freee プログラミングコンテスト2022（AtCoder Beginner Contest 264）

競技プログラミング

freee プログラミングコンテスト2022（AtCoder Beginner Contest 264）に参加しました。

結果

A,B,Cの3問正解でした。C問題でちょっと時間が掛かったので順位は低めで悲しい。

D問題は時間がちょっと足りなかった。20分くらい超過してACできた。もう少し落ち着いて解ければギリギリ間に合ったかも。

A - "atcoder".substr()

問題文の通り指定された範囲の部分文字列を出力させる。

文字列の扱い方に関する問題なんだと思う。

B - Nice Grid

指定されたマス目の色が白か黒かを答える問題。

マスの塗り方は同じなので2次元配列で白黒を管理して答えるようにして解いた。

もう少し時間をかければ何かしらの法則性があって数式にできるような気もしたけど、時間をかけたくなかったのと15 $\times$ 15くらいなら手作業で配列を初期化しても大した手間じゃないので手作業で対応した。

C - Matrix Reducing

うまい方法が思いつかずbit全探索で全通りの探索をして解いた。

どの行を選ぶかを全探索しつつ、どの列を選ぶかを全探索して行列を作って、作った行列がBと一致するかどうかで判断した。

制約を見ると行と列のサイズはそれぞれ最大で10なので、行と列それぞれで全探索したとしても $2 ^ {10}$ で1024程度。なので行と列をそれぞれ全探索下としても計算量はざっくりと計算して $10 ^ {6}$ 程度でTLEにはならない。後は行列の要素が一致しているかどうかを確認するのに最大で100回なので計算量は最悪の場合で $10 ^ {8}$ になる。これはギリギリTLEにはならない計算回数なのでbit全探索を使っても間に合いそう。

ここまではすぐに思いついたけど実装に手間取ってそこそこ時間がかかった…

D - "redocta".swap(i,i+1)

指定された文字列をバブルソートしてatcoderにする時の最小のスワップ数を答える問題。

最初は幅優先探索で解こうとしたけど入力例3を試してみたら結果が全然返ってこなかった。改めて考えてみると答えがxだとすると計算量は最小で $6 ^ {x}$ で答えが21になる入力例3だと計算回数が恐ろしいことになっていた。
文字列の種類は7!程度で大したことないはずなので既に見た文字列を弾く処理がうまく動いてなかったのかなあ。

別の方法を考えるために少し考察してみると、無駄なくソートしたときのスワップ回数がそのまま答えになるようなので、atcoderの先頭から順番に並べていく方針で考えることにした。

ABCDEXをバブルソートでXを先頭に持っていこうとするとソート後はXABCDEとなるのでスワップ回数はXを移動させたい距離になる。ここまでは簡単だけど、ソート後の文字列を作る部分でかなり手こずった…　直感的にこうなるという部分をうまくコードにするのが大変だった。

解説を見ると幅優先探索で解くっぽい方針だったので最初の解き方で合っていたっぽい。細かい処理が少し雑だったのかなあ。

2022-08-06

LINE Verda プログラミングコンテスト（AtCoder Beginner Contest 263）

競技プログラミング

LINE Verda プログラミングコンテスト（AtCoder Beginner Contest 263）に参加しました。

結果

A,B,C,Dの4問正解でした。

Dまではなんとか解けたけどE問題は全くわからなかった。期待値を求める系の問題は解いてこなかったので解き方がわからない。確率DPとか言われる類の問題なんだろうなとは思った。

あと、今日は夕方から頭痛がして頭の回転が鈍ってる。これはたぶん気圧のせい…

A - Full House

5つの数字がフルハウスになるかどうかを判定する問題。いろいろ解き方がありそうな問題だと思う。

私はvectorとsetを使ってゴリ押しした。

入力をvectorとsetに入れて、vectorはソートする。 setのサイズが2かつ、vectorの2番目と3番目もしくは3番目と4番目の要素が異なればフルハウスと判断して答えた。

フルハウスの条件はカードがXXYYYもしくはXXXYYの2パターンなのでsetのサイズでカードの種類を確認する。この時点でカードの種類が2じゃないならフルハウスには絶対にならないので処理を終了する。
XXYYYの場合は2番めと3番目のカードの数字が異なり、XXXYYの場合は3番めと4番目のカードの数字が異なるのでどちらかを満たしていることを確認する。

例外としてXYYYY、XXXXYのフォーカードがあり得るけどその場合は1番目と2番目もしくは4番目と5番目の数字が異なるので上記の確認でフォーカードをフルハウスと誤判定することはない。

B - Ancestor

グラフの問題っぽく見えた問題。

親の情報だけはもらえるのでNから1になるまで順番にたどるとか、人をノードとみなして親が誰かをもとに辺を繋いで1からNへの距離をもとめるとか、Union-Find木を作って距離を求めるとかいろいろ解き方が思いついた。

今回はグラフとみなして、幅優先探索で1からの距離を求めて答えた。

C - Monotonically Increasing

これもいろいろ解き方がありそうな問題だと思う。

制約を見ると $1 ＜ N \leq M \leq 10$ で数列の項数は高々10個なのでちょっと面倒くさい解き方をしたとしても時間はそれほどかからないように思った。

後は、vectorで数列を作ってからsetに入れて重複の削除とかソートを勝手にやってもらいつつ、setの内容を順番に出力すれば良さそうなことは思いついた。

各項の値は1以上M以下なので初項は1~Mのどれかで、後は1以上づつ増えていくので幅優先探索で項数Nの数列を作っていった。

データ構造をうまく使えればちゃんと解ける問題だと思った。

D - Left Right Operation

ぱっと問題を読んでもうまい方法が思いつかずちょっと考察していって解いた問題。

問題を読んで内容を理解すると結局、前からx個をLに置き換えて、後ろからy個をRに置き換えたときの数列の総和の最小値を求める問題だった。

制約を見ると数列の長さNが $1 \leq N \leq 2 \times 10 ^ {5}$ だったので $O(N)$ くらいで解かないとTLEになりそうだなと思った。
この時点で使えそうな処理が累積和や尺取法くらいだなあと思った。

とは言え尺取法だとlはループで1づつ増やしていけば良いとしてrをどこまで増やせば良いのかの判断は難しそうなのでちょっと違うなあと判断。

次に尺取法っぽい処理としてクイックソートの初期で数列の前と後ろから要素を見てゴニョゴニョする処理を連想して考えてみたけど尺取法と同じでどこまで要素を見ればよいのかの加減が判断できないので、尺取法っぽい解き方は無理だなあと思った。

手元の紙に色々書いて試してみて、最終的に以下の手順で解いていった。

各項に対してLに置き換えたとき、数列の総和がどれくらい減少するか計算する
先頭から1の和を求めていく。
各項に対してRに置き換えたとき、数列の総和がどれくらい減少するか計算する。
後ろから順に3の和を求めていく。
先頭からiまでの中で2で計算した和の最大値は何になるのかを各項に対して順番に求める。
後ろからiまでの中で4で計算した和の最大値は何になるのかを各項に対して順番に求める。
$1 \leq i \leq N$ に対して、5で求めた値[i]+6で求めた値[i+1]を計算することでx=iとしたときに数列の総和を減少できる量の最大値が求められるので、この計算結果を使って総和がどうなるのかを計算し、最小値を求める。

2022-07-23

AtCoder Beginner Contest 261

競技プログラミング

AtCoder Beginner Contest 261に参加しました。

結果

A,B,C,D問題の4問正解でした。

D問題がDPで解く問題だと判断して実装していたけど微妙に時間がかかった。 C問題までは比較的簡単な気がした。

最近はD問題まで早解きしてパフォーマンスを稼げていたので、今回レーティングの最高値を更新できた。あと100くらい上げたら水色になれる。

A - Intersection

赤色で塗られている部分と青色で塗られている部分の位置関係のパターンは3通りくらいなので場合分けしても解けそう。

紙に線を引いて考えてみると、共通部分があったとしてその左端はmax(赤の左端、青の左端)になるし、右端はmin(赤の右端、青の右端)になるので、共通部分の両端を求めて距離を計算して答えた。

B - Tournament Result

2重ループで全組み合わせを確認して矛盾がないがどうかを確認する問題。

ループの使い方がわかっているのかと文字列の扱いを確認する問題なのかな。

C - NewFolder(1)

i-1までに文字列 $S _ {i}$ が何回出てきているのかを管理して指定された文字列を作成・出力する問題。

どの文字列が何回出てきたのかを連想配列を使って管理すればそれほど難しくない問題。
連想配列を知っているかどうかな問題だと思う。

D - Flipping and Bonus

結論から言うとDPで解く問題。

DP[コイントスの回数][カウンターの数]として、

DP[i][j] = DP[i-1][j-1] + $X _ {i}$ + j連勝のボーナス　でDPを更新していけば良い。

2022-07-09

AtCoder Beginner Contest 259

競技プログラミング

AtCoder Beginner Contest 259に参加しました。

結果

A,B,C,Dの4問正解でした。

今日はずっと問題文をちゃんと読んでいなくて何かしらの情報を見落としたまま解いてて、入力例の答えが一致しなかったり提出したらWAになったりしてた。

ちょっと集中できていなかったのかなあ。

A - Growth Record

等差数列の指定された項の値を答える問題に見えた。
普通の等差数列と違って項数が決まっている、もしくは上限が決まっていてある項以降は同じ値な等差数列。

等差数列として考えると、初項がわかれば簡単に指定された項数の値を求められるので、まずはN,T,X,Dをもとに初項を計算した。
N<=Xかどうかでちょっと処理が分かれるけどとりあえず計算できる。
あとは指定された項数＝Mが上限値なのかどうかを判断して計算して答える。

B - Counterclockwise Rotation

指定された座標をd度回転させた座標を答える問題。考察どうこうとかではなく座標空間上での座標の回転をどうやって処理するのかを知っていて正確に実装できるのかどうかな問題だと思った。

座標空間で回転だったので回転行列で処理した。ただ、計算式の＋と－を間違えてて 1回WAだった。

C - XX to XXX

一方の文字列を指定の処理方法でもう一方の文字列に変換可能かどうかを判断する問題。
文字列の最大サイズが $2 \times 10 ^ {5}$ なのでO(文字列のサイズ)くらいで処理できないとTLEになりそう。
操作も難しさしそうに書いているけど結局、2文字以上同じ文字が連続していたら任意の個数まで増やせるというだけ。

文字列のサイズが大きいままだとTLEになりそうだし複雑な処理もできないので（文字,連続している文字数）と言う形でペアの配列にしてサイズの圧縮をした。（解説を読むとランレングス圧縮とか言うらしい。）

2つの文字列をそれぞれ圧縮して、文字の登場順や各文字の連続している個数を確認して文字列Sを指定の操作で文字列Tに変換できるかを判断していった。

D - Circumferences

円をグラフとか木のノードと考えて、指定されたノードと指定されたノードがつながっているかどうかを判断する問題。

円の個数も最大で3000程度なのでO( $N ^ {2}$ )でもTLEにはならなさそう。解き方は大きくは2つ思いついた。

1つ目は
初めに書いたみたいに円をノードとみなして、2つの円の中心の距離が半径の和以下ならその2ノードはつながっている。距離が半径の和より大きいならつながっていないとみなしてグラフを作っていく。
後は指定された始点がどのノードで終点はどのノードなのかを調べて、幅優先探索やダイクストラ法などの経路探索アルゴリズムで始点から終点へたどり着くかどうかを調べる。

2つ目は
UnionFind木で指定された始点と終点が同じグループにいるかどうかを確認して答える方法。
ある2つの円の中心距離が半径の和以下ならその2つは同じグループと判断して統合していくっていうのを全組み合わせで実施して木を作っていく。最後に始点と終点が同じグループかどうかを確認して答える。

今回は実装が楽そうに思って2つ目の方法で解いた。

2022-07-03

AtCoder Beginner Contest 258

競技プログラミング

AtCoder Beginner Contest 258に参加しました。

結果

A,B,C,D問題の4問ACでした。 E問題はやっぱり難しい。解けそうな方法を考えたけど実装量が多くて、コードを書きながら解き方間違えてる気がしてきた。結局時間内には実装が終わらなかった。

A - When?

指定分数後の時間を表示すれば良い問題。

言語によっては時間計算のライブラリがあるのでそれを使えば楽に解けそう。

地力でとくなら、時の方は（指定分数/60）時間後になるし、今回は最大でも100分なので21か22のどちらかになる。

分の方は指定分数を60で割った余りになる。こっちは1桁になる可能性があるのでそこだけ気をつけて先頭0埋めの2桁表記で表示させる。

出力時に先頭0埋めで表示桁数の設定ができるのでその設定を使って分は表示させるとか、9分以下なら0を表示後に計算した分数を表示させるとか、分数を文字列にして"00"と結合して下2文字を表示させるとかやり方は色々ある。

A問題にしてはちょっと面倒くさい気がする。

B - Number Box

マス目のあるマスを始点としてNマス移動して、マス目に書かれている数字を並べた時にできる数字の最大値を答える問題。

制約を見るとマス目がかなり小さいので全探索で十分間に合う事がわかる。
なので全探索するコードを書いて答えを探せば良い。

実装方法を考えていた時に、似たような内容の過去問の解説で始点の座標と縦方向・横方向の変化量を引数にして探索を行い結果を返す関数で簡単に実装していたことを連想して、そういった関数を作って答えてみた。 8方向分の探索が8回関数を呼び出すだけで住むのでだいぶコードがスッキリできた。（8方向分の探索を1つ1つ書くのはすごく大変そう。）

後は、数字1桁を表す文字は'0'で引くと文字が表す数字を整数値として取得できるとか、 N進数を10進数に変換するみたいに10倍して数字を足してを繰り返すとマスに書かれている数字を順番に並べた数字が作れるとか細々としてテクニックを使って実装した。

C - Rotation

複数のクエリを処理しながら答えていく問題。

よくある解き方としては、最後から処理していくとか、複数の処理をまとめて行うとかして計算量を削減するのが多いと思う。

愚直に解くと「S の末尾の文字を削除し、先頭に挿入する」をx回ループで処理する解き方になると思う。 Q個のクエリで毎回x回のループを処理していては時間がかかりすぎてTLEになるのは予想できる。

なので、x回分の処理を部分文字列を使って1回で処理できるようにしてみたけどそれでもTLEだった。つまり、もっと早く処理できないといけないってことになる。多分各クエリでO(1)くらいで処理できないと間に合わないんだと思う。

少し観察すると、「S の末尾の文字を削除し、先頭に挿入する」を実行するたびに
abcd → dabc → cdab → bcda　と言った具体に文字の開始位置が1つずつずれていっているように見える。そこで今の文字列の開始位置はもとの文字列の何文字目になるのかを管理しつつ、クエリによって開始位置は何文字目なのかを更新したり、管理している開始位置からx文字目はどの文字なのかを答えてみた。
こっちの方法ならACできた。

D - Trophy

どうやって解こうかなと少し考えた問題。

ちょっと考えてみると、以下に気づいた。

X回のステージクリアの内何回かはステージの初回クリアに使われ、残りがクリア済みステージの周回に使われる。
ステージの周回は、クリア済みステージの内 $B _ {i}$ が最小のステージを集会するのが1番効率がいい。
制約的にO(N)くらいで解きたい。

そこで予め、ステージiまでクリアするのに要する時間を累積和を使って計算しつつ、 $0 \leq x \leq i$ のうち $B _ {x}$ の最小値を管理しておき、
1～i番目のステージまでをクリアした場合にX 回ステージをクリアするために必要な時間の最小値を $1 \leq i \leq N$ の範囲でループを使って計算した。
i番目までのステージをクリアするのに必要な時間は累積和の値を参照することで求められて、残りX-i回分の周回は $B _ {1}$ ～ $B _ {i}$ までの最小値をもとに計算できる。

事前に計算しておくと各ループの中はO(1)で答えられるので最終的にはO(N)で答えられる。

2022-06-25

日鉄ソリューションズプログラミングコンテスト2022（AtCoder Beginner Contest 257）

競技プログラミング

日鉄ソリューションズプログラミングコンテスト2022（AtCoder Beginner Contest 257）に参加しました。

結果

A,B,C問題の3問正解でした。

C問題が意外と手こずって時間がだいぶなくなった。
ちょっと難しく考えすぎてた…

A - A to Z String 2

問題文の通り処理すれば良い問題。

愚直に文字列を構築してX番目の文字を出すのが無難かなと思う。問題の制約的にも十分間に合う速度で解ける。

ちょっと早く解く方法も一応ある。
XをNで割った答えと余りによってがアルファベットの何番目の文字を出力すれば良いかが決まるので、余りが0ならX/N番目のアルファベットを、余りが0以上ならX/N+1番目のアルファベットを出力すれば良い。

B - 1D Pawn

これも問題文の通りに処理すれば良い問題。

問題文に書いている操作の通りに実装してシミュレートすればQ回操作した後の状態を用意できるので、各コマの位置を出力すれば良い。

ループとか条件分岐を正しく処理できるかと言う問題だと思う。

C - Robot Takahashi

難しく考えすぎてかなり時間が掛かった問題。

結論としては、Xを決めた時に高速にf(X)を処理できる関数を作っておいて、後は線形探索でf(X)の最大値を求めれば良い。

問題文を読んで最初は2分探索かなと思ったけど、単調増加とか単調減少ではなくて、どこかまでは増加して、どこかからは減少するので違うなあってなった。
次に、上に凸の二次関数の最大値を求める問題とみて三分探索すれば答えが求められそうと思って実装してみた。確認はしていないけど、実際は二次関数っぽい形にはなるものの極値がいくつかあるグラフになるっぽいので二次関数ではなく、三分探索も使えない。

制約的に判定をO(N)未満でできれば線形探索でも間に合うのに気づいて、線形探索で実装してみた。判定の部分は予め子供だけ、大人だけの体重のリストをソートして用意しておいて、2分探索でX未満の子供の人数やX以上の大人の人数を求められるようにして対応した。

中途半端にアルゴリズムを覚えていたのでかえって遠回りしてしまった気がする。
最初は愚直に解くのをベースに解法を考えたほうが早く解けるのかなあ。愚直で無理なら真面目に考察して使えそうなアルゴリズムを吟味してみるとか。