概要 解いたEDPCの問題を一言のコメントとともに貼っていきます。 感想＋解答 A - Frog 1 典型。類題がたくさんある気がする。解答 B - Frog 2 これ好き。 最短経路問題。 解答 C - Vacation 典型。いつものやつ。 解答 D - Knapsack 1 典型。いつものやつ。…

問題 atcoder.jp 考えたこと ・愚直に辺をつなぐと間違いなくTLE. 辺を追加するクエリを頂点とみなすか、実は全部辺を考慮する必要がないかのどちらかだと思った。 ・任意のの2頂点間はで接続することができる。 ・したがって、「辺を追加する」という区間と…

Problem Problem - D - Codeforces Solution ・Excluding the building power plant, it is clear that getting MST is answer. ・finding that which power plant is efficient is difficult. (e.g. greedy algo is not correct.like this) also, if we bui…

解き直したら解けなかったので、ここで供養します 問題文 atcoder.jp 解法 頂点について考える.と鉄道で連結な頂点集合,高速道路で連結な頂点集合をとする. 求めるべき答えは を満たすの個数である. 頂点集合を構築するにはunionfindを用いればよい. の個数…

問題 atcoder.jp かなり考察したのに解けなかった。悔しいのでここで供養します。 考察 ・を使いたいとすると、用いることができるスポーツはを満たすような ただし、その他の行で何が一番になるか比較するのは計算量的に怪しい(と思う) ・あるに着目してか…

問題 atcoder.jp 以下では、最も大きな桁を1番目として考えてます。あとこの記事はかなり備忘録寄りになってます 考察 ・ひと目みて桁DPだと気づいたよ。すっかり忘れていたのでこのサイトで復習した。 ・余りが5である必要があるので、各桁について余りを管…

問題 長いので、リンクを踏んでください atcoder.jp 考察 ・にない文字がに含まれる場合は明らかに-1 ・部分列で構成しなければいけないので、単にに使う文字が出てくるまでを増やすのはダメ ・1時間ぐらい考えて二分探索が生える。ここから4時間ぐらい溶か…

問題文 都市についての数列が与えられ、これらは都市の0時との時差である。 都市との時刻の差の最小値をとするとき、の最大値を求めよ。 ※日本語が崩壊してる気がするので問題文を読むことをおすすめします。atcoder.jp 解く前に考えていたこと ・読解に少し…

問題 要素のdequeue が与えられる.push_back,push_front,pop_back,pop_frontを合計回行うことができる。 取り出した要素の和を最大化せよ。 atcoder.jp 解法 ・push,popを貪欲に決めるのは難しいそう。例えば負の要素は取りたくないが、あえて取ることで後ろ…

問題文 個の数字が与えられる。各数字に対して+1,-1を行う事ができる。uniqueな数字の数を最大化せよ。 考えていたこと ・AtCoderでやった問題だ！と思ったけど違った ・は、またはの数を増やすことができる。の数が3以上ならばどちらも増やせる。2だとどち…

2020年度の情報科学区分の受験記です。 数多くの受験記に助けられたので、誰かの役に立つように記そうと思います。結果は合格でした。 試験内容 書類審査 英語 数学 小論文 試験当日 服装とか当日の様子とか 数学 面接 その他 OC・見学会について 役に立つか…

問題 atcoder.jp 考えていたこと ・を問題文中での悪い虫の頂点集合、を高橋くんとする。 ・を含む部分グラフとを含む部分グラフに分ける最小カットを考えればいいことがわかる。 ・の要素をすべてに置き換えて最大流を流す → ”ログインできなくなる”という…

この記事は完全にポエムです。有益なことは多分ありません。 AtCoderを初めて3年近くで水色になりました。 ﾔｯﾀｾﾞ 水色になるまでやった*1ことは、他の方々が詳細に書いてくださってるので、失敗したことや心構え的なことを書きたいと思います。 1.コンテスト…

問題文 atcoder.jp解き直すと別の解法で解けたので書きます。 解法 ゲームには貪欲法が存在し、からに向かう頂点を埋めていくのが最適です。 与えられるグラフは木なので、任意の頂点に関して、がただ一つ存在します。 したがって、に含まれる頂点のうちどれ…

問題 解き直すと一瞬で通って悔しすぎるので、ここで供養しようと思います。 codeforces.com 解法 問題文に与えられた式を整理すると、 任意の正の有理数は、ただ一つの既約分数を用いて表せるという性質を用いる。 mapのkeyを のような文字列としてカウント…

問題文が理解不能すぎたので訳しました。間違ってたらコメントください。 というか訳しても意味がよくわからないけど codeforces.com coderトーナメントがもうすぐ開催されます。 校の学校が参加し、各校につき1人の選手だけが参加することができます。すべ…

Problem atcoder.jp Solution ・愚直解は、に対し、各個使ってシュミレーションが考えられるが、計算量的に間に合わない。 ・配列を次のように定義する 数字を個使ったときの場合の数 ・更新は ・更新した値をもう一度更新しないように、後ろから更新してい…

Problem atcoder.jp Solution ・愚直解は、に対し、各個使ってシュミレーションが考えられるが、計算量的に間に合わない。 ・配列を次のように定義する 数字を個使ったときの場合の数 ・更新は ・更新した値をもう一度更新しないように、後ろから更新してい…

この記事は備忘録です。 NStextFieldをNSmenuに埋め込んで、上のstatus barから入力受け取れたらいいんだけどな〜って思ってたんですが、どうやらバグ*1でできないらしいです。 具体的には、一度focusが離れると入力を受付なくなるらしい… なにか良い解決策…

面白そうだな〜と思っていたので、実装しました。 要するに電卓です。 10+4*(10/2+7)/2+2+(3+(2+2)) ←こういうのを計算してくれます。負数と小数点には対応してません。 楽しかったので自己満足記事です。verifyはしてないので、使用は自己責任でお願いしま…