れとろのメモ置場

とあるSEのメモ置場

ユニークビジョンプログラミングコンテスト2024 夏(AtCoder Beginner Contest 359)

ユニークビジョンプログラミングコンテスト2024 夏(AtCoder Beginner Contest 359)に参加しました。

結果

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

D問題が相変わらず解けない… ちゃんと時間取って精進しておかないと、最近参加者のレベルがじわじわ上がって来てるから現状維持だけだとレーティングが微妙に落ちてくる…

A - Count Takahashi

Takahashi か Aoki かの文字列がN個与えられるので、Takahashiが何個与えられたかを答える問題。

文字列の内容比較ができればTakahashiと等しいかどうかが判定できるので、 N回比較してTakahashiと一致している文字列の数を数える。

別解としては、与えられる文字列は2通りなので文字列の長さが5文字以上あるかどうかでTakahashiかどうかが判断できるので、文字列の長さを使ってTakahashiの数を数えることもできそう。

B - Couples

2N人が並んでいて、1~Nのいずれかの数値が割り振られている。同じ数値は2人だけが持っている。
この時、ABAみたいに同じ数値に一人挟まれている人が何人いるかを数えて答える問題。

数えるのはABAとなっているパターンだけで良いので、連続する 3人をみて1人目と3人目が同じ数字となっているかどうかを確認すれば良い。

C - Tile Distance 2

横に2マス縦に1マスのサイズのタイルが馬目地状に座標平面に敷き詰められている。 初期値から指定された座標へ移動するのに最小で何個のタイルを経由するかを数えて出力する問題。

タイルの縦のサイズは1なのでy座標の差分個だけのタイルはどうやっても経由する必要がある。 その代わり縦に移動すればするほど、x座標の移動のために経由するタイルの数は少なくなる。 (タイル1個分縦に移動すれば、1マス分追加でのタイル経由なしで横に移動できる。)

なので、まずは縦にタイル何個分移動が必要かを計算し、その結果に応じて横移動のためのタイル経由なしで移動できるxの値域が計算できる。
目的のx座標がその値域に収まっていれば追加の計算は不要で、値域に収まっていないなら 値域の範囲で目的のx座標に1番近づいた状態からタイルを何個経由すればたどり着けるかを計算する必要がある。

目的のx座標に1番近い上で計算した値域がタイルの左右どちら側なのかや、目的のx座標がタイルの左右どちら側なのかで微妙に計算方法が違って面倒。同じタイル内での左右移動だけなら経由するタイルの数は0で済むので計算しやすいようにゴールのx座標を微調整してから計算すると横に移動するマスの数÷2で経由するタイルの数を求められる。

D - Avoid K Palindrome

A,B,?で構成された最大1000文字の文字列を与えられるので、?にAかBを当てはめた文字列全パターンの内、 長さKの部分文字列が回文となっていない文字列のパターン数を答える問題。

?にAかBかの全通りを求めないと答えられなさそうだなと思ったので、深さ優先探索で全通り探索することにしたけど、そもそもこの方針が間違いらしい。 ?の数がある程度増えると時間内の全通り探索は不可能なので、どうやって効率的に数える必要のないパターンの探索を減らしつつ探索しないといけないパターンは探索を進めていくのかを考えてた。

長さK文字の回文のパターンを全部求めてから探索中の文字列にそのパターンが出てきたらそこから先の探索は打ち切ったり。

解説を軽く見るとDPで解く問題だったらしい。このパターンのDPは多分初見なのでDPと言う発想にたどり着かなかった。 深さ優先探索は無理そうだなあ。DPかなあ。でも何個目かの?にAかBを入れたとして、そこまでのパターンはどこかに持っていないと回文かどうかの判断できないしDPっぽくないなぁとかは思ってた。

CodeQUEEN 2024 予選 (AtCoder Beginner Contest 358)

CodeQUEEN 2024 予選 (AtCoder Beginner Contest 358)に参加しました。

結果

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

E問題がさっぱりわからなかった。ダメ元で27次元くらいの配列作ってごり押そうかとも思ったけど、要素数が多すぎでコンパイルできなかったので諦めた。

A - Welcome to AtCoder Land

問題文の通りに実装したら解ける問題。

