予鈴

競プロとか備忘録とか…

Codeforces Round #544 (Div. 3) D. Zero Quantity Maximization

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

A. Technogoblet of Fire の日本語訳

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

E-Union

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

NStextFieldをNSMenuに埋め込みたい。

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

数式(?)を逆ポーランド記法に変換して計算する。

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

D - Number of Amidakuji

問題 atcoder.jp 考えていたこと ・まではすぐにたどりつけたが、「正しいあみだくじ」の本数を求める方法がわからず。 ・からに推移できる。 解法 ・番目にいるときの、あり得るあみだくじの場合の数を計算する。 ・当たり前だけど、あみだくじの状態が決ま…

D - Christmas

問題 非負整数が与えられる。2つの文字に対して、N番目の文字列を とする。 下から文字に含まれる文字の数を求めよ。 beta.atcoder.jp 解法 ・各に対しての数と含まれるすべての文字の数を定義に従って前計算する。 ・再帰関数で含まれる文字数を計算するこ…

B - Neutralize

問題概要 個の数列が与えられる。個の連続する数字を選んで0にできる。の最大値を求めよ。 B - Neutralize 解法 動的計画法。 が最大値となる数列に含まれるか、あるいは0になるか二通り存在するので、 番目の数字を使った時までの最大値 番目の数字を使わな…

AOJ Sum of Integers Ⅱ

改めてみると解けるようになっていたのでメモ 問題文 Aizu Online Judge 解法 をやります。 数字iを見ているときに、k個の数字を使っていて、和がjのときの場合の数 でも解けますが、 k個の数字を使ってていて、和がjの時の場合の数 としても解けます。dpの…

Macのシステム容量が極端に増えるのをどうにかしたい。

題名通りですが、解決できたので自分用にメモ。 実行は自己責任でお願いします。 結論からいうとビルドファイルのキャッシュやiOSシミュレーターのキャッシュを削除すると40GBほど容量が増えました。 不可視ファイルを目に見えるようにする。 Terminalに貼り…

ACPC2018-参加記-

今年も参加しました。 Day 0 Day1 Day2 Day2 懇親会 Day3 最後に Day 0 移動中にHaskellをやっていました。関数型言語をやりたい&楽しそうだったのですが意外とむずかしい。。。継続していやっていきたい。 景色は相変わらずど田舎。 晩御飯はマルモ食堂で食…

Mujin Contest D - うほょじご

問題文 D - うほょじご 解く前に考えていたこと ・絶対これ考察するだけでしょwと思ってたら違った。 ・規則性を見出すことが全くできなかった。シュミレーションの選択肢を除外した。 正解 ・解答を見ると閉路を探し出すような解答になっていたが、わから…

ABC106 AtCoder Express 2

問題 D - AtCoder Express 2 解く前に考えていたこと 区間を数える典型なので、解き方は雰囲気で知ってた(実装はしてません)。 実装の際に盛大にバグらせたので戒めとして書きました。 解法 + クエリ先読みのオフラインアルゴリズムというらしい #include<bits/stdc++.h> us</bits/stdc++.h>…

ABC038 D - プレゼント

問題概要 D - プレゼント 解く前に考えていたこと ・AOJのマトリョーシカと非常に似ている。 ・ただし、この問題は制約がで解は部分点しか取れない。 ・LISであることは間違えないので、比較関数を書き換えて蟻本にあるのLISを書くがWA ・途中でpair型dpを更…

VimでIndentlineが動かなかった話

VimでIndentlineが動かなったのでメモ。 調べてみると、githubのIssueで報告されていました。 github.com 以下日本語でもメモを残しておきます。 まずターミナルで vim --versionを実行します。すると、以下のような画面が現れるはずです。ここで、-conceal …

ICPC 2018国内予選

国内予選に後輩(わたあめくん)と先輩とともに参加しました。 開始1時間前 大雨の影響で大学までの電車がなかったので、大阪の別キャンパスで参加することになる。 yebiが到着 → アナウンス「全館4時半で閉館です☆」(は?) わたあめくんと合流して、帰宅難…

vectorsのテンプレートを詳しく見る

