hogecoder

つたじろう(Tsuta_J) 競技プログラミングの記録

グラフ

PCK 2017 本選 5: 朝昼晩ごはん

この難易度帯にしては難しいなあと思ったら、自分の解法が想定と違った。 問題概要 日本語なので原文参照 → Aizu Online Judge 解説 人 と人 の食事の時間を同時に満たせるかどうかを考える。この判定は if 文で容易に行える。 さて、元の問題は「 に含まれ…

LeetCode Biweekly Contest 6: String Transforms Into Another String

問題概要 原文 → Loading... 文字列 と が与えられる。 以下の操作を 0 回以上行うことによって、 を と一致させることができるか判定せよ。 アルファベットをふたつ選び、それを とする。 に含まれる全ての を同時に へ変更する。 解説 操作をグラフとして…

Codeforces Round #540 Div.3 F1: Tree Cutting (Easy Version)

問題概要 原文 → Problem - F1 - Codeforces 頂点からなる木が与えられ、各頂点は赤・青のどちらかで塗られているか、何も塗られていないかのいずれかである。 木の辺を 1 つだけ取り除き、同じ連結成分内には色が高々 1 種類まで登場するようにしたい。これ…

Educational Codeforces Round 2 E: Lomsat gelral

問題概要 原文 → Problem - E - Codeforces 頂点からなる根付き木が与えられる。根は頂点 であり、木の各頂点には色 がついている。 各頂点 について、 を根とする部分木に存在する頂点の中で、塗られている個数が最も多い色を求め (タイもすべて数えるため…

Educational Codeforces Round 8 F: Bear and Fair Set

問題概要 原文 → Problem - F - Codeforces の倍数 と、整数 が与えられるので、以下を全て満たす正の整数集合を構築できるかどうか判定せよ。 要素数は で、値は全て 以下で相異なる の各元 について、要素を で割ったあまりが になるような、集合内の要素…

Codeforces Round #527 Div.3 E: Minimal Diameter Forest

問題概要 原文 → Problem - E - Codeforces 頂点からなる森が与えられる。このグラフに対して辺を追加して木を作りたい。木の直径が最小になるように辺を追加した時の、その直径の値と追加すべき辺を列挙せよ。 解説 森を木に分割して、木同士をマージするこ…

TopCoder SRM 716 Div1 Med (Div2 Hard): JumpDistancesOnTree

するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement 頂点からなる木がある。頂点 を起点として、いくつかの頂点に移動することを考える。集合 が与えられるので、頂点 の順に移動したときの隣り合う要素どうしの距…

TopCoder SRM 719 Div2 Hard:TwoDogsOnATree

するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement 頂点からなる木が与えられる。辺 にはそれぞれ重み が設定されており、パス のコストは、 と の間にある辺の重みの XOR と定義する。 与えられた木から、辺の重…

天下一プログラマーコンテスト 2016 予選 A C: 山田山本問題

hogehoge アルゴリズムのライブラリを貼るだけで解けるんじゃなくて、それにひと工夫加えないと解けない問題すき— tsutaj@進捗 6/35 (@_TTJR_) September 29, 2017 この手の問題すき。すきだから記事を書いてしまう。 問題概要 原文を参照してください → C: …

Google Code Jam Round 1B 2017 C: Pony Express

想定解法と違う方法で解いたので一応メモ。 問題概要 街が つあり、街 と を結ぶ道路の長さは (km) ( ただし の時は道路がないことを表す) である。 それぞれの街には馬がおり、街 にいる馬は時速 (km/h) で移動することができ、最大で (km) 移動できる。街…

TopCoder SRM 705 Div2 Med (Div1 Easy): AlphabetOrder

(追記: Div1 Easy と Div2 Med が完全に同じ問題なのでタイトルを変更しました) 今回のSRMは大勝利したので嬉しい。Medが個人的に良問だと思ったので記事を書きます。 問題概要 原文 → TopCoder Statistics - Problem Statement 英小文字のみで構成された文…

ICPC アジア地区予選 2014 F: There is No Alternative

今年ももう終わりですね。 問題概要 原文 → http://judge.u-aizu.ac.jp/onlinejudge/contest/ICPCOOC2014/F.pdf 重み付き無向グラフ が与えられる。 の最小全域木に必ず含まれる辺はいくつあるか? 重みの総和と共に出力せよ。 解説 まず、普通に最小全域木…