文字列を2つ受け取って、それぞれが指定された内容と一致しているかどうかを判定して、Yes/Noを出力する。 文字列比較の方法がわかれば解ける問題だと思う。

B - Ticket Counter

問題文を読むとイベントドリブン型のシミュレータでも作ろうかと思った問題だった。B問題でそれは過剰だろうと思ってもっと簡単に解けるだろうとちょっと考え直すことにした。

A秒でお客を捌くチケット売り場にN人のお客さんがT _ {i}秒後にやってくるので、各お客さんは今から何秒後にチケットを買ってチケット売り場から離れていくかをそれぞれ答える問題。

i番目のお客さんが来たときに売り場が空いていればすぐにチケットを変えるのでT _ {i} + A秒後に売り場から離れる。
もし売り場が空いていなければ前の人がチケットを買い終わるのを待ってからi番目の人が買い始めることになる。 i-1番目の人が売り場から離れるのがX秒後立とするとi番目の人がチケットを買い終わるのはX + A秒後になる。

また、1番目の人は売り場到着後すぐにチケットが変えるので、1番目の人が売り場を離れるのは T _ {1} + A秒後になる。

後は順番に2番目以降の人は1つ前の人がいつチケットを買い終わるかを元に計算していける。

C - Popcorn

N個のお店がそれぞれ何種類かのアイテムを扱っている。アイテムは全部でM種類ある。アイテム全種類を揃えるのには最小で何個のお店を選択すればよいかを答える問題。

どのお店を選択するかは全通り試したいなと思いながら制約を確認するとお店の数は最大で10個だった。 なのでビット全探索でどのお店を選ぶ・選ばないを全通り試せる。

後は、あるお店を選んだときに何種類のアイテムを揃えられるのかを管理しつつ、何個お店を選んだかをカウントしていく。 あるパターンで一通り処理が終わったら、結局何店舗選んで何種類のアイテムを揃えられたかを確認して 全種類のアイテムを揃えたときに選んだ店舗の数の最小値を管理していく。

D - Souvenirs

M人の人がそれぞれ価値B _ {i}以上の価値のあるアイテムを要求するので、 N種類あるアイテムの中から全員の要求を満たしつつ価値の合計の最小値を求める問題。

B _ {i}以上を要求している人には価値B _ {i}以上の内できるだけ小さい価値のアイテムを割り当てたい。 また、残りのアイテムを管理しているデータ構造では線形探索よりは二分探索で指定されている価値以上のうち価値最小のアイテムを探したい。

これに適しているデータ構造としてmultisetがあったので、multisetを使って解いた。 具体的にはmultisetにアイテムを全部突っ込んで、B _ {i}をソートしておく。 後はB[i]以上の値をlowe_boundで探して見つかったものを答えとして足し合わせつつmultisetから削除していく。

最後に足し合わせた合計値を出力する。

AtCoder Beginner Contest 356

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

結果

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

D問題何回見直してもアルゴリズム的におかしいところが見当たらなくて、どこかでオーバーフローしてるんだろうなと思ったら案の定オーバーフローしていて完全に見逃してた。 コンテスト終了後に解説見てたら気がついて修正したらACできたし、 何なら初回に提出したコードを修正したらACになった。

ソースに直書きした数値はintとして扱われるっていうのは知らなかったので、ビットシフトでオーバーフローしていたのを完全に見逃してた。結構もったいないミスだなあ。

A - Subsegment Reverse

1からNまで順に並んでいる数列のLからRまでを逆順にしたときの数列を出力する問題。

1からL-1まで出力してRからLまで出力して、R+1からNまで出力すれば解ける問題。 任意の内容でループ処理を書けるなら特に困らず解ける問題だと思う。

B - Nutrients

N個のアイテムとM個のパラメータがあって、それぞれのアイテムは各パラメータを増加させていく。 N個のアイテムすべてを消費したときに各パラメータはしきい値A_{i}を越えているかどうかを判定し結果を出力する問題。

アイテムの数とパラメータの数はそれほど多くないのでそこまで難しくないと思う。

M個のパラメータそれぞれの合計値を管理する配列を用意して、全アイテムの各パラメータの値を順番に足していく。 最後に各パラメータがしきい値を越えているかどうかを順番に確認して結果を出力する。

二重ループと配列を使ったデータの処理ができれば解ける問題だと思う。

C - Keys

