AtCoder Beginner Contest 115 D - Christmas
全完やったああああ！（初めてかもしれない） AGCも頑張るぞおおお（白目）
問題
多次元バーガーは以下のようなものです。
- レベル0バーガーとは、パティ1枚である。
- レベル
バーガー
とは、バン1枚、レベル
バーガー、パティ1枚、レベル
レベルバーガーを作ったときに、下から
枚を食べると、何枚のパティを食べることができるか。
解説
レベルバーガーの構成は以下のようになる。
ここで、がどこまで伸びているかによって食べられるパティの枚数は変わってくるので、場合分けして枚数を数えてみる。
レベルで食べることのできるパティの枚数を
とすると、以下のように場合分けできる。
が真ん中のパティより上もしくは同じ位置の時
= (
+ 1) + (真ん中のパティより上側のレベル
バーガーで食べることのできるパティの枚数)
= (レベル
バーガーで食べることのできるパティの枚数)
後はそれぞれのレベルについて食べられるパティの枚数を、その時のに応じて数え上げると答えが求まる。
ここで、レベルバーガーを食べる時も、同様に数え上げることができるので、レベル
バーガーを下から
枚食べた時のパティの枚数を数えることができる。
ただし、端のバンや、終了条件を注意して実装する必要がある。
提出
（書き直してないので、汚いです。ごめんなさい。。。）
感想
全完はうれしかった。誰か褒めてくれると喜びます。
ちなみに本番はこんな感じだったよ。
同じことを繰り返すだけなので、再帰で書いてもループで書いても大差ないと思うけど、バーガーの構成が再帰的になってて綺麗だから、再帰で書きたくなる。
↓
バグる
↓
∑(O_O；)
↓
ミスに気付く
↓
バグる
↓
Σ┌( ┐*ロ)┐
↓
...
みたいなことを8回繰り返しました...（あほすぎる）
モチベーション上がってきたので、競プロ頑張りゅ～ （ゆるキャンの物販行ってきたのでバイアスがかかっています）
CODE FESTIVAL 2016 Final C - Interpretation
解法
ある人とある人の間に辺が貼ってあるか、ある人とある人が連結であることがわかればよい。ここで、UnionFindを使いたい気持ちになるので、どうにか使えないか考える。
ここでは、問題の入力例1を元に考えることにする。
この図を縦に見ると、ノードが同じ言語に並んでいる場合は、一つ目の条件である「2人ともが話すことの出来る言語が存在する」を満たしている。
また、１人目が３人目とコミュニケーションを取るためには、２人目を経由する必要があるが、これは図で表すと次のようになる。
赤色の矢印の両端の人はコミュニケーションができる。水色の矢印の両端はが話せる言語である。
この時、AとBがを経由してコミュニケーションを取ることができる時、AとBにパスが存在する。
水色の矢印については、同じ人がコミュニケーションを取ることができるとみなせるので、統合する必要はない（自己ループは考えない）。
赤色の矢印については、両端の人でコミュニケーションを取ることができるので、両端の人を統合し、一つのグループを作る。
あとは、人の参加者が同じグループに入っているかを調べれば、全ての参加者とコミュニケーションを取ることができるかを調べられるので、この問題が解ける。
おわりに
UnionFindの練習にはちょうどいいかも。
富士山やああ富士山や富士山や
一応この記事はこちらのアドベントカレンダーに貼り付ける記事ですが、まぁ書く人が少ないので、旅行記としてゆるふわに書こうと思います。
1日目: 箱根→御殿場→須走
実は昨年、御殿場まで1日で走ったのですが、今年は須走まで走ることになりました。まぁ、これが割としんどい。。。（´。＿。｀）ゞぅぅぅ…
僕が作ったルートではないですが、こんな感じでした。
latlonglab.yahoo.co.jp
正直芦ノ湖半周したあたりで、足が残ってなかったですね...（最近引きこもってたからね）
この日のおすすめポイントは、何と言っても長尾峠！
車も少ないし、左側の景色を楽しめながら登れるので僕は好きですね。あと、静岡側の下りがくねくねしてて楽しいですよ>_<
2日目: 須走→富士五湖→富士宮
「11月の朝寒すぎ... ε＝（‐ω‐；；）まぁ、漕げばあったまるやろ」
とかほざいていたら、早速峠へ。(｡_｡`)ﾁｰﾝ
だましだまし登って、山中湖へ。
うーん曇ってる...
今日は富士山見えなかったら見所が無くなる気がするんだけど...
西湖
通過。雲が晴れてきて、富士山見えそう。
精進湖
一部界隈にうけそうな湖。うーん湖飽きてきたなw
本栖湖
ここは行きたかった！理由はオタクだから*1
*:.｡.(❁´ω`❁).｡.:*
はい、オタク乙。
それはそうと雲が晴れて、千円札の富士山が見えました。
溢れでる日本感 (´ω｀)
本栖湖を一周して、富士宮へ。
途中で白糸の滝を見ようということで、寄ってみました。思ったより迫力があったので、近くに寄った際は是非。（湿度120%ぐらいあった）
最後に
富士山見すぎて飽きた。
ARC 047 B - 同一円周上
備忘録。
解説AC
考察
マンハッタン距離が等しい点をとると、菱形のような形になる。これは解説の図がわかりやすい(12ページ)。https://www.slideshare.net/chokudai/arc047-57126901
arc047 from AtCoder Inc.
www.slideshare.net問題の解説にもあるが、この図形を45度回転させて正方形を作ることで今後の処理を楽にする。
この時の座標変換は(x, y) → (x + y, x - y) となる。
あとは、各辺を見ていって、正方形の中心を求めて、それぞれの頂点について確認すればおーけー。
典型かどうかはわからないけど、覚えておきたいアイディアだなと思った。
Maximum-Cup 2018 C - 嘘つきな天使たち
備忘録です。
問題文
解法
二部グラフかどうかを判定すれば良い。
次の性質を用いることができる。
二部グラフ奇数長の閉路を部分グラフとして持たない
証明はここ。
#include <bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<(b);++i) #define erep(i,a,b) for(int i=a;i<=(int)(b);++i) #define per(i,a,b) for(int i=(a);i>(b);--i) #define eper(i,a,b) for(int i=(a);i>=b;--i) #define pb push_back #define mp make_pair #define INF (1<<30)-1 #define MOD 1000000007 #define all(x) (x).begin(),(x).end() using namespace std; typedef long long ll; typedef pair<int,int> Pii; template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; } template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; } int dy[]={0, 0, 1, -1}; int dx[]={1, -1, 0, 0}; int gcd(int a,int b){return b?gcd(b,a%b):a;} int lcm(int a,int b){return a/gcd(a, b)*b;} int n, color[100005]; vector<int> g[100005]; bool dfs(int v, int c) { color[v] = c; rep(i, 0, g[v].size()) { if (color[g[v][i]] == c) return false; if (color[g[v][i]] == 0 && !dfs(g[v][i], -c)) return false; } return true; } int main() { cin.tie(0); ios::sync_with_stdio(false); cin >> n; rep(i, 0, n) { int a; cin >> a; a--; g[i].pb(a); g[a].pb(i); } rep(i, 0, n) { if (color[i] == 0) if (!dfs(i, 1)) { cout << -1 << endl; return 0; } } cout << n/2 << endl; return 0; }
AtCoder Regular Contest 006 C - 積み重ね
問題文
C - 積み重ね
解法
Greedy. 重ねられるところまで重ねてあげて、無理だったら地面（？）に置く。できるだけ重ねてあげれば山の個数を最小にできる。
#include <bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<(b);++i) #define erep(i,a,b) for(int i=a;i<=(int)(b);++i) #define per(i,a,b) for(int i=(b);i>(a);--i) #define eper(i,a,b) for(int i=((int)(a));i>=b;--i) #define pb push_back #define mp make_pair #define INF (1<<30)-1 #define MOD 1000000007 #define all(x) (x).begin(),(x).end() using namespace std; typedef long long ll; typedef pair<int,int> Pii; template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; } template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; } int dy[]={0, 0, 1, -1}; int dx[]={1, -1, 0, 0}; int gcd(int a,int b){return b?gcd(b,a%b):a;} int lcm(int a,int b){return a/gcd(a, b)*b;} int n; int main() { cin.tie(0); ios::sync_with_stdio(false); cin >> n; vector<int> w(n), a; rep(i, 0, n) cin >> w[i]; rep(i, 0, n) { bool flag = true; int dist = INF, itr = 0; rep(j, 0, a.size()) { if (a[j] >= w[i]) { flag = false; if (dist > a[j] - w[i]) { dist = a[j] - w[i]; itr = j; } } } if (flag) a.pb(w[i]); else a[itr] = w[i]; } cout << a.size() << endl; return 0; }
macbook pro を買った話
これは coins Advent Calendar 15日目の記事です。
13日目の記事は 普段歴史に触れない人へ - 歴史とプログラムの狭間 です。
coins Advent Calendar 2017 の Adventar は こちら
龍馬伝、懐かしいですね。親の影響で見ていました。機会があれば再履修したいです。
自己紹介
先に自己紹介を。coins17のdonkoといいます。最近寒すぎてサムスになりそうです、はい。
Twitterアカウントは@donko_ITF です。
情弱なのでプログラミングとか全然できません。精進します。
はじめの一歩
この記事は新しくPCを買う人に読んでもらいたいというより、これから入学するであろう新入生に読んでもらいたいなぁ、と思っています。というのも、大学に入ってから「PC買おう」と思って適当になものを買って、あとで悲しい気持ちになるのは嫌ですよね。(まぁ、わいがそうなったからこんな記事を書いているわけですけれども...)
というわけで、ここからは私の二代目PCちゃんを買った時の話です。
目的はしっかりとね
先ずは、自分がこれから何をしたいのかを明確にするべきですね。(一番の失敗点はここだったと思います)
最近、サークル関係で動画編集などのためにAdobeのソフトウェアを使う必要性が出てきました。学割とか効かせると年間2万ちょっとで利用できるそうです。
当時、僕が持っていたPCのメモリは4GBのDDR3-1600。MS Wordを開くだけでWindowsがフリーズする始末。無論PremiereやAEを使おうものならどうなるか容易に想像できます。(Ubuntuをデュアルブートしてしのいでいました)
うーん、渋い...
この時点で思考が買い替える方向に振り切れました。
なににする？
もうフリーズする画面に手を合わせるのは嫌だったので、メモリは16GB以上でストレージもそこそこあると安心だろうと思い、500GB以上という条件の下で探してみたところ、いろいろ見つかりました。
ありすぎて困るぐらいには。
細かいところを比較していくと、CPU・GPUとかバッテリーとか操作性とかとか。これ以上は個人の好みかなと思います。
いろいろ考えた挙句、私はMacbook pro 13 touch bar対応モデルの購入を決めました。
Apple on Campus
高い、高いよmac。どうにか安くならんのかと思ってググってみると、こんなプログラムを見つけました。
Apple On Campus (AOC) | 筑波大学 情報環境機構 学術情報メディアセンター
ちょっと安くなるみたいです。使うに越したことはないので、早速Appleコールセンターで買えるということだったので、Appleへ電話。(学内LANからならwebで購入可能)
お姉さんの指示に従って番号を入力後、しばらくすると担当者の方と思われるお兄さんが対応してくれました。そこでApple on Campusでmacbook pro を買いたい、ということを伝えました。大学名や学籍番号、メールアドレスを伝え、またマシンのカスタマイズも電話で伝えました。
内容確認のメールが届き、間違いないことを伝えて電話を終えました。
注文から商品の受け取りまでにちょうど1週間かかりました。カスタマイズすると上海からの発送になるようで、時間がかかるそうです。
思ったより使いやすいね
ずっとwindowsを使ってきたので、若干抵抗はあったのですが、ワークスペースの切り替えとか、Chromeで前のページをみたりするときとか、トラックパットの使い方を少し覚えただけでかなり便利になりました。まぁ、時々CapsLockとcontrolを間違えて、「あ...」ってなる時がありますが。。。
あれしたい、これしたい
これはPC選びとは全然関係ない話です。
一応coins AdventCalendar ということでフレッシュ(?)な話を一つ。
新入生説明会の時にから使いたいなぁ、っておもってた 「openfab 創房」
論理回路も授業でやってるし、創房で自作CPUをつくろうかなぁ、などと考えてます。
あとは、最近興味が湧き出したデータマイニングにも手を出してみたいと思います。
サークル関係ではゴリゴリ映像編集とかしたいですね。
終わりに
繰り返しますが、PCを買う前にはよくよく自分のやりたいことを考えて、明確にしましょう。そこそこのスペックで安けりゃいいや、みたいに考えてるとあとで後悔します（ソースはわい）。逆に、やりたいことがわかってたら最高の相棒に巡り会えると思います。
マシン選びは「楽しく、慎重に」ね！
