2019年11月15日及び16日に行われた、ICPC 2019 Asia Yokohama Regionalに参加しました。nicklawさん(参加記はこちら)とNOSSさん(参加記はこちら)と私でチームEldoradoとして出場しました。結果は4完で65チーム中23位でした。 1日目 リハーサル前 いつもどお…

起きたら黄色になってました！ pic.twitter.com/f6KMCqxPEy— まほろば (@mhrb_minase) 2019年11月16日 AtCoder Beginner Contest 145でレートが2033と2000を突破し、黄色になりました。53分41秒で全完での色変でした。初めてのコンテストに出てから1年半とち…

グラフの単一始点最短経路問題を解くアルゴリズムとして、ベルマンフォード法が知られている。ダイクストラ法と比較すると、計算量を犠牲にして、コストが負の辺にも対応させたというような格好になっている。コストが負の辺は、単にコストが負というだけな…

問題ページ 解法 人々は整数時刻に座標を出発し、速度で正の方向に歩き続けます。よって、時刻から時刻まで座標を通行止めにするということは、時刻に出発した人は座標で通行止めに当たるということになります。人々が歩いている途中に通行止めに当たった場…

問題ページ 解法 ある列の格子点全てにバス停を置くと、任意のその列を跨いだ左右間の移動が可能となり、かつ総移動距離がマンハッタン距離と等しくなるようにできる。よって、左右独立に考えることができるようになるため、分割統治でこの問題を解くことが…

問題ページ 解法 2つの街が直接偶数メートルで繋がっているか、2つの街の両方から行き来できる奇数長の閉路があれば、またその時に限りクエリに対する出力はYESとなる。これは、重み付き（ポテンシャル付き）Union-Find木を使うと調べることができる。道路を…

問題ページ 解法 番目の木までを見たときの美しさの最大値とする。すると遷移は、その木を使わないときとなる。木を使う場合、を満たすに対して高々1本しか木を使えないという制限がある。よって、木を使う場合はこれを満たすものの中で最大のの次に遷移する…

問題ページ 解法 grundy数を考える。白石、黒石がともに0個のときこれ以上の遷移ができず、必敗であることが分かる。また、石は等しい個数同士を交換するか取り除くしかないため、最終的に必ずこの状態になる。よって、再帰的にgrundy数を求めることができる…

問題ページ 解法 0-9, A-J, a-j, S, Tの高々32頂点間の距離を幅優先探索で求める。このとき、A-J及びa-jは通り抜けてはならないことにする。0-9に0-9、A-Jに10-19、a-jに20-29、Sに30、Tに31の番号を割り当て、グラフを作る。数字を持っているかいないかの各…

ICPC2019 国内予選に参加しました。nicklawさん、NOSSさんと私のチームで4完41位、学内1位で予選突破しました。 チームメイトの参加記 ICPC2019 国内予選 参加記 - NOSSの雑記 やったこと A問題は縦方向の和のmaxなので私が秒で実装し、通しました。Bをnickl…

問題ページ - A - Darker and Darker概要行列のマス目が与えられる。各マスは白、または黒のいずれかに塗られている。全てのマスが黒色になるまで、以下の操作を繰り返す。 白いマスであって、黒いマスと辺を共有するマスを黒くする。 この操作が何回行われ…

コンテスト初参加から1年で青くなることができました！ pic.twitter.com/fND6dnbB5b— まほろば (@mhrb_minase) 2019年4月20日 先日行われたTenka1 Programmer Contest2019でレートが1657になり、青色に到達しました（なお執筆時点のレートは1642な模様）。30…

先日行われたAtCoder Beginner Contest 124に参加した。今回は、全てPython3で解いた。 A問題 問題ページ 解法は、愚直にシミュレーションをした。コードは以下の通り。 a, b = map(int, input().split()) ans = 0 for i in range(2): if a > b: ans = ans +…

合宿 始まりはいつも突然に 参加者 1日目 バチャ 夜 2日目 バチャ その後 さいごに 合宿始まりはいつも突然に2月6日21:07、横浜国立大学競技プログラミング部(YNUCPC)Slackに、山梨大学競技プログラミング部(YUCPC)から合同合宿の誘いが来てる旨を伝えるメッ…

問題ページ - B - Bonsai Grafting概要頂点の木と頂点の木が与えられる。木の辺は頂点と頂点を結び、木の辺は頂点と頂点を結ぶ。2つの木から頂点を1つずつ選んでそれらの頂点間に辺を張り、頂点の木をつくる。通りの頂点の選び方それぞれについて、新しい木…

問題ページ - F - Coins on the tree概要頂点の根付き木が与えられる。頂点の親はであり、である頂点が根である。この根付き木上で、枚のコインを用いて以下のいずれかの操作を合わせてちょうど回行う。 根にコインが置かれていない場合、新しいコインを根に…

問題ページ - E - すぬけ君の地下鉄旅行 / Snuke's Subway Trip概要個の駅があり、本の地下鉄路線がこれらの駅間を結んでいる。番目の路線は駅と駅の間を結び、会社によって運営されている。地下鉄の運賃は、同じ会社の路線に乗り続ける場合は距離にかかわら…

問題ページ - D - Nearest Card Game概要枚のカードがあり、各カードには整数が書かれている。高橋くんと青木くんが、高橋くんから交互にカードを1枚ずつ取っていく。個の整数が与えられる。高橋くんは書かれた整数が大きい方から、青木くんはに近い方から取…