AOJ0595 - Schedule

DPが出来なさすぎてつらいので練習

AOJ0595(Schedule)

コード

// 8種類の選び方 N日のスケジュール
int dp[8][1010];
const int mod = 1e4 + 7;

int getid(char c)
{
  if (c == 'J') return 0;
  if (c == 'O') return 1;
  return 2;
}

// 責任者が居ない場合を除外
void exclude(int now, int id)
{
  REP(i, 8) {
    if ((i & (1 << id)) == 0) {
      dp[i][now] = 0;
    }
  }
}

signed main()
{
  int N;
  string s;
  cin >> N >> s;

  REP(i, N) {
    // 一日目はJの参加が必須
    if (i == 0) {
      REP(j, 8) dp[j][i] = 1;
      exclude(i, 0);
    } else {
      REP(j, 8) {
        REP(k, 8) {
          // 前日に居た人が一人でも居なければ飛ばす
          if (j & k) {
            dp[k][i] = (dp[k][i] + dp[j][i - 1]) % mod;
          }
        }
      }
    }
    exclude(i, getid(s[i]));
  }
  int ans = 0;
  REP(i, 8) {
    ans = (ans + dp[i][N - 1]) % mod;
  }
  print(ans);

  return 0;
}

メモ

分からなかったのでJOIの解説を見ながら実装した.
dp[出席状況][何日目] = スケジュールの場合の数 を表す.
dp[k][i] = (dp[k][i] + dp[j][i - 1]) % mod は前日までの場合の数( dp[j][i - 1] )を足していく処理.
REP(j, 8) REP(k, 8) の部分で昨日の出席状況に合わせ,ありうる今日の出席状況を全列挙している.(ここでは責任者がいない場合は考慮していない)
そのあとのexclude(i, getid(s[i])) で責任者がいない出席状況のときの場合の数を0 にしている.

出席状況をbitで管理するのは面白いなぁと感じた.

こんな感じで1 が立ってるところは出席していると判断する.

I O J
0 0 0 0
1 0 0 1
2 0 1 0
3 0 1 1
4 1 0 0
5 1 0 1
6 1 1 0
7 1 1 1

exclude() の中で責任者がいない場合を判断するために論理和を使っている.
if (j & k) は前日に居た人が居なかったら飛ばす(鍵が無いので出席できないから)ところでも論理和を使って上手く判定している.

また配るDPは最後に足す処理があることが多いらしい.覚えておこう.

SuperCon2016に参加した話

Supercomputing Contest - Supercomputing Programing Contest Official Site

SuperCon2016の本選に参加しました.

キャンパスを間違えた

SuperConの会場は豊中キャンパスだったのですが,ぼくの調査不足により吹田キャンパスに行ってしまい,無限に時間を溶かしました.申し訳ないです.

大阪大学の学食は美味い

安くて美味しかったです.

色んな人にあった

みんな「THE・オタク」と言った感じで面白かったです.
ゲ・ドリンクくんは過度のストレスにより禿げてました.(マジ)
つよっしーくんは本名が「つよし」ではなかったです.
KO氏はデレステを片手でしていました.
うぃんじー氏はプロでした.
らて氏はルマンドの黄色と紫色の違いが分かるイケメンでした.

内容

n個の頂点,c色に塗り分け,d次の正則グラフの最短経路長の総和(ASPL)をなるべく小さくしようという問題.
SuperConなので東工大の「TSUBAME」を使って高速化しようみたいな感じです.
ぼくはそもそもグラフに関して疎く,今回の問題で沢山の知識を得ました.(ダイクストラ,ワーシャルフロイド,焼きなましとか)
言語はC言語(CUDA)を使いました. CUDAはGPUプログラミングに必要な環境で,TSUBAMEを使うためにはこれが必要でした.

方針としてはRandomに生成したグラフを重みの和が小さくなるようにつけかえていき,これ以上良くならなかったらASPLアスパラを計算して良くしていくという感じです.

ASPLはnが2048くらいになると死ぬほど時間がかかったので辛かったです.

結果

