trsing’s diary

勉強、読んだ本、仕事で調べたこととかのメモ。

AtCoder Beginner Contest 126参加メモ

問題増えた!目標は3+\alpha

atcoder.jp

結果

A,B,CはAC。Dは方針決まったけど実装まで至らず。E,Fは問題ちょいみ。

後日、D,Eは自力でAC、Fは解説見てAC。

C:Dice and Coin

intで割り算して「あれ???」となっていました。初心者かよ。

D:Even Relation

例えばa-b-cとなっている場合、ac間の距離を求める必要はない。 aの色を決める、a-b間の距離でbの色を決める(偶数ならaと同じ色、奇数なら別の色)、b-c間の距離でcの色を決める(偶数ならbと同じ色、奇数なら別の色)とすればいい。

グラフ作成してどっか適当なノードの色を決め、そこから全探索。自ノードの次のノードとの距離で次のノードの色を決めていく。

グラフ作成するには・・・重みもいるし・・・えーと・・・複数グラフの接続も・・・と悩んでいるうちに時間切れ。残念。

E:1 or 2

後日ちゃんと問題を見てみると、

  • X,Y,Zからはカードに書かれた数字が決まらない
  • 同じグループの場合、1枚カードの数字がわかればほかのカードの数字もわかる

ということに気づいた。グループの数が魔法の使用回数ということ。グラフ作成すればグラフの数がグループの数になる。

※グループ
1 2 Z1
2 3 Z2
とあれば1,2,3は同じグループ。

F:XOR Matching

範囲にペアになるやつがあれば0になるからKを対称に挟めば(abc K cba)・・・あ、もう一個Kあるな。K以外でKを作れれば(K K' K K')・・・いや残りがあるから残りが上手く相殺できるならK abc K' cba K K' (abc=0))・・・えーとこんな都合のよいものになるかどうやって判定すればいいんだ・・・??

わからん。ちょっと視点を変えて各桁のビットに注目してみると・・・どれも2^{M-1}個になるのか・・・こっからKを・・・わからんもぅマヂ無理解説みょ・・・

\displaystyle{
\oplus_{i=0}^{2^{M}-1}i=0
} (各桁とも1の数が偶数個(2^{M-1})のため)

これからKを抜くにはKでxorを取ればよく

\displaystyle{
\left( \oplus_{i=0}^{2^{M}-1}i \right)  \oplus K=0\oplus K=K
}

おお・・・おお・・・

というわけで
K以外を適当に並べる(1) K 1を逆順に並べる K
とすればよい。

所感

実装力が・・・実装力が足りない・・・。