M-SOLUTIONSプロコンオープン：水色erのムーブ備忘録
競プロ大好きなsyunsukeです。
今回は昨日のM-SOLUTIONSプロコンオープンのムーブ備忘録です。
配点 A:100 B:200 C:500 D:500 E:600 F:800
制限時間 120分
コンテスト開始時のsyunsukeのレート 1290
この配点、水色下位にとっては恐怖。
500、600点問題が解けなければ、茶、緑、水色下位あたりのＢ早解き競争が始まり、問題文が開くまでの時間次第では茶パフォもありえる？
加えてABC128で集中力が100分続かなかったと書いた翌週に120分コンテスト。
嫌な予感しかしないです。
今回の方針
・まずＡ:100点、Ｂ:200点を解く。
・Ｃ:500点は問題を見て、解けそうでも先にD:500点の問題を見る。
・D:500点が解けそうでも先にE:600点を見る。
・C,D,Eの解きやすそうなものから順に解く。
コンテスト開始
Ａ：はやく問題文見せてください
昔(30年くらい前かな？)小学校でやったやつ
(N-2)x180
一応テストケースで確認して
2:18 AC
Ｂ：Ｘの数をかぞえて７以下or８以上のif文
一応テストケースで確認して
4:31 AC
Ｃ：確率の問題、しかもテストケースの2番が変な数字になってる？
何をさせたい問題なのかよくわからん。
方針＋出題の意図も読めないのでパス
Ｄ：木の２つの頂点を結ぶ辺のコストは2つの頂点の数字の小さいほう
だったら、いちばんたくさん子がいる頂点を最大の数字にして、それに隣接する頂点に順に大きい数字から順に割り当てる。
子の中でも、さらにたくさんの子がいる頂点に大きな数字を割り当てたいがどうやって？
方針＋解ける見込みがないのでパス
Ｅ：等差数列の積
式をいじってみて、ダブリングをうまいこと使えば解けそう？
方針によりパス
C,D,Eどれから着手？
見込があるのはE,D,Cの順
ますはＥから
Ｘ＋０ｄ、（Ｘ＋１ｄ）、（Ｘ＋（Ｎ－２）ｄ）、（Ｘ＋（Ｎ－１）ｄ）
先頭と最後を掛けて
Ｘ2＋（Ｎ－１）ｄＸ
２番目と最後から2番目を掛けて
Ｘ２＋（Ｎ－１）ｄＸ＋・・
Ｘ２＋（Ｎ－１）ｄＸをＡとおいて・・
できそうでできません。
やっぱりパス
20:00頃
Dに戻る
子のうち、さらにたくさんの子をもつものの検出？
UnionＦindでsizeでも使う？
そもそもその方針であってる？
正しいような間違っているようなモヤモヤ
やっぱりパス
40:00頃
Ｃに戻る
やっぱり出題の意図がわからず、≡記号の意味をググったり
テストケース2で出てくる数字をいじくりまわしたり
テストケース2の期待値は93/16で、ここからどうやってやたらでかい数字を出す？
これも無理
順位表確認
！！！やばい！！！
ってかなんでみんなＤ通せるの？
Ｄに戻る
良くわからないけど、解いてる人数からして難しいことはやってないはず。
もしかして、子を一番多くもつ頂点に最大の数字、そこから繋がる頂点に、順に大きい数字(その子の数は関係ない？）を割り当てれば良い？
・最大の数字はスコアに反映されないが、最大の数字の頂点に隣接する頂点の数字は必ずスコアに反映される。
・小さい数字はスコアに反映させたくないから、末端に配置して、1回だけスコアに反映(末端以外だと2回スコアに反映されてしまう)
と考えれば
cは大きいほうから順にソート
a,bを見て一番多く出現した頂点に最大のcを配置
後は最大のcを配置した頂点からのDFSで、順に大きいcを配置
これで試したら。
通るじゃん！
74:37 AC
あとはＣとＥを行ったり来たりで時間切れ。
Ｃは10**6+3を加えて計算すれば何となくできそうなことはわかったけど時間切れ
Ｅは進展なしで時間切れ
結局A,B,D３完 74:37 0WA 769位でパフォ1464 レートは+19で1309
レートは上がりましたが、反省点の多い回でした。
・Ｄ：合ってるかどうかよくわからないからパス。
なぜ提出しなかった？
どうせわからないならペナルティ5分は痛くないはず
順位表を見て、そんなに難しくはないと判断できた点は良し
・Ｃ：途中でググったのは良し。
何やってる？
AGC034は参加できませんが、次回以降のコンテストに生かしましょう！
