天下一プログラマーコンテスト2016予選Aの参加日記
2完の141位/446人。さっさともう一問解けるようになりたい。
1~100の数のうち、3と5のいずれでも割り切れない数の合計を求めよ。
Console.WriteLine(Enumerable.Range(1, 100).Where(s => s % 3 != 0 && s % 5 != 0).Sum());
このFizzbuzz的難問が解ければ上位0.5%のプログラマのはず。
参考:どうしてプログラマに・・・プログラムが書けないのか?
N台の機器からなるネットワークがある。ネットワークは根付き木の形をしていて、機器0がルートである。このとき、機器間にPackDropという、0.01の確率でパケットを破壊する装置をいくつか置くことができる。子を持たない機器B(1)…B(M)それぞれに対し、機器0からの望ましいパケット到達率が与えられたとき、最少のPackDropの個数を求めよ。
なるべくルートの近くにPackDropを置くようにすればよい。
class Program { static void Main(string[] args) { var str = Console.ReadLine().Split(); var n = Int32.Parse(str[0]); var m = Int32.Parse(str[1]); var e = new List<List<int>>(); for (int i = 0; i < n; i++) e.Add(new List<int>()); for (int i = 1; i <= n - 1; i++) { var p = Int32.Parse(Console.ReadLine()); e[i].Add(p); e[p].Add(i); } var pd = new int[n]; for (int i = 0; i < n; i++) pd[i] = 0; for (int i = 0; i < m; i++) { str = Console.ReadLine().Split(); var b_ = Int32.Parse(str[0]); var c_ = Int32.Parse(str[1]); pd[b_] = c_; } foreach (var c in e[0]) Dfs(0, c, pd, e); var ret = 0; Dfs2(0, ref ret, 0, 0, pd, e); Console.WriteLine(ret); } static int Dfs(int prev, int idx, int[] pd, List<List<int>> e) { if (pd[idx] != 0) return pd[idx]; var ret = Int32.MaxValue; foreach (var c in e[idx]) { if (c == prev) continue; ret = Math.Min(ret, Dfs(idx, c, pd, e)); } pd[idx] = ret; return ret; } static void Dfs2(int prev, ref int sum, int val, int idx, int[] pd, List<List<int>> e) { sum += (pd[idx] - val); foreach (var c in e[idx]) { if (c == prev) continue; Dfs2(idx, ref sum, pd[idx], c, pd, e); } } }
文字列AiとBiがそれぞれN個与えられる(i:0~N-1)。アルファベットの順番を任意に変え、すべてのAiがBiより辞書順で小さくなるようにしたい。そのようなアルファベットの並びはあるか。ある場合は、辞書順最小のものを出力せよ。
アルファベット26文字をノードとするDAGを、Kahnのアルゴリズムを使ってトポロジカルソートをすればよい。入次数0の頂点集合を優先キューにすることで、最終的な解が辞書順最小になる。
static void Main(string[] args) { var edges = new List<List<int>>(); for (int i = 0; i < 26; i++) edges.Add(new List<int>()); var n = Int32.Parse(Console.ReadLine()); for (int i = 0; i < n; i++) { var str = Console.ReadLine().Split(); var astr = str[0]; var bstr = str[1]; var idx = 0; while (idx < Math.Min(astr.Length, bstr.Length) && astr[idx] == bstr[idx]) idx++; if (idx == Math.Min(astr.Length, bstr.Length)) { if (astr.Length > bstr.Length) { Console.WriteLine(-1); return; } continue; } edges[astr[idx] - 'a'].Add(bstr[idx] - 'a'); } var ret = new List<int>(); var inEdgeNum = new int[26]; for (int i = 0; i < edges.Count(); i++) foreach (var e in edges[i]) inEdgeNum[e]++; var que = new PriorityQueue<int>(); for (int i = 0; i < 26; i++) { if (inEdgeNum[i] == 0) que.Push(i); } while (que.Count() > 0) { var val = que.Pop(); ret.Add(val); foreach (var e in edges[val]) { inEdgeNum[e]--; if (inEdgeNum[e] == 0) que.Push(e); } } Console.WriteLine(ret.Count() == 26 ? ret.Select(v => ((char)(v + 'a')).ToString()).Aggregate((a, b) => a + b) : "-1"); }
重複のない大文字のアルファベットからなる無向木がある。この木の各頂点に接続する辺の本数は、4本以下である。
この木を100x100以下のマスで視覚的に表示せよ。
適当な根を選び、DFSで頂点を置いていけばよい。頂点数が26以下なので、距離を2^26、2^(26-1)、・・・と半分にしていけば、必ず重なることはない。表示する前に100x100に入るように整形する。
class Program { static long[] dx = new long[] { -1, 0, 1, 0 }; static long[] dy = new long[] { 0, 1, 0, -1 }; static void Main(string[] args) { var n = Int32.Parse(Console.ReadLine()); var edges = new List<List<int>>(); for (int i = 0; i < n; i++) edges.Add(new List<int>()); for (int i = 0; i < n - 1; i++) { var str = Console.ReadLine().Split(); var v = str[0][0] - 'A'; var w = str[1][0] - 'A'; edges[v].Add(w); edges[w].Add(v); } var posX = new long[n]; var posY = new long[n]; Dfs(-1, 0, 0, 1 << 26, 0, 0, posX, posY, edges); Clean(posX); Clean(posY); var ret = new char[53, 53]; for (int i = 0; i < 53; i++) for (int j = 0; j < 53; j++) ret[i, j] = '.'; for (int i = 0; i < posX.Length; i++) { ret[posX[i], posY[i]] = (char)(i + 'A'); } AddLines(ret, edges); Console.WriteLine("53 53"); for (int i = 0; i < ret.GetLength(0); i++) { for (int j = 0; j < ret.GetLength(1); j++) { Console.Write(ret[i, j]); } Console.WriteLine(); } } static void Dfs(int predDir, int prev, int idx, long dist, long currentX, long currentY, long[] posX, long[] posY, List<List<int>> edges) { posX[idx] = currentX; posY[idx] = currentY; var dir = predDir == -1 ? 0 : (predDir + 3) % 4; //avoid to go backward foreach(var next in edges[idx]) { if (next == prev) continue; var nextPosX = currentX + (dx[dir] * dist); var nextPosY = currentY + (dy[dir] * dist); Dfs(dir, idx, next, dist / 2, nextPosX, nextPosY, posX, posY, edges); dir = (dir + 1) % 4; } } static void Clean(long[] pos) { var values = pos.Distinct().OrderBy(v => v).ToList(); for (int i = 0; i < pos.Count(); i++) { pos[i] = values.IndexOf(pos[i]) * 2 + 1; } } static void AddLines(char[,] ret, List<List<int>> edges) { for (int i = 0; i < ret.GetLength(0); i++) { for (int j = 0; j < ret.GetLength(1); j++) { if (ret[i, j] != '.' && ret[i, j] != '-' && ret[i, j] != '|') { for (int dir = 0; dir < 4; dir++) { DrawLine(ret, i, j, dir, edges[ret[i, j] - 'A']); } } } } } static void DrawLine(char[,] ret, int x, int y, int dir, List<int> children) { var drawChar = dir == 0 || dir == 2 ? '|' : '-'; var curX = x + dx[dir]; var curY = y + dy[dir]; while (curX >= 0 && curX < ret.GetLength(0) && curY >= 0 && curY < ret.GetLength(1) && ret[curX, curY] == '.') { curX += dx[dir]; curY += dy[dir]; } if (curX >= 0 && curX < ret.GetLength(0) && curY >= 0 && curY < ret.GetLength(1) && children.Contains(ret[curX, curY] - 'A')) { curX = x + dx[dir]; curY = y + dy[dir]; while (ret[curX, curY] == '.') { ret[curX, curY] = drawChar; curX += dx[dir]; curY += dy[dir]; } } } }