N本の鍵があって何本かは正しい鍵で、何本かはダミーの鍵になっている。この時K本以上の正しい鍵を使えば鍵が開く。 こういった状況で何本かの鍵を同時に使って鍵が開くかどうかのテストをM回行った。

N本の鍵のどれが本物でどれがダミーかのパターンの内テスト結果に矛盾しないパターンは何通りあるかを答える問題。

鍵の本数は最大でも15なので全通りのパターンを確認してもなんとか時間以内に処理が終わらせられそう。

全通りの処理としてビット全探索を採用して全パターンの処理をすることにした。 1パターンごとにMケースあるテスト結果に矛盾しないかどうかを確認して、矛盾しないパターンの数を数えていき、 最後に出力した。

全通りの探索を正しく実装できるかどうかがポイントな問題だと思う。 ビット全探索を知っているかどうかがかなり影響しそう。

D - Masked Popcount

最後までオーバーフローに気付けなくて時間内には解けなかった問題。ソースに直書きした数値はintになるっていうのを知らなかったのと、任意のビットが1かどうかの判定にC問題で出てきたビット全探索で使っている処理を流用したのがまずかった。
ビット全探索だとintの範囲で収まることが多かったから用意してたコードメモがintにしか対応してなかったのが失敗だったなあ。

NとMが与えられるので\Sigma^{N}_{k+0}(k&Mの1となっているビットの数)を計算して出力する問題。 NとMはともに2^{60}未満とかなり大きな数になる可能性がある。

愚直に0からNまで順番に論理積を計算して1となっているビットの数を数えて足してとやっていたらTLEになる。

別の解き方を考えていった考察としては以下の通り

  • 論理積なのでkとMの両方で1となっているビットだけが加算の対象となる。
    Mの時点で0となっているビットはそもそも処理する必要がない。
  • 各ビットを個別に注目すると1ビット目は010101・・・2ビット目は00110011・・・といった具合に周期性がある。

なので0からNまでを順番に処理するのではなく、 N以下の内1ビット目が1になる数字はいくつあって、 2ビット目が1になる数字はいくつあって、・・・を計算して最後に順番に足していけば解けると考えた。 これなら60ビット分の数値計算をするだけて済むので処理時間はかなり短くなる。

N以下の数値の内iビット目が1になる数値の数は、 周期何周分とあまりいくつかを計算して、1周期の中ではビットが1になるのはいくつあって、あまりのうちビットが1になるのがいくつあるのかを計算すれば求められる。

  • 周期数は(N+1)/2^{i}あって、1周期のうちの半分は1なのでまずは(N+1)/2^{i}/2
  • あまりは(N+1) mod 2^{i}あって、そのうち前半の2^{i}/2はビットが0になる。なのでビットが1になる数値の数は ((N+1) mod 2^{i}) - (2^{i}/2)になる。

この2つの値を足すと、kとMの論理積の内ビットiが1となる数値の数になる。

60ビット分この処理を行って、最後に60ビット分の算出結果を合計すれば求めたい値を算出できる。

東京海上日動プログラミングコンテスト2024(AtCoder Beginner Contest 355)

東京海上日動プログラミングコンテスト2024(AtCoder Beginner Contest 355)に参加しました。

結果

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

最近またDが解けなくなってきた。復習ちゃんとやらないとなあ

A - Who Ate the Cake?

人1、人2、人3の3人の犯人候補がいて、人A、人Bは犯人じゃないとの証言が与えられる。 この時、犯人を一人に絞り込めるかどうか、絞り込めるなら誰が犯人かを出力する問題。

人A、人Bが別々の人なら名前の出ていない人が犯人に絞り込める。 人Aと人Bが同じ人なら犯人は一人に絞り込めない。

3人分の犯人かどうかのフラグを用意しておいて(初期値は犯人フラグ)、人A、人Bの入力に応じて2人分のフラグを犯人じゃないと更新する。 最後に3人分のフラグを確認して、1人だけ犯人フラグなら犯人を特定できるので、その人の番号を出力する。 犯人フラグが2人いたら犯人を特定できないので-1を出力する。

B - Piano 2

数列Aと数列Bが与えられるのでこれらを全部まとめてソートしたときに数列Aの要素が2つ連続するかどうかを答える問題。

