ABC108
久しぶりに参加。
A - Pair
2で割って余りつかって奇数と偶数の数を割り出した後、かけ合わせればおわり
B - Ruined Square
頭の中で正方形描きながら、xの増加分をyに足して、yの増加分をxから引いて・・・と
順番に考えていって合計4回足し算引き算して終わり。
(x2, y2)→(x3, y3)のところで、間違えて(x1, y1)を基準にしたためサンプルが通らず。
よく読んだら気づけたのでOK。変数名が悪かったかも
C - Triangular Relationship
とりあえずmodで考える問題だろうなというところからスタート。
a,b,cをkで割った余りがx,y,zとすると、0<=(x+y),(y+z),(z+x)<2k-1であることから、
それらをkで割った余りが0になるパターンは、0かkのみ
さらに、x+y=kかつy+z=0のようなパターンは、x-z=kとなるが、0<=x,z<kであり
これらを満たすx,zの組は存在しない。
したがって、x+y=y+z=z+x=kまたは、x+y=y+z=z+x=0である
このとき、x=y=z=k/2または0
0であるパターンは、Nに含まれるKの倍数すべてであり、その個数の3乗
k/2であるパターンは、kが偶数の場合のみ存在し、N + K/2に含まれるKの倍数の個数
であり、その場合に存在する組み合わせは求めた個数の3乗
この2つを合計すると答えが出る
最初にk/3で考えてしまってサンプルが通らなかったりしてたけど、
通せた段階でのスコアはノーミスで7位だった
D - All Your Paths are Different Lengths
配点を見て絶望する。皆目検討がつかなず諦めかけていたが、10^6という条件が
引っかかったのでそこから考えてみることに
多重辺がOKなので、まずはシンプルに0,1の組み合わせを考える
その上に何がつながるか考えて、0,2を考えると、0-3まで網羅できることがわかった
ここで、最初の1→2の間の辺を、0,1,2にすると、たとえば上を0,3,4とすると
0→4と1→3で選んだときが同じになってしまい、唯一性を満たさない
ということで0,3,6にしてみると、これはうまくいきそうだが、そもそも
2^20で40本使って20本余った状態で、10^6を超えられるならばそちらのほうが
簡単だろうと思い、計算してみたところ本数に余裕があることがわかったので
それ以上は考えないことにした。
これにより、基本となるツリーが以下のように完成した
1 2 0
1 2 1
2 3 0
2 3 2
3 4 0
3 4 4
...
ここで、問題となるのは2の累乗の超過分である。
別のツリーを作って・・とやっていくとさすがに辺の本数が足りない
ここでまた20分ほど試行錯誤した結果、まずはLを2進数にすることを考えた
そして、0であるビットを示すものを前に、1であるものを後ろにして、
その切れ目の頂点からNまでを新しい辺でつないでやればよかったと考えた
ところが実際にコードを書いてみると、L-1の距離をもつルートはあるが、L-2が
満たせない場合があるなど、歯抜けになってしまうことがわかった。
ここで解決策が思いつかず、残り20分を切る。
結果的に、たとえばL=100であるとすると、
1 =(0,1)=2=(0,2)=3=(0,4)=4=(0,8)=5=(0,16)=6=(0,32)=7
という形が基本になる（カッコの中は辺の長さ、カッコなしの数字は頂点）
ここでまず、0-63までは網羅され、残りは36個である
その後、頂点6までは0-31をもっていることから、6-7を長さ64の辺でつないでやれば
よいことがわかる。この時点で、残りは4個である。
その後、3と7を長さ96の辺でつないでやれば、96-99を網羅することができ、
完成となった
これを一般化して、大きい頂点から順番に、そことNをつないだときの経路数が
Lを超過しないならば、現在の経路数+1の長さの辺でNとつなぐ、という操作を
繰り返し、ACのコードが書けた
実際には、脳内でぐちゃぐちゃやっていた部分のせいでつなぐ頂点を1個間違えたり
経路数+1の長さの辺でつなぐ、というところがうまく理解できていなかったり、
長さはLまでではなくL-1までだということがすっぽ抜けたりしていて間に合わず、
コンテスト終了の7分後に通過
途中で心が折れていなければ間に合っていたかもしれないなあというペースなので
純粋にくやしいですね
それはそれとして、パフォーマンス的には1600だったのでレートも上がって満足
次回からまたARCに挑戦するか、水色まではABCで頑張るかは未定
