はじめに ※この記事は完全にポエムです。 CFで青色になった。 2週間ぐらい前に、CFで青色になりました。やったぜ。 ここまでの道のりは長かったし、競プロ始めた当時は青色になれるなんて思ってなかったので、とても嬉しいです。 やったこと CFの青色になる…
Problem You are given two string and of the length of . You can perform following operation : 1.selects some subset of positions of such that 2.selects a letter , and sets each letter in positions , to letter Minimize the number of operati…
Problem Problem - C - CodeforcesI could not solve problem A, so I have no rating change in this contest :( You are given an array of permutation of . You can perform the following operation any number of time : choose two-element such that…
Problem You are given a collection of non-negative integers. You can perform following operations: choose two distinct indices . If before the operation ,, then after the operation ,. Maximize Solution 英語書くの疲れたので、日本語でやりま…
この記事はなに？ ブログで解説を書くほどではないけど、空き時間で解法を５秒で思い出したい問題を挙げていきます。 この記事はなに？ CF C. Eugene and an array C. Dreamoon Likes Coloring C. Social Distance AtCoder A - Sorted Arrays A - 梱包できる…
英語の論文を読むとき、よくGoogle翻訳やみらい翻訳を利用するんですが、改行コードのせいでうまく翻訳できないことがあります。 改行を取り除かずに翻訳 改行を取り除いて翻訳した場合 これぐらい精度が変わります。 毎回手動で改行を取り除くのは手間なの…
概要 解いた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はしてないので、使用は自己責任でお願いしま…
問題 atcoder.jp 考えていたこと ・まではすぐにたどりつけたが、「正しいあみだくじ」の本数を求める方法がわからず。 ・からに推移できる。 解法 ・番目にいるときの、あり得るあみだくじの場合の数を計算する。 ・当たり前だけど、あみだくじの状態が決ま…
問題 非負整数が与えられる。2つの文字に対して、N番目の文字列を とする。 下から文字に含まれる文字の数を求めよ。 beta.atcoder.jp 解法 ・各に対しての数と含まれるすべての文字の数を定義に従って前計算する。 ・再帰関数で含まれる文字数を計算するこ…
問題概要 個の数列が与えられる。個の連続する数字を選んで0にできる。の最大値を求めよ。 B - Neutralize 解法 動的計画法。 が最大値となる数列に含まれるか、あるいは0になるか二通り存在するので、 番目の数字を使った時までの最大値 番目の数字を使わな…
改めてみると解けるようになっていたのでメモ 問題文 Aizu Online Judge 解法 をやります。 数字iを見ているときに、k個の数字を使っていて、和がjのときの場合の数 でも解けますが、 k個の数字を使ってていて、和がjの時の場合の数 としても解けます。dpの…