数列Aと数列Bで同じ値が出ることは無いので連想配列で数値をキーにAかBかを保存して、この数値はこっちというのがすぐに分かるようにする。 次にAとBをまとめた配列を用意してソートする。 最後に数値を元に数列Aの要素なのか数列Bの要素なのかを確認して、数列Aの要素が2個以上連続するのかどうかを確認して答える。

C - Bingo 2

N×Nのビンゴカードがあって、T個の数値が与えられるので何個目の数字で初めてビンゴになるかを答える問題。

Nのサイズ的に1個数字が与えられる度に縦横斜め全部を1個1個チェックしていくのは無理でTLEになる。 この問題のポイントはビンゴになっているかどうかのチェックをどれだけ簡単にできるのかだと思う。

数字は1から順番に並んでいるので、入力された数値が何行目の何列目なのか、斜めの列の一部分なのかどうかを算出できる。

算出した結果を元に各列、行、斜め2つ分それぞれの穴を開けた数を管理しつつ、新しく穴を開けた結果その行列斜めで穴の数がN個になっているかどうかでビンゴになっているかどうかを判定した。 これならチェックの度に計算量はO(1)で処理できるようになるのでTLEにはならなくできる。

AtCoder Beginner Contest 352

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

結果

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

コンテスト後にD問題の解説を見たら結構惜しいところまでは解けていたっぽい。採用するデータ構造を誤っていて処理に余計な時間をかけていたみたい。数列の最大値、最小値を取得するのにsetが使えるのは自分の中には無い発想だったのでためになる失敗だったと思う。

A - AtCoder Line

駅1から駅NまでのN個の駅があり、X駅からY駅へ移動する。このときにZ駅を通るかどうか答える問題。

XとYの間にZがいるかどうかを判断してYes/Noを出力するだけの問題。

X,Yの大小関係が不明なので大小比較してスワップして常にXがYより小さい/大きいを固定してから X,Yの間にZがいるかどうかを確認すれば良い。 大小関係的には X \leq Z \leq Y (X \leq Yの場合)になっているかどうかをif文で判断すれば早い。 もしくはループ処理で1つずつ確認していっても制約的には間に合う。

B - Typing

タイプミスしながらある文字列(T)を入力したので、もともと入力したかった文字列(S)の各文字が正しく入力できている文字列Tの位置を順番に答える問題。

文字列Sの文字を文字列Tの前から順番に探して答えていけば解ける問題。 文字列はそこそこ長い可能性があるので、文字S _ {i}を探すときは文字列Tの先頭からじゃなくて、S _ {i-1}を探すときに途中まで探索していた文字列Tの続きから探索を始めていくと言う工夫は必要そう。

C - Standing On The Shoulders

巨人がN人いて、それぞれの肩の高さA _ {i}と頭の高さB _ {i}が与えられる。※地面を基準としたときの高さ。

巨人がそれぞれの肩に立って積み上がっていく時、巨人の頭の高さとして実現できる最大値を求める問題。

N人目の巨人の足元の高さはN-1人の巨人の肩の高さの和になる。 だからN人目の巨人の頭の高さは、N-1人の巨人の肩の高さにN人目の頭の高さを加えた位置になる。

N人の巨人それぞれが1番上にいる場合の頭の高さを計算して、最大値を出力すれば解ける。

N-1人の巨人の肩の高さを毎回計算しているとTLEしそうなので工夫が必要そう。 予めN人分の巨人の肩の高さの合計を計算しておき、巨人iが1番上だった場合は、肩の高さの和からA _ {i}を引いてB _ {i}を加えることで巨人iの頭の高さをO(1)で算出できる。

D - Permutation Subsequence

1~Nを並び替えて作った数列が与えられるので、i~i+Kの各位置の最大値と最小値の差の最小値を出力する問題。

色々考えてみた結果としては以下の通り。

  • サイズKのウインドウをスライドさせているわけなので、1~N-Kまでが探索の範囲になる。N-K+1からK個数値を探していくと最後の数値はN+1になって数列の最大値を超過する。探すだけ無駄なのでどこからK個見るかの基準には1~N-Kで間に合う。
  • 与えられる数列は1~Nを並び替えたものなので、それを元に値iは数列のどの位置にいるのかを管理している方が処理が楽そう。数列の端から端まで探索してKの値を探すより、1はどこ、2はどこというのを管理しておけばK個の値を参照するだけでその時の処理対象の位置が取得できる。

