yukicoder contest 219 - gratan’s diary

なんかTwitter見たらあるらしかったのでなんとなく出てみました

初ゆきこ

問題：1～Z日目のうちX日目とY日目以外の日数を求めよ

実装

Z-(X<=Z)-(Y<=Z）と簡単にかけて良かった（こなみ）

問題：A/Bを小数点50位まで求めよ

考察：

これ面白かったです～

普通にやるとdouble型が18桁？くらいまでの精度なのでできません

筆算します。

問題：路線ABCが長さx,y,zで存在し、1の駅同士と、x,y,z駅でそれぞれに乗り換えられる。開始位置と目的位置から最短距離を求めよ

考察：

どうやっても解けそうですが、場合分けがかなりめんどくさそうなのでグラフに落としました。

0の駅(乗り換え用)と、Nの駅(逆側の乗り換え用)の頂点と、それぞれの路線の端点、開始目的位置、の10個の頂点を用意し適切に辺を作ってdijkstraしました。

乗り換え駅へ行くとき１，出るとき０など、０１で設定するとうまくいきます。

Atcoderの「すぬけくんの地下鉄旅行」で覚えたテクニックですね。

問題：N個の整数組c、dを分割する。全体のコストは、はじめの要素以外のdと、部分列の中の最小のcで計算される。最小化せよ

解けなかったので解説から

解説：

分割した部分列と、それをマージするためのダミー頂点を考えます

ダミー頂点と部分列をつなぐ辺は、cです。これは各部分列ごとに高々1つでよく最小のものになります。

部分列内の連結は、dで行います。

こうして頂点N個辺2N個から最小全域木を構築すれば解くことができました。

感想：

これ天才ですね。最小のcを取る操作が、うまくマッチしているところがなるほどと思いました。辺の数を制限できるなら最小全域木は構築が簡単なので積極的に使いたいですねー。

そのうちやります

問題：N個の異なる整数で、XORがXになる整数列を構築せよ。

1<=N,X<=10^5

1<=構築する整数<=10^5+5

考察：

まずXを普通に追加してそれ以外で0を作ることを考えました

有名な事実として4k～4k+3をXORすると0になるのでこれでN%4に圧縮して考えられそうです。N%4==0のときは、N-4までを4個セットで作ればよいでしょう

最大で10^5-4個を使用します。1~3は使えないので、4~10^5-1を使いそうです。

またX付近は残したいので、10^5+3までを考えればよいでしょう。

余った1,2,3,10^5+4,10^5+5,X,X^1を使ってうまく組み合わせると1,2,3,4個でXが作れます。

またX=1がコーナーになっていますが、X付近が自動的に残るので余る整数が

1,2,3,10^5,10^5+1,10^5+2,10^5+3,10^5+4,10^5+5

となり、自由度が上がり簡単に構築できます。