まえがき
本文(嘘)
木曜日に再試が有ります．怖いです．
ICPCが終わってからでなんですが，めっちゃ競プロのモチベが高いです．
(本当にごめんなさい)
ここから先は読まなくていいパートです．
今日解いたモンダイ
AGC018 B- Sports Festival
- [愚直透,貪欲かな?]
自力では解けませんでした．解説を見て理解．
まず，全ての競技を開催するところから始めます．
全ての競技を開催するとき，それぞれの選手(N人)に対して，必ず一番好きな競技に出ることになります．
つまり，選手iが参加する競技はA[i][0]となります．
このとき，競技 j ( 0 <= j <= m-1) に出場する選手の人数を，
b_jとします．(b_0 + b_1 + b_2 + ... + b_n-1 == N)
また，この中で値が最大のものをMAX(b)と表記しましょう．
この，M種類全ての競技を開催している状態で，MAX(b)を減らすためには，MAX(b)となるような 競技 j の開催をやめなければなりません．
なぜなら，MAX(b)となるような競技j以外の開催を辞めたときに何が起こるか考えます．
{j o o o o,
j o o o o,
o j o o o,
j o o o o }
表の見方ですが，'x'は開催しないことに確定した競技, 'o' は開催することになっている競技，です
(つまり，o にはj以外の競技番号が入ります)
この時，jへの参加選手は3人と言うことになります．(上から3番目の行を見ると，jより好きな競技が開催されていることが分かる)
この状態から，j 以外の競技を'x'にしてみます．
{j o x o o,
j x o o o,
x j o o o,
j o o x o }
まぁ，こんな風になったとしましょう．
見ての通り，jへ参加する人数が変わりません．
だから,MAX(b)を変えるためには，MAX(b)となるような競技jをやめる以外に手はありません．ある選手がj より嫌いな競技をkとして，kの競技の開催を辞めてもある選手はjに出る
また，ある選手がjより好きな競技をkとして，kの競技の開催を辞めると，ある選手は j へ出場する可能性が出てきます
何が言いたいかっていうと，MAX(b)となるような j 以外の競技を辞めたところで，MAX(b)は変わらないか，増えることしか起こりません．
つまり，j を辞めない限り，MAX(b)以下にすることが出来ません．
更に，競技を辞めることに決めていく順番は関係無いので,MAX(b)となるjが分かった瞬間にjを辞めて次のMAX(b)を求めていくと良い．
あとがき ICPC参加記
2014年
これは僕が中学2年生の頃です．
僕が所属していた男子バドミントン部は，同じ学年の男子が6人(僕を含む)いて，3年生の先輩は一人も居ないという悲しい部でした．
もう何月のことだったかハッキリと思い出せませんが,いつかの大会に僕らはでました．
先輩がいないため，他校の一つ上の学年の方たちと戦うことになった俺，美味しいパスタ作ったお前．
対戦相手が強すぎるせいか，緊張が極値に達したからか（多分前者），プレイ中ガチ泣きしてしまいました．
2020年11月7日 都内某所
当日の流れは以下
起きる．
寒い
布団
布団
布団
起きる
コンビニ
飯
飯
お菓子
お菓子
飯
エナドリ
エナドリ
競プロ
競プロ
腰やすめ
腰やすめ
屈辱のあの大会から6年経ち，僕はいま，パソコンの前に座っています．
あの日は 泣いて座った.でも，今日は違う．
僕はそんなエモい気分になっていた．
16時30分試合開始．
国内予選中
まずトップページにつながらない．
まぁ，なんか，アクセス多いんだろうし仕方ないな．
電話しろとかかいてあったけどそもそも俺携帯電話持ってないし，まあ多分他のチームも同じ状況だろ．と楽観視しながらボイスチャットで「つながりませんね~^^」と．
16時???分．「あ，繋がった」
とりあえずA~Dぐらいのモンダイを一通り見て，BがUnionFind使うっぽいな，となって，
僕は参加者中レートが2番目だったのでまあレート順でABCと割り当ててみる．
その後，なんかただのUnionFindじゃねえぞ？となって頭がパニック，C担当をしていたチームメイトが実装できそうなので代わってもらうことに.
Cを見る．
3項の積がpなら, w<=d<=hとこっちで決めてもモンダイないだろうと判断．
wをpの三乗根まで回して…みたいな感じで実装
...している間にAをメイトが通してくれました
実装が終わった．
sampleで手元で実行．
実行が終わらない
whileループをバグらせたか？
チームメイトとのコードを見比べるもやはり分からない．
while(1){ int n; cin >> n; solve(n); }
みたいな感じにするか???いやでもそんなんしても治らんやろ…
と思いつつ，「whileループ止まらなくなっちゃった…」と言ってソースコードを共有
数分して，「実行に時間かかってるだけじゃね?」とチームメイト．
もう一度手元で実行して見ると時間がかかりつつも無事結果はあっていることを確認
入力データをページが取り寄せて手元で実行…
実行が長過ぎる
この間にチームメイトがBを通してくれました．
実行長過ぎるから，入力をcin使わないほうがいいのか？とか言いつつ，D以降の方針も立たないのでcinを使わない入力とかに変更できそうだったら変更してもらえない？
と言って変えてもらいつつも実行は継続
5分以上かかった気がするが，やっとデータの1つ目の実行が完了
僕の方が結局データの実行が早く終わったので，入力の形式はcinのままで出してデータ1でAC
その後，データ2でも5分ぐらいの実行を待ち提出，AC(ありがとう)
普段競プロしかしていないので，2s以内に止まらないプログラムは無限ループを回していると思い込んでしまいます．
実行に時間がかかっていると教えてくれたのは本当に助かりました．(いや，まぁそりゃそうだけど，計算量削減できなかったの力不足だよね)
その後D以降は通すことなく椅子とキットカットを温めました．
温まっているキットカットはちょっと気持ち悪かったです．
反省点とか改善点とかは思いつくけど，正直ICPC3日ぐらい前まで競プロ全然していなかったので，何となく書くことに抵抗があるので書きません(他の頑張った人たちに対して何となく負い目がある)
うちの大学には競プロサークルがなくて，Twitterで知り合った1年生と3年生（俺は二年）に声をかけてICPCに出ることができました．
出させてくれてアリガトウ
それに，コーチ探しも教授にメールをして，教授から院生を紹介してもらいました．
うちの大学でICPC国内予選にでれたのは，そこそこ運が良かったんだと自分でおもっています．
来年そのような出会いがあるかは分かりませんが，でれるならもう一度出たいです．
後，これは大事なので言っておきたいんですが，ICPC出れて良かった．
最後になりますが，計算量って大事ですね．
