AOJ 2717 Where is the Boundary
問題
Where is the Boundary | Aizu Online Judge
直線状にn個の県が並んだ国がある。
m種類の分類法があり、これによって各県は、'E'または'W'に分類することができる。
今、この国を'E'と'W'に分ける境界を決める。
m種類の分類法に対する誤差が最小になるような境界位置を求めよ。
解法
全探索する。
境界線を決めたとき、境界の左側にあるEの数と、境界の右側にあるWの数の和を求める。
この和が最小になる境界線が答えとなる。
ソースコード(C#)
using System; using System.Collections.Generic; using System.Linq; namespace _2717 { class Program { static void Main(string[] args) { int[] nm = Console.ReadLine().Split().Select(int.Parse).ToArray(); int n = nm[0]; int m = nm[1]; string[] d = new string[m]; for (int i = 0; i < m; i++) { d[i] = Console.ReadLine(); } int[,] e = new int[m, n + 1]; int[,] w = new int[m, n + 1]; for (int y = 0; y < m; y++) { for (int x = 0; x < n; x++) { e[y, x + 1] = e[y, x]; if (d[y][x] == 'E') e[y, x + 1]++; } } for (int y = 0; y < m; y++) { for (int x = n - 1; x >= 0; x--) { w[y, x] = w[y, x + 1]; if (d[y][x] == 'W') w[y, x]++; } } int ans = int.MaxValue; int bound = 0; for (int x = 0; x < n + 1; x++) { int tmp = 0; for (int y = 0; y < m; y++) { tmp += e[y, x] + w[y, x]; } if (tmp < ans) { ans = tmp; bound = x; } } Console.WriteLine("{0} {1}", bound, bound + 1); } } }
ISUCON6本戦で昨年来の夢を叶えた #isucon
ISUCON6本戦で昨年来の夢が叶いました。
これです。
isuconの名刺、格好良さそうだから欲しい
— ゆー (@yu3mars) 2015年10月31日
かっこいいですからね。
ISUCONとは
いい感じスピードアップコンテスト。 webサービスが与えられるので頑張って高速化します。 詳しくは公式サイトを読んでください。
今回のお題は、pixiv Sketch。
チーム
チーム「:innocent:」として参加しました。
順位表での表示は😇になっていました。まさか本当に置換されるとは思っていませんでした。
運営の方がわざわざ対応してくださいました。ありがとうございました。
画像は1位を獲得した瞬間です。
私を本選に連れて行ってくれた素敵なチームメイトの記事はこちら。
やったこと
- rack-lineprofileを使うもログが残らず失敗
- Azureでポートを開く
- nginxでHTTP2対応
- nginxで静的ファイル配信を試みるも失敗
- Redisでキャッシュを試みるも型エラーを起こし失敗
- DBの構成をSlackに張り付けて眺める
- N+1問題を解消するためクエリを改造する
結果
23位 3177点
当初の目標である正の点数を取ることに成功しました。
初期点数 3907点 を一度も超えることができなくて残念……
前日の様子
- nginx実践入門を購入
- ヒカリエ侵入訓練
- 当日集合時間決定ミーティング
- 例によってruby実装をベースに頑張ることを確認
当日の様子
- 8:50に到着。名札を獲得。会場は半分くらい席が埋まっていた。
- 会場のレゴを撮影する。
- 持参したルービックキューブで遊ぶ。
- 競技開始。PVにざわつく。
- 参加チームがことごとくデプロイに失敗する。4コア*5台でAzureの制限に引っかかった?
- 2コア*5台に構成が変更される。
- 高速にデプロイ。ベンチを回し暫定1位を獲得(最初にベンチを回したので自明)。
- nginxの設定をする。
- アプリをDockerから出すことを検討するも、Docker爆破コストを考え、そのままにする判断をする(結果的には引き摺り下ろしたほうが良かった)。
- rack-lineprofileを使うもログが残らず、眼力でボトルネックを調査し始める。
- 方針が立たなさ過ぎてDBの構成をSlackに張り付けて眺める。
- get_ほげほげ がN+1問題を引き起こしていることが分かっていたので、改善に取り組む。点数が初期実装を超えられなくて謎。
- nginxで静的ファイル配信を試みるもfail。原因究明に失敗したため、切り戻し。
- Redisでキャッシュを試みるも、キャッシュが返す型がキャッシュでないものと変わっており、型エラーを起こしfail。終了直前まで粘るも解決できず。
- 絶対に正の点数を取りたかったので終了10分前に切り戻し。再起動実験は時間がないのでしなかった。
- 😇 ←この顔になった。
- 懇親会で他チームの方針を聞いて知見を深め、交流した。
感想
自分の実力不足を改めて痛感しました。
次回があれば、本選で名札を獲得して、有意な貢献ができるようになりたい。
Webサービスに関して、ある程度全体の雰囲気が分かるようになった(気がする)のは収穫。
運営の皆様、参加者の皆様、そしてチームメイトの2人に感謝です。
おまけ
Iikanji Syokuba-sagasU CONtest 個人的に開催中です。 いい感じの職場情報があればお知らせください。
ISUCON用 便利コマンドを雑にリストアップしてみただけ
ISUCON超初心者向けに、使いそうなコマンドをひたすら並べただけの記事です。
他の人の記事だと当たり前すぎて書いていない内容を補完するスタンスで書きました。
具体的なファイルの設定は各自ググってください。
ssh
ssh ユーザー名@IPアドレス -i 公開鍵のディレクトリ
sysctl
sudo vim /etc/sysctl.conf sudo /sbin/sysctl -p
memcached
redis-server
sudo apt-get install redis-server
立っているプロセスの確認
service --status-all
nginxの設定
sudo vim /etc/nginx/nginx.conf
動かせるサービスの確認
ls /etc/systemd/system
サービスが動いているかの確認
sudo systemctl status サービス名
サービスの起動
sudo systemctl start サービス名
TopCoder SRM 700 Div2
Xylophone (Easy)
問題
TopCoder Statistics - Problem Statement
方針
やるだけ。
7の剰余で分類して、それぞれ使われているか数えればよい。
ソースコード(C#)
class Xylophone { public static int countKeys(int[] keys) { bool[] b = new bool[7]; foreach (var i in keys) { b[i % 7] = true; } int ans = 0; for (int i = 0; i < b.Length; i++) { if (b[i]) ans++; } return ans; } }
XMarksTheSpot (Med)
問題
TopCoder Statistics - Problem Statement
方針
全探索。
まずは盤面を調べる。
'O'の上下左右の端を調べて持っておき、'?'の位置を調べて持っておく。
'?'が'O'であるか'.'であるかを全通り場合分けして試す。ビット演算を使うとよい。
ちなみに?の場合分けをする際、毎回盤面を調べているとシステムテストで落ちる。
ソースコード(C#)
using System; using System.Collections.Generic; class XMarksTheSpot { public static int countArea(string[] s) { int ans = 0; List<int> qx = new List<int>(); List<int> qy = new List<int>(); int l = int.MaxValue; int r = int.MinValue; int u = int.MaxValue; int d = int.MinValue; for (int i = 0; i < s.Length; i++) { for (int j = 0; j < s[0].Length; j++) { if(s[i][j]=='?') { qx.Add(i); qy.Add(j); } else if (s[i][j] == 'O') { l = Math.Min(l, j); r = Math.Max(r, j); u = Math.Min(u, i); d = Math.Max(d, i); } } } for (int bitcnt = 0; bitcnt < (1<<qx.Count); bitcnt++) { int ltmp = l; int rtmp = r; int utmp = u; int dtmp = d; for (int qcnt = 0; qcnt < qx.Count; qcnt++) { if (((bitcnt >> qcnt) & 1) == 1) { ltmp = Math.Min(ltmp, qy[qcnt]); rtmp = Math.Max(rtmp, qy[qcnt]); utmp = Math.Min(utmp, qx[qcnt]); dtmp = Math.Max(dtmp, qx[qcnt]); } } ans += (rtmp - ltmp + 1) * (dtmp - utmp + 1); } return ans; } }
XYZCoder (Hard)
問題
TopCoder Statistics - Problem Statement
方針
DP。
順位が下の人間から見ていき、
順位を決めた人間の数、部屋内での優勝者が決まった数をキーにしてDPすればよい。
最後に、優勝者の順列を出すために、部屋数の階乗を掛ける。
適宜modをとること。
DPの雑なイメージはこちら。
| 使った人数＼部屋トップが決まった人数 | 0 | 1 | 2 | 3 | ||||
|---|---|---|---|---|---|---|---|---|
| 6 | 1 | 5 | 9 | 5 | ||||
| ↑ | ↗ | ↑ | ↗ | ↑ | ↗ | ↑ | ||
| 5 | 1 | 4 | 5 | 0 | ||||
| ↑ | ↗ | ↑ | ↗ | ↑ | ↑ | |||
| 4 | 1 | 3 | 2 | 0 | ||||
| ↑ | ↗ | ↑ | ↗ | ↑ | ↑ | |||
| 3 | 1 | 2 | 0 | 0 | ||||
| ↑ | ↗ | ↑ | ↑ | ↑ | ||||
| 2 | 1 | 1 | 0 | 0 | ||||
| ↑ | ↗ | ↑ | ↑ | ↑ | ||||
| 1 | 1 | 0 | 0 | 0 | ||||
| ↑ | ↑ | ↑ | ↑ | |||||
| 0 | 1 | 0 | 0 | 0 |
ソースコード(C#)
class XYZCoder { public static int countWays(int room,int size) { long ans = 1; long mod = 1000000007; long[,] dp = new long[room * size + 10, room + 10]; //member,winner dp[0, 0] = 1; for (int member = 1; member <= room*size; member++) { for (int winner = 0; winner <= room; winner++) { if(winner>0 && member >= winner*size) { dp[member, winner] = (dp[member - 1, winner] + dp[member - 1, winner - 1]) % mod; } else { dp[member, winner] = dp[member - 1, winner]; } } } ans = dp[room * size, room]; for (int i = 1; i <= room; i++) { ans = (ans * i) % mod; } return (int)(ans % mod); } }
AOJでC#を快適に使うための(バッド)ノウハウ
本記事では、AOJで快適にC#を使うための(バッド)ノウハウを紹介します。
warningを無視する
AOJでは、warningが出るだけでCEにされます。
1つ未使用の変数があるだけでCEになるのは非常につらい。
対策
以下の1行をコードに追加します。
これが記述された行より下の行で発生するすべての警告を無視します。
位置は冒頭がおすすめ。
#pragma warning disable
System.Numerics を使わない
これです。
using System.Numerics;
AOJでは使えない模様。
ちなみにAtCoderでは使えます。
対策
あきらめる。
C# 5 以上の機能を使わない
こんなコードは書けません。
using static Hoge; class Program { static void Main(string[] args) { int i = a(3); } } static class Hoge { public static int a(int x) => x * 2; }
対策
あきらめる。
class Program { static void Main(string[] args) { int i = Hoge.a(3); } } static class Hoge { public static int a(int x) { return x * 2; } }
おわりに
AOJ 1357 Squeeze the Cylinders
問題
Squeeze the Cylinders | Aizu Online Judge
n個の円柱があり、それぞれの半径が与えられる。
円柱は地面に沿って転がして動かせるが、円柱の順番は入れ替えられない。
一列に並んだ円柱を両側から壁で押したとき、壁同士の最短距離はいくらになるか求めよ。
解法
左側の壁がx=0にあるとする。
i番目の円柱のx座標は、左側の壁に接している場合、0～i-1番目の円柱に接している場合のうち、最も遠いもの。
右側の壁は、0～n-1番目円柱に接している場合のうち、最も遠いもの。
n<=500なので、全て調べても間に合う。
ソースコード(C#)
using System; using System.Collections.Generic; using System.Linq; namespace _1357 { class Program { static void Main(string[] args) { int n = int.Parse(Console.ReadLine()); double[] y = Console.ReadLine().Split().Select(double.Parse).ToArray(); double[] x = new double[n]; double xmax = 0; for (int now = 0; now < n; now++) { double nowx = y[now]; for (int bef = 0; bef < now; bef++) { nowx = Math.Max(nowx, x[bef] + Math.Sqrt(Math.Pow(y[now] + y[bef], 2) - Math.Pow(y[now] - y[bef], 2))); } x[now] = nowx; xmax = Math.Max(xmax, x[now] + y[now]); } Console.WriteLine(xmax); } } }
