院試を振り返る
2021年度4月期入学で、京都大学情報学研究科通信情報システム専攻に合格しました。 結果は専門基礎Aが245点、専門基礎Bが294点でした。
学部の単位に追われて、準備期間は一か月程度しか取れませんでしたが、 コロナの影響で、授業が遠隔になったおかげで時間が取れて、ギリギリ何とかなった気がしてます。
専門基礎Aから4科目、専門基礎Bから4科目選択して回答するのですが、 時間がなかったので4科目ずつしか準備していかなかったら、かなりきつかったので、 時間が取れる人は5科目以上準備していって、当日の問題で4科目選ぶようにしましょう。
以下、選択の一助になれば、と思って書きます。 情報系なので、電気系科目のことはわかりません。
院試情報 <- 過去問
専門基礎A
A1:数学(微分積分、線形代数)
準備の時間があるなら選ばない方がいい。(私は全然取れませんでした…) 出題範囲が他の科目と比べて恐ろしく広いうえに、出題パターンも決まってないので、数学苦手な人がとるのは難しそう。
A2:数学(複素関数論、フーリエ解析、微分方程式)
出題範囲は広いものの、出題パターンは固定なのでおススメ。 ただし、留数の計算がきつい。
A5:情報理論
ほぼ満点が狙えるので、絶対取ったほうがいい。 出題パターンは固定なのでおススメ。 私はこれ一冊でやりました。
情報理論 改訂2版 | 秀樹, 今井 |本 | 通販 | Amazon
A7:計算機アーキテクチャ
ほぼ満点が狙えるので、絶対取ったほうがいい。 出題パターンは固定なのでおススメ。 範囲としてはパタヘネ上巻の前半7割ぐらいかと思います。
専門基礎B
B1:情報通信工学(情報伝送、通信ネットワーク)
電気系科目なのですが、出題パターンがしばらく同じなので選択しました。 (待ち行列周りの話と、OFDM周りの話と、通信ネットワーク周りの話しかしばらく出てない。) 実際、8割ぐらいとれたと思います。
B4:論理回路
ほぼ満点が狙えるので、絶対取ったほうがいい。 出題パターンは固定なのでおススメ。 私はこれ一冊でやりました。
論理回路 (New Text電子情報系シリーズ) | 高木 直史 |本 | 通販 | Amazon
B5:計算機システム
かなり範囲は広いですが、高得点が狙えるはずです。 出題パターンは固定なのでおススメ。(私は用語問題などで結構ひかれてそう。) 範囲としてはパタヘネ上巻の後ろ3割、下巻の前半ぐらいかと思います。
B8:計算と論理
範囲はあまり広くないと思います。 理解していれば高得点が狙える気がします。 ただし、去年から追加されたので、過去問が去年と今年しかないです。
C++ 組み合わせ列挙
#include <vector> using namespace std; vector<int> next_comb(int n, int k, vector<int> v){ for(int i = k-1; i >= 0; --i){ if (v[i] != i+n-k){ int t = ++v[i]; for (int j = i+1; j < k; ++j){ v[j] = ++t; } return v; } } for (int i = 0; i < k; ++i){ v[i] = i; } return v; } vector<int> v = {0, 1, 2}; for (int i = 0; i < 10; ++i){ for (int j = 0; j < 3; ++j){ cout << v[j]; } cout << endl; v = next_comb(5, 3, v); } /* 012 013 014 023 ... 234 */
私のためのMacキーボード設定
最近バイトの関係でMacを使うようになったのだが、キーボード入力の文化が違いがストレスだったので、MacをWindowsっぽいキーボード入力に設定したときの覚書
システム環境設定 > キーボード > 入力ソース
で以下3点を変える
ライブ変換をオフ
Macでは入力中にスペースを押さなくても予測変換の第一候補に変換してくれる。 私は変換したくない時に変換されるのが不便だったので外してある。Windows風のキー操作をオン
returnキー1回で確定されるようになる。Caps LockキーでABC入力モードと切り替えるをオン
Macでは入力ソースの切替ショートカットがデフォルトで(ctrl + space)になっているのだがとにかく素早く切り替えたいのでCaps Lock一発の方が私は馴染んだ。
)
E - Cell Distance
考えたこと
マスのうち任意に2マス選ぶと、その2マスの選び方は残りのマスの中からマス選ぶ選び方の個数回使われるということに気づけなかった。
#include <iostream> using namespace std; const long long mod = 1e9 + 7; long long modpow(long long a, long long n) { long long r = 1; // a^n = (n%2) ? (a^2)^(n/2) : a*(a^2)^(n/2) while(n) { r = r * ( (n%2) ? a : 1) % mod; a = a * a % mod; n >>= 1; } return r; } long long modcomb(int n, int k) { if ( n < 0 || k < 0 || k > n) return 0; k = min(k, n - k); //nCk = nC(n-k) long long p = 1, q = 1; while ( k > 0 ) { p = p * n-- % mod; // p = n*(n-1)*(n-2)...(n-k+1) q = q * k-- % mod; // q = k*(k-1)*(k-2)...1 } // 1/q = q^(p-2) (mod p) return p * modpow(q, mod - 2) % mod; } int main(){ int N, M, K; cin >> N >> M >> K; long long x = 0, y = 0; for (int d = 1; d < N; ++d){ x += 1LL * d * (N-d) % mod; } x = x * M % mod * M % mod; for (int d = 1; d < M; ++d){ y += 1LL * d * (M-d) % mod; } y = y * N % mod * N % mod; cout << (x + y) % mod * modcomb(N * M - 2, K - 2) % mod << endl; }
ABC126E 1 or 2
考えたこと
条件は
個のが与えられ、は偶数である。
なので、の偶奇が分かればの偶奇が一意に定まる。 そこで枝によって作られるグラフを考えると連結部分のうち一か所が分かれば、連結部分は一意に定まる。 よって枝によって作られるグラフの連結成分の個数を調べれば、 その回数分の魔法だけで各連結部分の偶奇が一意に定まることとなる。 実際にやることとしては、枝で繋がれている頂点同士を同一グループに分けて、そのグループの個数を調べればいいので、union-find木でAC。
#include <iostream> #include <vector> #include <set> using namespace std; const int MAX_N = 1e5; int par[MAX_N + 10]; int size[MAX_N + 10]; int rankrank[MAX_N + 10]; void init(int n){ for (int i = 0; i < n; i++){ par[i] = i; size[i] = 1; rankrank[i] = 0; } } int getRoot(int x){ if (par[x] == x){ return x; }else{ return par[x] = getRoot(par[x]); } } void unite(int x, int y){ x = getRoot(x); y = getRoot(y); if (x == y) return; if (rankrank[x] == rankrank[y]) { par[y] = x; size[x] = size[x] + size[y]; rankrank[x]++; }else if (rankrank[x] < rankrank[y]) { par[x] = y; size[y] = size[x] + size[y]; }else if (rankrank[x] > rankrank[y]) { par[y] = x; size[x] = size[x] + size[y]; } } int getSize(int x){ return size[getRoot(x)]; } bool isSame(int x, int y){ return getRoot(x) == getRoot(y); } int main(){ int N, M; cin >> N >> M; init(N); for (int i = 0; i < M; ++i){ int x, y, z; cin >> x >> y >> z; --x; --y; unite(x,y); } set<int> s; int ans = 0; for (int i = 0; i < N; ++i){ s.insert(getRoot(i)); } for (auto ite = s.begin(); ite != s.end(); ++ite){ ans++; } cout << ans <<endl; }
ABC126D Even Relation
考えたこと
求めるグラフの条件は
同じ色に塗られた 任意の 2 頂点について、その距離が偶数である。
であるが、任意の2頂点間の距離を求めて、すべてが偶数かを確認する必要はない。 なぜなら考えるグラフは木なので、閉路を持たず、各頂点間の距離は適当に選んだある根からの距離で一意に表現できるからだ。(実際、(1)を見れば一意に表せることがわかる。) そこで 頂点iと頂点jの距離を、根をとすると
と表せる。
が偶数であるという条件について考えると(1)より
すなわち が偶数であることはとの偶奇が一致することと同値であることが分かる。
よってやることは
根と各頂点との距離を求めて()、の偶奇で01を出力すればよい。
#include <iostream> #include <vector> using namespace std; const int MAX_N = 1e5; struct edge{ int to, weight; }; vector<edge> Edges[MAX_N + 10]; int dir[MAX_N]; void dfs(int vertex, int parent, int distance){ dir[vertex] = distance; for (auto e : Edges[vertex]){ if (e.to == parent) continue; dfs(e.to, vertex, distance + e.weight); } } int main(){ int N; cin >> N; for (int i = 0; i < N-1; ++i){ int u, v, w; cin >> u >> v >> w; --u; --v; Edges[u].push_back(edge{v, w}); Edges[v].push_back(edge{u, w}); } dfs(0, -1, 0); for (int i = 0; i < N; ++i){ if (dir[i] & 1){ cout << 1 << endl; }else{ cout << 0 << endl; } } }
ABC126C Dice and Coin
考えたこと
愚直に各の確率を求めればよい。 以下のコードだとだが、テストケースの 14.txt だけどうしても通らず…。 なにか間違っているのか、それとも精度が足りないのか…。
#include <iostream> #include <math.h> #include <iomanip> #include <algorithm> using namespace std; int main(){ double N, K; cin >> N >> K; double ans = max( 0.0, 1.0-(K/N) ); for (long long i = 1; i <= min(K, N); ++i){ ans += 1.0 / ( N * pow(2.0, ceil( ( log(K) - log(i) ) / log(2) ))); } cout << setprecision(15) << ans << endl; }
そこで、制約を確認すると
であるので
計算量のはなし - Hello Wor.log
等を参考にするとか程度であることが予想できる。
各Nに対して、何回2をかければKを超えるかはで求まるので、結局以下のコードでで求められてAC。
#include <iostream> #include <iomanip> using namespace std; int main(){ int N, K; cin >> N >> K; double ans = 0; for (int i = 1; i <= N; ++i){ int num = i; int counter = 0; while (num < K){ num*=2; counter++; } ans += 1/(double)(1<<counter); } cout << setprecision(15) << ans/(double)N << endl; return 0; }
ついでに
入出力ストリームで浮動小数点型の桁数を指定しないと、勝手に丸められるので注意。デフォルトは6桁
#include <iomanip> ... // 少数点以下2桁に固定 cout << fixed << setprecision(2) << 3.1415 << endl; // "3.14"