0x19f (Shinya Kato) の日報

主にプログラミング関連の話をします

7/5 マルチタスク

 

OS自作入門が15日目に入って, ついにマルチタスクの話に. いまいちGDTあたりが理解できてない. ちょっと見直してくる.

 

AOJ-ICPC

なんか最近今日のAOJ-ICPC!みたいな日報になってきているけれど, 構わず続ける. 他チームもちょこちょこACしていて頑張らねばと言う気持ち.

  • Dark Room | Aizu Online Judge [解答]
    じっくり考えてたら状態数2^16個しかないことに気づく. で, さらによーく考えたら最短距離を求める幅優先探索すれば良いことに気づく.

  • Manhattan | Aizu Online Judge [解答]
    地味に悩んだ. 基本的には斜辺の長さdの直角二等辺三角形をなすように配置するのがベストなのだけれど, d = 1.000のときのように格子点と格子点の中央に端点を配置して遠回りさせた方が距離が最大になる場合もある. 安定をとって, そういった配置も全て列挙した. 他の人の実行時間短いコードを覗いてみたらもっと簡単でも通るっぽい.

  • Magic Bullet | Aizu Online Judge [解答]
    3次元の点と線分の距離を求めれば, 球と線分の交差判定ができる. 2次元版は用意していたけど, 3次元版は用意してなかったので作った.

    github.com

  • Prowler | Aizu Online Judge [解答]
    無限にバグらせまくった. 現在地の座標(y, x)と向いている方向dと手をついている座標(hy, hx)の5つを状態にして拡張ダイクストラ. 状態の遷移は向きを左右に変える, 前へ進む, 手の位置を現在の手の位置から隣接するマスに動かすのいずれか. 現在地と手の位置が正しいかどうかを判定する関数を作って, 少し多めに遷移は試している. はまるポイントが多くてしんどかった. なお, Vとvを間違えたのは本当にしょうもないのでアレ. 意外と最近{ 0, 1, 0, -1, 0 }使う系の問題解いてなかったのでいい練習になったかも.

 

なんか気がついたらソフトウェア制作のリポジトリにメンバーからPRがきていて, ゲームのタイトル画面がいい感じになってた. こういうのほんとありがたいんだよなぁ. というわけでもうちょっとグラフィック綺麗にしますか.