AtCoder Grand Contest 035
ばんわー。
AGCめっちゃ事故りましたシクシク
配点が3-7-7の時点で無理そうだなって感じはしてました。
だって700点以上で通してるの4問しかないし。
でも絶対無理って感覚ではないから精進で可能性はありそうです。
800点以上は知らん。
A XOR Circle
問題：N個の整数が与えられる。右隣と左隣のXORが自らの整数と一致するように、環状に並べられるか調べよ
考察：
・a,b,c,d…と並んでいるとする
・a^c=b、b^d=cを解くとa=dとなる
・任意の箇所で上記のことが言える
・N%3=0のときは、a,b,cの3種類を順番に並べるため、3種類かつ出現回数が同じ必要がある
・a^b=cとなるように注意する
※c++では(a^b)==cのようにしないと計算順序の関係でバグる。
・N%3=0のときb=0のときに限りa,a,bでもよい
・2*x=yのときなぜかyのほうが小さいと勘違いする。中学生かな？
・それ以外のときは全ての要素が一致する。
・a^a=aのときa=0である
・1種類かつ0であるときがYes
感想：
・無限にバグってた。
・pythonで書いたときにa^b=c、a^a=a、a^b=a && a^a=bの条件を忘れてたところから沼が始まった。
・焦って700解くどころじゃなかったので落ち着いて300を考える
・300通らず700通すのは自分には無理そう
B Even Degrees
問題：N頂点M辺の単純無向グラフが与えられる。任意の頂点の出次数が偶数になるように向きをつけろ。
考察：
・Mが奇数なら自明に構築できない
・次数が1の頂点では、入る側になる
・また構築の途中で次数が1になった場合どちらかに決まる
・次数が2以上の頂点しかないときどうすればよいか。
自分の実装：
・適当に決めたら順次決まりそう（雑考察）
・当然嘘っぽいけど、反例が出てこずに、ちゃんとした考察も伸びずに終わり
解説：
・逆にどの状況なら出次数を調整できるかを考える
・辺が1つあれば調整可能
・各頂点辺を1つ持つ→根付き木っぽい
・また入力から必ず木が構築可能であることはわかる
・根は調整不可では？
→全ての辺を処理すると、必ず偶数になる。
・なぜならば、辺の数は偶数で、根以外の頂点は偶数になっているので、根も偶数になる。
・根付き木を除いて適当に決めて、根付き木を使い調整すればよい。
・根付き木で、辺が１つしか残っていない頂点から順次決めるのは、自分の考察と同じ
感想：
・落ち着いて考察できなかったのもあるが、雑すぎた
・制約から木を考えるか、木が便利だから構築してみるか、あたりがとっかかりなのかなあ。難しいです。
C Skolem XOR Tree
問題：頂点2Nの木を構築せよ。ｉからｉ＋Ｎのパス上のＸＯＲがｉになるようにせよ。
考察：
・ほぼ考察できませんでした
・結構難しそうだったからＡＢに注力した(なお結果）
解説：
・2*k＾(2*k+1)＝１かつ、1は必ず出現するためＮ＝奇数のときは簡単に構築できそう
・ただし１－１＋Ｎのパスをどうするか初めに考える
・2^3=1、1^2=3、1^3=2は%4が循環することを知っていればわかる
・まずこれを作っておく
・次にＮ＝偶数のとき構築できるか考察する
・簡単に考えればbit分割すれば良さそう
・偶数を分割すると偶数が2つ出るため、パスに必ず他の数字が入ってしまう
・また長めのパスを考えるとＸＯＲが１になるやつが入りそうだから短めで構築したい
・偶数ー1ー奇数の形を考える
・Ｎ＋１をbit分割する
・Ｎ＋１に2つ以上bitが立っている必要がある
・ただし１を使うことはできないため、1以外に2つbitが必要
・つまりN=2^kのときは構築不可能。
・上でN>=3に限り初期状態を構築したが、1,2の場合が構築不可能であることもこの処理で排除できる。
・適当にbit分割し、1と隣接するように気を付けながらＮ，２Ｎをつなげばよい。
感想：
・限りなく簡単な例を考える
・はじめ％4を１セット考えたが、多分%４=０,1,2の場合でも詰めれば解けた気がする(ほんとか？)
・考察、実装含めて時間がかかる問題だったので(少なくとも今の自分では)、Ａを素早く解く力が求められたと思う。
Ｄ以降はやりません
自分語り：
129分1完という酷い結果で、パフォ848でした
なんということでしょう
2019年の2月からAtCoder始めたんですけど、1番パフォ低いという。
半年頑張ったのに寧ろ点数は落ちてましたみたいなオチを期待されて実現してしまいました。
まあ、今までは上手くいったコンテストばかりでしたし。（大事故起こしたABC126や、divertaはunratedになり助かりました。）
たまには下振れする回もあっても仕方ないなーとか思ったり、そこまでショックではないです(強がり）
まずはABCが安定を目指して600を埋めます。
今は解説見ないでできなかったら他って感じなので、準備期間って感じ。
解説読んで理解して通す、通したやつをやり直して精度を上げるとかすると実力が伸びると思ってます。知らんけど
AGCやってみて700～800埋めるくらいまでは青で停滞しそうとか思った。エアプです。いじめないで。
てかrated減るから黄色になるインセンティブちょっと薄いですよね。
青はどうしてもなりたいって思えたんですけど、なんか青になってからはあんまりレートの変化に感情が動かないです。
とはいえ、できない問題ができるようになるのは、今まで通りとても楽しいので精進頑張りたいなと思います。
いや院試勉強しないとマズイですよ！
じゃあね