という事で各要素にランダムアクセスできて、先入れ後出しができるデータ構造が適していそうと思ったのでdequeを使って解くことにしてみた。 1つ要素を追加するときに最大値を更新して、1つ要素を削除するときに最小値を更新しながら、常に要素数がK個になるようにしながら最大値と最小値の差を計算して最後に差の最小値を出力してみた。

けどTLEでダメだった。

結局コンテスト中には解ききれなかったのでコンテスト後に解説を読んでみたら、 データ構造としてはsetを使うのが正解だったみたい。setだと最大値と最小値の取得が簡単にできるので要素を更新するたびに最大値・最小値をメンテする必要がなくなって、その分処理が早くできるっぽい。

確かにdequeを使って管理していると、すでにキューに入っているどれかが新しい最大値・最小値となる場合は毎回K個全てを探索しないといけなかったのでTLEの原因だろうなとは思っていた。

AtCoder Beginner Contest 351

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

結果

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

D問題解いてみたらTLEになってて、結局時間内には正解できなかった。でも解説を見てみると解き方の方針自体はTLEになった回答と同じだった... 何か無駄な処理でもあってTLEになったのかなあ... ちょっと納得いかない...

A - The bottom of the ninth

野球が9回表まで終わっているので9回裏のチームは何点以上取れば勝てるかを答える問題。

各回での2チーム分の得点が与えられるのでチーム別に集計して、後攻側のチームが何点取れば先攻側の得点+1点になるかを計算して出力する。
問題文の通り処理するだけのいつものA問題

B - Spot the Difference

1箇所だけ異なる文字列が1組与えられるので、文字列が異なる位置を答える問題。

文字列から任意の1文字だけを参照する方法を知っていれば解ける問題。 ループで全通りのチェックと文字列比較と文字列から任意の1文字の取得ができれば解ける問題。

C - Merge the balls

数列が与えられるので、空の列に指定された手順で処理しながら1つずつ移動させていき、最終的に列の要素数を答える問題。

空だった列に移した後、最後尾2つを対象に処理を行っていく。
数値2つの値が同じなら2つを取り除き+1した値を数列へ加えて、2つが異なる値だったら次の値を列へ移動させる。

最後尾2つの値を処理したいので空の列としてスタックを使うことにした。 最後尾2つは2回ポップすれば取り出せるので、することがなくて元に戻す時の順番だけ気をつければ今回の問題にあったデータ構造だと思う。

もともとの問題文だと数列の値は2 ^ {A _ {i}}で列の最後尾2つの値が同じ時はその数値の和を列に追加するという設定だったけど、0 \leq A _ {i} \leq 10 ^ {9}だったのでバカ正直に累乗を計算して値を列に加えていくのは現実的じゃない。そもそも2 ^ {10 ^ {9}}とか大きさ的に扱える範囲を大きく越えてそう。
指数部分だけ管理すればなんとか扱える範囲で収まるし、同じ数の和を計算すると指数が1増えるだけでするので、わざわざ指数を元に数値を計算して、和を計算して、指数表記だと2の何条になるか求めてってことはしなくて済む。

一通り数列の値を列へ移し終えると、要素数はスタックのサイズを出力するだけで済むので最終的な要素数を1つ1つ数えないで済む。

スタック以外でも配列なら頑張れば対応できると思う。キューで処理するにはちょっと無理がある。

どのデータ構造を使うのかと、そのデータ構造で何を管理するのかを正しく設定できれば後は指定されたとおりに処理するだけの問題になるのでそこまで難しくなくなると思う。

D - Grid and Magnet

グリッドが与えられて、一部のマスには磁石がある。磁石と隣り合うマスに移動するとそれ以上は移動できなくなる。こういった設定のときに、そのマスから移動可能なマスの数をそのマスの自由度と定義する。 この時自由度の最大値を求める問題。

磁石と隣り合わないマス同士が隣り合っていれば、そのマス達の自由度は同じになる。 なので、磁石と隣り合わないマス同士をグループとして1まとめにし、グループごとに自由度を求めて、自由度の最大値を出力すれば解けると考えた。