はじめに vectorsテンプレート 可変引数テンプレート decltypeについて 参考 はじめに 競プロやってると、多次元のvectorをよく使うことがあります。非常に便利なんだけど、宣言がめんどくさい。 例えば、3次元のvectorを宣言しようとすると、 vector<vector<vector<int>>>v(10,</vector<vector<int>…

B - Construct Sequences

B - Construct Sequences 解く前に考えてたこと ・配列の要素数を超える大きい公差を持った等差数列を考えて、順列による差を相殺したい。 ・具体例を考えるも、一般化できずに死亡、特に、入力 の値によって、数列を構築しようとしたのが問題かもしれない。…

CS Academy No Prime Sum

問題概要 csacademy.com個の相異なる数字が与えられる。2つの和が素数にならないように数字を取り除くときき、最小の数と取り除く数字を答えよ。 解く前に考えていたいこと ・2つの色に彩色したい気分になった。しかし、グラフは木ではない。 ・グラフがたく…

RUPC day3: AA グラフ (AA Graph)

問題概要 https://onlinejudge.u-aizu.ac.jp/#/challenges/sources/VPC/HUPC/2869アスキーアートでグラフが与えられるので最短経路を求める問題。 個人的にすごく好き。 注意するとこ ○|○○○ ○|○G○ ○|○○○ この場合はうまく弾かないと行けない。 #include<bits/stdc++.h> u</bits/stdc++.h>…

CS Academy Array Removal

csacademy.com 問題概要 要素の数列が与えられ、要素のsubarrayが与えられる。 回連続する数列の和の最大値を出力する。ただし、subarrayの番目の数字は使えなくなる。 解く前に考えてたこと DP : 不可能そう。使えない数字が出るたびに引くと間に合わない S…

RUPC2018 参加記

RUPC2018に参加しました。 Day 0 Day 1 Day2 Day3 最後に Day 0 今回は作問チームに関わってもおらず、何も準備してません。ごめんなさい。 Day 1 家で寝てました。 Day2 ・立命館大学 プロジェクト団体 RiPP○が9時に来いって言われたので早起きした。 ・久…

D- People on a Line

D - People on a Lineコンテスト中に解けなくて悲しい思いをした問題。 コンテスト中に考えてたこと ・全点対最短路を求めることができたら良さそう。 ・有効辺のみなので、dfs(コンテスト中はDijkstraをした)時にusedとdを持つと解ける。 (つまりdfsごとに…

RiPProを休部する話

RiPProを休部することにしました。 ※この記事は完全にポエムです。 理由をメンヘラにならないように簡潔に書く。 ①留学の準備のために1日3,4時間ほど勉強する必要がでてきた。 留学のために2017年の前半を溶かしたといっても過言ではないので、留学はしっか…

D-塗り絵

D: 塗り絵 - AtCoder Beginner Contest 036 | AtCoder個の島があり、個の橋がある。 島を白または黒に塗っていく。ただし、両端の島を黒で塗ることはできない。 色の塗り方が何通りあるか求める問題です。グラフ上の頂点を、黒色で塗るか、白色で塗るかをメ…

D - Mixing Experiment

D: Mixing Experiment - AtCoder Beginner Contest 054 | AtCoder薬品をにする最小費用を求める問題。 制約も小さいので、でナップサックをすると解ける。 更新をを薬品の最小の比だと思い込んでて時間を溶かした。 具体的には、漸化式を int div=(int)gcd((…

D - 3N Numbers

D: 3N Numbers - AtCoder Beginner Contest 062 | AtCoder 以前解けなかった問題が、ヒントで解けるようになったので… 前半の要素と後半の要素の差を最大にすれば良い。 中間の要素(配列の添字だと)を最適に選べば良い。 PriorityQueueを使って、前半要素の…

Xcodeで<bits/stdc++.h>を使いたい。

Xcodeでを使いたい人向けへのメモ。 まずはターミナルを開いて、次のパスへ移動する /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/include/c++/v1 ここから、bitsの中身を拝借する。 mkdirコマンドでbitsというファ…

ABC 051 D - Candidates of No Shortest Paths

D: Candidates of No Shortest Paths - AtCoder Beginner Contest 051 | AtCoder無向連結グラフの最短距離 に含まれない辺の数を求める問題です。 含まれない辺 = 全点間最短経路を求めたときに、更新された辺 が含まれない辺ということがわかります。 の範…

B - PackDrop

葉から根に向かって最小値を更新していき、dfsで解くことができます。 シンプルで好きです。 #include<bits/stdc++.h> #define rep(i,n) for(int i=0;i<n;i++) using namespace std; #define mp make_pair #define INF 1e9 int ans=0; vector<vector<int>>edge(1001,vector<int>()); vector<int>cost(1001,INF); void dfs(int vertex){ if(edge[vertex].size()==0)ret…</int></int></n;i++)></bits/stdc++.h>