優勝は久留米高専の「GhostDiv」でした. そしてぼくたち沖縄高専「tsuraMI」は7位でした.つらみ.

4問目はなぜかぶっちぎりで1位でしたが,6問目は18位(最下位)など問題によって順位のブレがありました.
また,「GhostDiv」はGPU不使用でした.GPUを使わないチームは強いみたいな風潮があります.

感想

今回はjin先輩にコーディングなど任せっきりだったので,ぼくがやったことと言えばASPL高速化を考える(失敗したが)くらいしかしてません.反省しています.
そのためにはもっと競技力をつける必要があります.PCK,JOIがあることですし,蟻本等読んで勉強していきたいです.
来年は今年以上の結果を出せるようリベンジしたいです.

幸子輿水輿水幸子 輿水輿水幸子幸子

{ \sin (\alpha \pm \beta) = \sin \alpha \cos \beta \pm \cos \alpha \sin \beta }
{\cos (\alpha \pm \beta) = \cos \alpha \cos \beta \mp \sin \alpha \sin \beta }

AOJ0010 - Circumscribed Circle of a Triangle

計算するだけなんですけど,色々と面倒臭かった.

AOJ0010

参考:kanetaiの二次記憶装置

各点から円の中心までの距離(つまり半径)が全て等しいことを考える.

各点を { A(x_1, y_1)} { B(x_2, y_2)} { C(x_3, y_3)} と置く.
また中心の座標を{ P(x_p, y_p)} と置く.

半径が等しいということは

{ | \vec{PA}| = | \vec{PB}| = | \vec{PC}|}

これらを連立方程式として解けば{ x_p}{ y_p}が求まる.

連立方程式は以下のようになる.

{
\begin{cases}
\; 2(x_1 - x_2)x_p + 2(y_1 - y_2)y_p = x_1^2 + y_1^2 - x_2^2 - y_2^2 \\
\; 2(x_1 - x_3)x_p + 2(y_1 - y_3)y_p = x_1^2 + y_1^2 - x_3^2 - y_3^2
\end{cases}}

行列を用いて,

\begin{pmatrix} 2(x_1 - x_2) & 2(y_1 - y_2) \\ 2(x_1 - x_3) & 2(y_1 - y_3) \\ \end{pmatrix}

逆行列

\begin{pmatrix} x_1^2 + y_1^2 - x_2^2 - y_2^2 \\ x_1^2 + y_1^2 - x_3^2 - y_3^2 \\ \end{pmatrix}

の積を求めればよい.

また,半径の長さは先程の { | \vec{PA}| = | \vec{PB}| = | \vec{PC}|} どれか一つに代入して求める.

コード

#define sq(x) ((x) * (x))

signed main()
{
  int n;
  scanf("%d", &n);

  while (n--){
    double x1, y1, x2, y2, x3, y3;
    scanf("%lf%lf%lf%lf%lf%lf", &x1, &y1, &x2, &y2, &x3, &y3);

    double a = 2 * (x1 - x2), b = 2 * (y1 - y2),
           c = 2 * (x1 - x3), d = 2 * (y1 - y3);
    double e = sq(x1) + sq(y1) - sq(x2) - sq(y2),
           f = sq(x1) + sq(y1) - sq(x3) - sq(y3);

    double x = (1 / (a * d - b * c)) * (d * e - b * f),
           y = (1 / (a * d - b * c)) * (-c * e + a * f);

    double r = sqrt(sq(x - x1) + sq(y - y1));
    printf("%.3f %.3f %.3f\n", x, y, r);
  }

  return 0;
}

工藤忍は最高や!!ということをプレゼンした(LT)

こんにちは.kurokojiです. 今回は2016/5/12(Thur)に発表したLTについてです.

(記事にするの1ヶ月遅れたおじさんの顔)

スライド

LT

今まで一番楽しかった.自分が好きなことだからやっぱり楽しいよね.


以下忍の話

忍担当です

最初に手に入れたRの帽子を被った垢抜けないような格好(それはそれであり(画像は「工藤忍」でggったら分かると思う))から R+で前髪を出し,左足を後ろに上げ,とてもキュートな姿に瞬間にぼくは