と言う事で大雑把な方針としては

  1. Union-Find木で磁石に隣接しているマス以外でグループを作る。
  2. グループ毎に自由度を求める。
  3. 求めた自由度の内最大値を出力する。

として解いてみた。 けど、TLEでダメだった。

AtCoder Beginner Contest 350(Promotion of AtCoderJobs)

AtCoder Beginner Contest 350(Promotion of AtCoderJobs)に参加しました。

結果

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

個人的にはC問題が面白いなと思った。自分でソートを実装してどことどこを入れ替えるかを答えるというのは、 ソートの種類ごとの計算量とかを把握していないと実装はできてもTLEしたり交換はN-1回以内とかの制約に引っかかると思う。バブルソートなんて実装したらとてもじゃないけど通せない。

A - Past ABCs

ABCXXXのようにABC+数字3桁の6文字が与えられるので、それはこれまでに開催されたコンテストの略称かどうかを答える問題。 開催されたコンテストはABC001からABC349の範囲でABC316だけは誤答になるのでそこだけは例外的に処理が必要。

単純に処理するなら文字列の大小比較するだけで解けると思う。 ABC001以上かつABC349以下であり、ABC316ではない時はYesと出力して違うときはNoと出力するだけの問題。

プログミング言語的に文字列の大小比較がただの演算子でできるなら特に困らない問題だと思う。

最初の3文字はABCで固定なので後ろの三文字を取り出してどうにかして数値に変換して・・・と処理しても良いけど面倒くさい。

B - Dentist Aoki

最初はN本の歯があってQ回治療を行う。T_{i}番目の歯があるなら歯を抜いて、歯がないなら歯を生やす(生やす!?)。 最終的に生えている歯の本数を答える問題。

T_{i}が出てきた回数が奇数か偶数かで、その歯は最後抜かれたのか生やされたのかが判断できる。 配列でどの歯を何回治療したのか管理して、最後に治療回数が偶数回の歯の本数を数えて出力すればよい。

C - Sort

数列が与えられるのでN-1回以内のスワップでソートする問題。 どの位置の数字とどの位置の数字を入れ替えるかを順番に出力して答える。

ソートのやり方はいろいろなアルゴリズムがあるのでまずはその中からどれを実装するか決めて、スワップするときにどことどこを入れ替えたのかを記録していけば解けると思う。
ソートアルゴリズムの計算量を把握して置かないとO(N^{2})とかのアルゴリズムで実装するとTLEになるので注意が必要。

はじめはクイックソートを実装しようとしたけどテストケースのいくつかがWAになった。サンプルは問題ないから微妙なパターンでバグがあったのかなあ。 クイックソートがダメだったので選択ソートをベースにしつつ連想配列でどの値がどの位置にあるのかを管理して、未ソートの中の最小値がどこにいるのかをすぐに分かるようにして実装した。

D - New Friends

N人の人がいて、友達の友達は友達と言う考えで友達を増やしていった場合、ユーザー全体では今の状態から最大何人友達を増やせるかを答える問題。

サンプルを手計算しながら考えてみると、以下のことに気づいた。

  • 人のつながりの状況によってはいくつかグループができる。
  • グループ内だと全員と友達になれる。(友達の友達は友達になれて、その新しい友だちの友達とも友達になれるので、結局グループ内の全員と友達となれる。トポロジー的にはフルメッシュになる。)

なので解く方法としては、人と人とのつながりを元にグループ分けする。 グループ内では未設定の友達関係が何組あるのかを数える。

グループ分けする方法は深さ優先探索幅優先探索、Union-Find木を使うなどいろいろやり方がある。

グループ内で新規に友達となれる組がどれくらいあるのかはグループ内に誰がいるのかと現状何組の友達がいるのかを元に数えていく必要がある。けど、グループごとに配列を用意してまとめて、二重ループでこの組は今友達なのかどうかを確認して、数えてとやってみたらTLEとかWAとかMLEとかになった...
よくよく考えると知りたいのは新規に友達となれる組数だけで、誰と誰が友達になれるのかはあまり重要じゃない。 グループごとの人数と、グループ内の友達の組数だけわかれば、最大何組の友達関係が構築できる中で、今この組数しか構築できていない。よって新規に何組が友達になれるかが計算できる。 なのでこの組み合わせは友達かどうか確認するのをやめて計算して友だちになれる組数を全グループ分求めて答えることにした。