チーム紹介
Ponjuice : 構築とか実験して嬉しい構造を見つける系の問題が好き
Series_205 : AGCで得たレートをARC参加者に配る仕事をしています
hir35 : 構築とかが好き チームメイトより400ぐらいレートが低いです
戦略
事前に用意したものはatcoder,他の様々なライブラリをexpandするものぐらいで変なものはたいして用意をしなかった
戦略としては1問目はPonjuiceがとき、B以降は印刷物がくるまで右画面に表示している問題文を都度進めて解き進める感じで進める
問題
A Ponjuice
n*(n-1)/2の二乗で終わり。
0分で通せてるところは何者ですか?
B Series_205
入力が小さいので、全探索。
C hir35
setで重複を除きつつやる
土曜日と日曜日の定義は書かなくていいのかなあなどと思いました。
D Ponjuice
最初、実装で詰まってしまって一回Eにパソコンを譲りました。よくよく考えてみると左上の文字が0
になるように#.
を01
の配列に直すとはとのxorになっているのと、1行目と1列目で.#
が入れ替わる頻度が明らかに間違ってないことが条件でこっちで書き始めると意外とすぐ終わった。(最初に実装始める前にもう少し詰めればよかったかもだが、順位表見てるとそこまで悪くない?)
E Series_205
問題文に字が多すぎる!これを英語でやられると困ります。
その頂点にいなければならない時刻を考えると、木DPになる。各頂点の親が与えられるのでDFSすらいらない。
本来なら一瞬で解けるはずだったが、変数名を取り違えて終了。
たぶんEFをデバッグしている頃にやっと紙の問題文をゲットした。チーム数が多い大学の弱点。
F hir35
それぞれの操作は最初にある(A/B)の塊を一個右にずらす操作と思える。
数が違うとどう見てもダメで、他は可能だと信じてやると、後ろから合わせていけることがわかる
復元ミスって1ペナ
コーナーあってもう1ペナ(すみません、、)
G Ponjuice
サンプルを見てみる側面は基本三角形であるが、四角形になった分だけ麺の数が減っている。
四角形にできるのは辺が平行になるときだけであるが、平行である時に確実に平面になるかどうかがよくわからない。Fが終わったタイミングで他に解けていた問題がなかったため一応これを書いてみて出してみるとAC
H Series_205
G が書かれている間に hir35 と考察を進めると、普通に解けそうということに。
とりあえずランレングス圧縮をする。
2以上に出られるかが重要で、あとは偶奇しか関係ない。そのへんを頑張って計算すると、残りは ()()(
みたいな文字列と等価で、これは自明。
(()()))
みたいなやつは、どこからでも ((
や )))
に出られるので、()()
の分を別で足す必要がないことに実装中に気付いて、えらい。
I Ponjuice
Hを書いてもらっている間にhir35で一緒に考察。
同じ数字をswapすることはないので1~Nの数字がそれぞれ2つずつある問題に直すことができることまではいけるが、その先が苦しい。隣り合っている数字をスワップしたいのは 1221のようにそれぞれの数字を結んだ線が交差してない時なので区間の中でペアができてる数字を探したくなりMo'sを書こうとする。実装中、Seriesからセグ木で後半部分を解けるよと言われ、0~N-1までの数字が二つずつになるように変換するところまで書いてSeriesと交換。最初にint n; をしていることを忘れ n*(n-1)/2
をして1ペナ。
全完後
それぞれ解いてない問題を読んで解法の共有や反省をしたが、時間は余った。ただ、順位表がかなり熱く、AMATSUKAZEが最後全完した瞬間には科学大から5チームいけるかと思ったが、その次の瞬間提出がでた。科学大からyokohamaに5チームの希望も一瞬で終わった...(来年はワンチャンないかな?)
感想
-
Ponjuice
実装より考察の方が多い問題が多かった(そこをたまたま担当していた?)割に実装する人が途切れることなくそこそこ早く全完することができていてかなり満足。最近、競プロ以外に浮気することが多く、ちょっと自信がなかったが思っていたよりも活躍できたようで良かった。 -
Series_205
Eのミスはバカすぎたが、バカすぎてサンプルすら通らずノーペナで済んだので耐えた。横浜は難易度的にも英語という点でもここまで調子よくはいかなさそうだが、チャンスはかなりあると思う。精進します。 -
hir35
しょうもないペナを出してしまったので、注意力を高めていきたい。チームメイトの皆様ありがとうございます。