7/10 久しぶりに家でのんびり
日曜日, 月曜日と久しぶりに1日中家にいられる日が作れた. カレンダー見る限りだと家から出なかった日は1ヶ月ぶりぐらいらしい. OSAの課題と無線通信の課題を片付けて残りの時間はOS自作入門に当てた. かなり睡眠時間も確保できたし, 今週もがんばりませう.
AOJ-ICPC
-
Evacuation Route | Aizu Online Judge [解答]
最初はユニットが閉じられていく順番の逆順でUnionFindして〜みたいなことを考えていたけれど, どう考えてもダメっぽそうなので方針転換. 結局, 脱出可能な人数を左右から順番に見ていくだけということに気づく. 脱出可能な人数dを最初は0にしておいて左から順に, 出口に当たればd = INF, 防火扉ならd = -a[i]に更新して, ループの終わりでd--すればよい. これを左からと右から行い, 大きい方が脱出可能な人数.
- D: 25個の整数 - AtCoder Beginner Contest 025 | AtCoder [解答]
だいぶ前に解こうと思って, 解説見てわかんねーってなってた問題. 数字を小さい順にマスに入れていくと, どのマスに数字が入っているかの情報だけから次の数字をマスに書き入れられるかどうかが判定できる. なので状態数は2^20のbitDPをすればよい. 普通に0から1 << 25までfor文で状態を見ていくって方針でトライしたのだけれどうまくいかなかったのでdfsしてみた. 結構判定自体も煩雑でややこしいので, そこでミスったんだろうか.
7/8 DBの合格証書が届いた
DBスペシャリストの合格証書が届いた. これで, 基本/応用/DB全部取得したので実質星野源と言っても過言ではない(？).
ところで, 応用を受けた時は合格証書の受け取りに失敗してIPAまで自分で取りに行ったことがある. 簡易書留で送られてくるのだけれど, 忙しくて受け取れないでいたら差出人のところに戻って行ってしまった. メールで取りにきてね〜と言われて, 受け取りに. 受付に入ったらいきなり例のパスワードのアレのポスターがでかでかと貼ってあって笑いを堪えるのに必死だった. 個人的には「ひどい, パスワードが使い回しだったなんて......」が好きです.
そういえば, 秋の情報処理技術者試験の申し込みが開始したみたいっすね. ネスペ, チャレンジしようかどうしようか.
7/6 Javaでボン○ーマン風のゲームを作った
ソフトウェア制作のグループワークでJavaでゲームを作った. 懐かしのドット絵ですよ. 良さげな画像素材を使ってグラフィックをいい感じにしたら, 割とゲームっぽくなってきた. 素材の作者は偉大. ノリでSEとBGMもつけてみたけど, コンピュータルームのパソコンって, 音鳴らせるんですかね. 移動する, 爆弾置いて一定時間経つと爆発, 相手に爆風当てれば勝ち, 壁に爆風が当たると壊れる, 壁からランダムでアイテム出現, アイテム取ると爆風の範囲や同時における爆弾の数が増える, ぐらいまでは実装した. PCルームでソケット通信のテストもしたので多分大丈夫. 一人で自分のPC + PCルームのPC * 2を起動して作業するのめっちゃ周りから見たら「なんだこいつ」って感じだったんだろうなぁ. ゲームっぽさを上げるためにもうひとひねりしたいのだけれど, 時間が足りなさそうで残念. 明日の発表終わったら動画でも載せようか.
AOJ-ICPC
-
Minus One | Aizu Online Judge [解答]
最初方針を完全に間違えていた. 最短経路長を求めて-1すればいいと思ったのだけれど, 閉路がある時にダメだった. 木だったら問題なさそうな気がする(木だけに)(激ウマギャグ). 正しくは, 各頂点のs, tからの距離を求めて距離の和がdist(s, t) - 2になるような組の数を数え上げる. これならO(N)で計算できる. ちなみに, 一個int型だとオーバーフローするケースがあるみたいでWAした. a, bがint型, cがlong long型の時にc = a * bを計算するとa * bはint型で計算された後にcに代入されるらしい. まじかー. 基本的には全部long long使ってた方がいいのかも. ってか, 今までずっと勘違いをしていたのか...
言語処理系の試験？？？ 知らない子ですねぇ......
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次元版は用意してなかったので作った. -
Prowler | Aizu Online Judge [解答]
無限にバグらせまくった. 現在地の座標(y, x)と向いている方向dと手をついている座標(hy, hx)の5つを状態にして拡張ダイクストラ. 状態の遷移は向きを左右に変える, 前へ進む, 手の位置を現在の手の位置から隣接するマスに動かすのいずれか. 現在地と手の位置が正しいかどうかを判定する関数を作って, 少し多めに遷移は試している. はまるポイントが多くてしんどかった. なお, Vとvを間違えたのは本当にしょうもないのでアレ. 意外と最近{ 0, 1, 0, -1, 0 }使う系の問題解いてなかったのでいい練習になったかも.
なんか気がついたらソフトウェア制作のリポジトリにメンバーからPRがきていて, ゲームのタイトル画面がいい感じになってた. こういうのほんとありがたいんだよなぁ. というわけでもうちょっとグラフィック綺麗にしますか.
7/4 ソフトウェア制作...
AOJ-ICPC(A〜Cぐらいの問題を巡回することにした.)
-
Let's Solve Geometric Problems | Aizu Online Judge [解答]
結構苦戦した. -
Koto Distance | Aizu Online Judge [解答]
X方向/Y方向を別々にチェックすればOK. O(W + H)で計算できる. チェックはimos法使ってある座標を含むクエリの数を数えて, その最小値が0でなければOKという感じ. X/Yどっちかで全範囲カバーされていればYes, そうでなければNo. -
Fast Division | Aizu Online Judge [解答]
こういうタイプの問題苦手. n >= 3の時に0を出力すればいいことを示せば終わり. どう考えても具体的な値は求められないから, あるところから答えが一定になるんじゃないかなぁとは思ったけれど. 証明にはフェルマーの小定理(aとpが互いに素ならa^(p-1) ≡ 1 (mod p))を使う. 思い返すと高校生の頃からこういうの苦手でしたね. -
ABC Gene | Aizu Online Judge [解答]
問題勘違いし続けてひたすら時間を溶かした. 本番だったら死にたいレベル. "ABC"を見つけて'A', 'B', 'C'のいずれかに置換するって手順をdfsしながら見てく. 最終的に"ABC"に一致すればOK. 気をつけないといけないのが, 'A', 'B', 'C'のいずれかを選んで「「「全て」」」"ABC"に置換すると言うところ. 全て置換するので, dfsする時に置換先の文字が他に含まれていたらカットしないといけない.
ソフトウェア制作やらないといけないんだけど, 気分が乗らない......
7/2 ICPC模擬国内予選2017に参加してきた
ICPC模擬国内予選に参加してきた. 結果は4完で学内2位. M1チーム, B2チームと解いた問題数は一緒だったけれど, ペナルティで勝ったみたいな感じ. どっちも予選本番では強敵なので油断はできないですね. なお, 某チームに関してはさすがですって感じ. WA出さなかったことに関してはよかったなぁと.
自分はBを解いたのだけれど, 思いの外実装で手間取って時間をかけてしまった, 反省.
C問題は結構チーム内で「え〜、それほんとにあってる〜？」みたいなやり取りがあったのだけれど, 思い切って投げてみるとAC. ちょっと慎重になりすぎたかも(？).
D問題はペアプロみたいな感じでコーディングしてる横で一緒に考察してた. ぱっと見で二分探索ってことはわかったのだけれど, 「ゲームをクリアできない」状況ってのが理解できてなくて問題の本質をつかむまでに時間がかかってしまった. あと, データセットの解答に-1が多すぎてこれも「いや〜、これほんとか〜？」って言ってたのだけれど, 投げてみたらAC. 普通に歓声をあげて喜んでた.
この時点で残り1hあったのでもう1問解きたかったなぁという感じ. Fを考察していたのだけれど, 最小費用流(？)ってことに気づいたのが残り15分ぐらいでライブラリの準備もしていない状態だったので撤退. 他チームがACしないのを祈ってた. Eの方は幾何のライブラリがあんまり準備してなかったので選ばなかったのだけれど, こっちを選んでもよかったなぁという気持ち. 本番も4完した後にだれてしまう可能性あるので気を引き締めていきたいところ.
いろいろトラブルあって開始時間が遅れたりコンテスト時間が伸びたりしたけれど, 運営さんお疲れ様です.
本番はうちからプリンタ担いでいくぞい.
AOJ-ICPC(これで130問)
-
Falling Block Puzzle | Aizu Online Judge [解答]
すべての落下の仕方をdfsで探索するだけなのだけれど, 結構実装がしんどい. 落ちものパズル系の問題で消去して落下させる時は上から見ていく方がいいんですかね.
ARC077(起きたらコンテスト終わってたので, 後から解いた)
-
C: pushpush - AtCoder Regular Contest 077 | AtCoder [解答]
vectorを二つ用意して, 交互にpushしていく. 全部pushしたら片方をreverseして出力. -
D: 11 - AtCoder Regular Contest 077 | AtCoder [解答]
重複する要素の間に挟まれない要素の数を数える. 仮にその数をsとすると, k - 1 <= sのときはcombination(N + 1, k) - combination(s, k - 1)が答え. それ以外のときは, combination(N + 1, k)が答え. というのも, 同じ組み合わせができるときっていうのは重複する要素を含む組が2つできるときだけなので. そういう組の数は, 重複する要素の左右の要素数から(k - 1)個選んで, それに重複する要素を加えた構成になっているはず. -
E: guruguru - AtCoder Regular Contest 077 | AtCoder [解答]
Eは自力ではわからなかったので解説を見た. お気に入りを1にしたときの回数を求めておいて, i + 1のときの回数をiのときの回数から計算すると時間制限に間に合う. (i + 1)の回数 = iの回数 + (お気に入りボタンで直接ジャンプしたときに飛ばしていた数) - (iを含む区間の数)で計算できる. 足している部分はi番目ではお気に入りボタン一発で変更ができていたクエリで, i + 1になることでボタンをぽちぽちしないといけなくなる分になっている. 引いている分はお気に入りがiのときにはお気に入りボタンとボタンをぽちぽちしていたクエリで, お気に入りがi + 1になると全て1回分ボタン操作が減る. 後者はimos法で求めてあげればOK. 輪っかみたいになった状況でのimosって初めてだったけれど, M - 1と0の間を跨ぐときは, (A[i], M - 1), (0, A[i + 1])っていう二つのクエリに分割すればよさそう. ちなみにINFの値が小さすぎて1時間WA出し続けた().
明日は卒検ですねぇ............
7/1 睡眠削る生活やめたい
睡眠削るのって次の日は寝不足で頭回らないなーってぐらいで済むけど, それを補って長めに寝た次の日が全然頭働かなくなる気がする. 起きてるのにずっとぼーっとしてるみたいな感覚. 早くこういう生活やめたいのだけどなぁ...
今日で自動車学校の教習は全部終了. 明後日に卒検なのだけれど, 落とされそうで怖いっすね... まぁ, 免許取るには一度地元に帰らないといけないので夏休みになるんですが. 確か豊川の免許センターに行かないといけなかったはず(？). あんまりよくわかってない.