尊い 優勝 天才 神

と感じました.

モバマス始めた

デレステからシンデレラガールズを知りましたが,Pになるにはやはりモバマスもやるべきではと思い,始めました.(結構前に) 最近やっと慣れてきた感じです.

第5回シンデレラガール総選挙

残念ながらランクインならずでしたね. 全て忍に投票したのですがモバマスは未だに無課金故に,ぼく個人の数が圧倒的に少なすぎました.反省点です.

しかし,忍が所属するグループ『フリルドスクエア』のメンバー「喜多見柚」が大健闘の全体11位,Pa4位でした.すごい.

この影響で忍のみならずフリルドスクエアメンバーの人気も上がってほしいです.

ということでね

これからも頑張りたいと思います.

AOJ0594 - Super Metropolis

問題見たとき幅優先かなと思い,実装したら間違ってて悲しくなったのでブログに残しておきます.

AOJ0594

右下と左上方向に移動するときは斜めの道が使えないので,マンハッタン距離の分だけ移動. それ以外は差の絶対値が大きいほうを取る.

コード

// テンプレは省略

signed main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  int W, H, N;
  int px, py;
  cin >> W >> H >> N;
  
  // スタート地点
  cin >> px >> py;
  int ans = 0;
  REP(i, N - 1){
    // ゴール地点
    int nx, ny;
    cin >> nx >> ny;
    // 右下と左上に行くときはマンハッタン距離の分だけ移動する
    if (px > nx && py < ny || px < nx && py > ny){
      ans += abs(px - nx) + abs(py - ny);
    } else {
      // 斜めの道を使うときはX,Yそれぞれの差の絶対値が大きいほうを取る
      ans += max(abs(px - nx), abs(py - ny));
    }
    // スタート地点の更新
    px = nx; py = ny;
  }
  print(ans);
  
  return (0);
}

Ubuntu14.04 LTSでIntuos CTL-490を動かす

こんにちは.kurokojiです.最近はUbuntu16.04LTSがリリースされましたね.

さて今回は『Ubuntu14.04でIntuos CTL-490を動かす』という記事ですが,まず

Intuosってなんやねん

ってことですよね.

Intuosとは

Intuos」は、このたび従来のIntuos5からモデルチェンジ したIntuos Proと、従来のペンタブレット製品である BambooがモデルチェンジしたIntuosからなるペンタブレット・ブランドです。プロフェッショナルの使用を前提とした Intuos Proと...
Intuos | Our People | Wacom


ペンタブです

姉になぜか買ってもらいました.ありがとうございます.

Ubuntuで動かす

ここからが本題なのですが,ぼくの持っているIntuos CTL-490Ubuntuで刺しただけでは動きませんし,公式がUbuntu用のドライバを配布してません.なんかwacom製のは動くって聞いたけど動きませんでした.残念.

そこで諦めるわけにはいかないので,なんとか動く方法を探しました.
Ubuntu intuos ctl 490」でググるこんなのがありました.

try to install this driver...
download from the link: http://sourceforge.net/projects/linuxwacom/files/xf86-input-wacom/input-wacom/input-wacom-0.30.0.tar.bz2
unzip the file
open the terminal and go to the directory
run:
・ 4.1 - ./configure
・ 4.2 - make
・ 4.3 - sudo make install
plug the wacom tablet and be happy!
it worked for me!
Ubuntu 14.04. 2 does not recognize my Wacom Intuos tablet draw (ctl-490b)

簡単に訳せば,

  • ここからドライバをDLしてね
  • 解凍してね
  • ターミナル開いてね
  • 解凍したディレクトリに移動して
    • ./configure
    • make
    • sudo make install すると

ペンタブ使えて幸せになれるよ!!!!

ということです. その通りにやって再起動すると動きました.やったぜ.
英語に屈せずにちゃんと読んでよかったです.

GIMPとかも筆圧検知して動いてくれます.筆圧ONにする方法はググってください.
以上です.