SRM 504.5の練習会に参加。結果はeasyとmedをそこそこ高得点で通してhappyでした。 問題 TopCoder Statistics - Problem Statement 解法 まずある程度以上の数は必ず作ることがわかります(4と7は互いに素なのである程度大きい数からは連続して作れるようにな…

問題読んだ時さっぱりわからなかったけど解説読んで目からウロコだった。 問題 Problem - 547C - Codeforces 解法 各クエリに対して,数aに注目しているとすると,gcd(a,b)が1になるものの数は, aの素因数がp1, p2, ..., pmと書けるとして, (p1〜pmのうち0個の…

問題 TopCoder Statistics - Problem Statement 解法 適当に実験してるとなんか漸化式が出てくるのでそれで解いても良い。…が,どうもしっくりこないのでDPを使ってちゃんと解いてみる。まず前提となる考え方から。 ある人aに嫌いな人がいて,さらにその嫌いな…

Looksery Cup 2015に参加しました。結果的にADHを通しました。レーティングは大幅に上がったのでハッピーです。この問題は本番全く意味がわからないままサンプルを頼りにして通したんですが解法見て感動しました。 問題 Problem - 549H - Codeforces 解法 B…

意外に大したことない。 問題 Problem - E - Codeforces 解法 すこし考えれば難しいアルゴリズムは何も必要ありません。まず最後が1の時は絶対にムリ。 また,最後から3番目までずっと1で最後から2番目,1番目が0のときもムリ(これは帰納法的に示せる)。 それ…

問題読んだ直後は(これは解けないな…)と思っていたので解き方がわかった時はすごくテンション上がった。良い問題。 問題 TopCoder Statistics - Problem Statement 解法 いつも通り状態を保存するように深さ優先探索しても状態数が多すぎて間に合わない。と…

SRM練習会に参加しました。結果はeasyをそこそこ早解きしただけです。medが面白い問題でした。 問題 TopCoder Statistics - Problem Statement 解法 それぞれの町iについて,最高で何人の住人が集まれるのかを考える。これは,町i以外の町について人口をソート…

問題 Problem - D - Codeforces 解法 奇数の場合は写真のようにすれば構成できる。偶数の場合は作ることは不可能(な気がする)。 あとで証明します。 uwiさんに教えてもらいました。@mayoko_ まず橋の個数がいくつでも、連結成分をまとめたものは木をなすから…

SRM 660に参加。SRM div1では多分初めてmedも提出したんですがeasyもmedも落ちて0点でした。 問題 TopCoder Statistics - Problem Statement 解法 いろんな方法があるっぽいですが枝刈り使った方法でやってみます。2つの点a, bを選んだ時の最高点数の指標と…

TCO15 Round 2Aに参加。遅いながらもなんとかeasy通して140ptくらいゲットしました。unratedで悲しいですね。 問題 ある数列mが与えられて,f(x)=x%m[0]%m[1]%m[2]...と定義する。 ある整数Rについて,f(1)+f(2)+...+f(R)の値はいくらか。 解法 f(x)の結果とし…