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

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

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

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

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

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

葉から根に向かって最小値を更新していき、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>

ACPCの参加記です。 0日目 ひたすら新幹線で移動してました。 痛すぎてお尻4つに割れた— yebi (@sigsigma19) 2017年9月17日 郡山からズに移動する途中の電車は、ひたすら同じ風景が続いてて、やはり大悪魔や植物が競プロしてたり校内にセグ木が生えている大…

Country in Distortion | Aizu Online Judge 拡張Dijkstraの問題です。 各頂点に対して、頂点に到着した速度で次の辺へのコストが代わるので、今回はとして頂点からの距離を持ちます。 ここで注意しないと行けないのが、無向グラフかつコストが0の辺が存在す…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0212最短経路を求める問題ですが、道中に枚割引券を使うことができます。 として、拡張Dijkstraをやります。 は今持っている割引券の枚数です。 nowに対して、割引券を使う方と使わない方をqueにp…

大会前 いつのまにか自分のMacで参加することになってたので、環境整備係してました。 以前のチーム練習で、毎回include書くのはめんどくさいとわかったので、bitsを入れたりg++のバージョンを上げたりしてました。 チームメイトの素数うさぎ(@wk1080id)とし…

B: ツリーグラフ - AtCoder Regular Contest 030 | AtCoder頂点からなるツリーグラフが与えられます。 いくつかの頂点にはお宝があり、そのお宝をすべて回収し、最初の頂点に戻ってくるまでの最小コストを求める問題です。各頂点について考えます。 現在見て…

問題文:Sergeant Rian | Aizu Online Judge すべての橋を爆破する最短コストは、最もコストが掛かる島(葉ではなく、1から到達するまでに最もコストがかかる島)を爆破する順番を最後にすれば良い。 サンプルを最短コストになるように鉛筆でなぞると、最もコス…

コンテストに参加しなかったのですが、想定解ではない方法で解いたので記事にします。 ABCのD問題、重さを圧縮したらdpで解けるんじゃねと思ってやってるんですが無限にWAを生成してます。なぜ— yebi (@sigsigma19) 2017年5月2日解法は,重さの制約が特殊なの…

3月26~3月29日にかけて、KMC(京都大学マイコンクラブ)とNAIST、RiPProで行った合同合宿の参加記です。 全部書いてると長くなるので、コンテストの内容とかはおいおい書くつもりです。 1日目 2日目 3日目 最終日 まとめ 1日目 集合場所も知らず、準備も全くせ…

※一番PV数が多いので、ちょっと直しました(2020/5/24)例題として、 B - 書き換え（Rewrite）を使います。 まずはこのコードを見てください。 #include<bits/stdc++.h> using namespace std; int main(){ int N,M; cin >> N >> M; vector<int>V(N),T(N); for(int i = 0; i < N; ++</int></bits/stdc++.h>…

０日目 基本的に事務的な準備をしてました。 問題文や解法の議論に全く参加できなかったので、来年はそういう積極的に参加したい。 さて、明日のコンテストは立命勢の日ですが今年はなんと阪大勢とのコラボです!!☺️そしていつもよりコンテストが1時間長いで…

N!の約数の個数を数える問題。 の数字を片っ端から素数で割っていく。 は添字に素数を持ち、N!の素因数の数を持つ。 の値を初めて更新するとき()は、が含まれるからにしてる。 #include<iostream> #include<string> #include<cstdio> #include<algorithm> #include<stack> #include<queue> #include<vector> #include<cmath> #in</cmath></vector></queue></stack></algorithm></cstdio></string></iostream>…

制約がだったのでnext_permutationだと思ったけど違った。再起できれいに書けてAC。辞書順ってところに時間を取られすぎてしまった… #include<iostream> #include<string> #include<cstdio> #include<algorithm> #include<stack> #include<queue> #include<vector> #include<cmath> #include<utility> #include<set> #include<complex> #include<map> #define</map></complex></set></utility></cmath></vector></queue></stack></algorithm></cstdio></string></iostream>…

個人的にすごく苦しんだ。(同期はプログラミング始めて二ヶ月でACしてる) 偶奇に分けて、奇数なら2で割った値をに足す。 を2で割ると"偶数のペア"の数がわかるから、奇数にいくつ肉付けできるかがわかる。 （イメージは、奇数は(1+偶数)になっているから、'…

2017年になったので、ブログをはじめました。 競プロとか英語とかの備忘録になる予定です。