7/12 ICPC2016国内予選のA, B, C問題を解きました(今更)

ICPCの国内予選が目前に迫ってきているわけですけど, 実は自分は昨年はICPC参加してないんですよね. AOC-ICPCでも昨年の問題は最後に残しておこうと思って, 今日まで解かずに温存してありました. というわけで, 今日はABCまで解いてみました. ABCは難しくなかったかなぁという印象. なるべく高速に解きたいところだけど, 本番で緊張すると意外とできなかったりするんだろうなぁ.

AOJ-ICPC

• Selection of Participants of an Experiment | Aizu Online Judge [解答]

  ソートして要素間の差を取って最大値を求めるだけ. 瞬殺したい問題. こういう問題は読解力勝負だなぁと.

• Look for the Winner! | Aizu Online Judge [解答]
  地味に問題文が複雑で本番だとテンパりそうで怖い. 一票ずつ開票して, その状態である候補者と他の候補者の得票数の開きが残り票より大きければその人が当選. 後から気づいたけれど, 制約が厳しくないから一票ごとにソートして1番目の候補者と2番目の候補者の差を見るだけでもよいかも. こっちのほうが実装楽そう.

• Bamboo Blossoms | Aizu Online Judge [解答]
  エラトステネスの篩みたいなことをすると解ける問題. 問題文に最大ケースの答えが出ているので, その値+1の大きさの配列を用意する. 最初は全部trueで初期化しておく. m番目から順にtrueな要素を見つけたらその倍数をfalseにするのを, trueな要素がn個見つかるまで繰り返す. そのあとに出てくる最小のtrueな要素のインデックスが答え. エラトステネスの篩って, O(Nlog(logN))とかだったと思うのだけれど, これもそれぐらいで求まるんですかね.

7/11 寝坊したので-2000円

どうやら目覚ましをかけ忘れたらしく, 起きたら9時を過ぎていた. 早起きに失敗したので焼肉基金に2000円を支払った. 通算-6000円. 夏休みに入ったら焼肉ですかね(). 朝起きれなかったら罰金, 結構起きられるようになるのでオススメですよ. そういえば, スヌーズするたびに口座から寄付されるって目覚ましをTwitterで見かけた気がする.

AOJ-ICPC

• Unordered Operators | Aizu Online Judge [解答]
  *, +, -を含んだ数式が与えられて, 演算子の優先順位を変更して式の値を最大化するという問題. 制約は厳しくないので適当な実装しても通る, 結構面倒だけれど. ちなみに, 演算子の優先順位付きの式の構文解析は優先順位のグループ数+1個の非終端記号を持った文法で表せる. E→E+T, T→T*F, F→数値|(E)みたいな感じ. このままだと左再帰が残っていて再帰下降型の構文解析をするときに無限再帰になってしまうので, 左再帰を除去してプログラムにしてあげればOK. うっかりミスって右結合になっていて詰まったけれど.

• An Equation in a Mine | Aizu Online Judge [解答]
  考察も結構しんどかったけれど, そこからの実装がそれ以上にしんどかった問題.  チームメイトがまだ解いてなさそうなので解説はなしで.

7/10 久しぶりに家でのんびり

日曜日, 月曜日と久しぶりに1日中家にいられる日が作れた. カレンダー見る限りだと家から出なかった日は1ヶ月ぶりぐらいらしい. OSAの課題と無線通信の課題を片付けて残りの時間はOS自作入門に当てた. かなり睡眠時間も確保できたし, 今週もがんばりませう.

AOJ-ICPC

• Evacuation Route | Aizu Online Judge [解答]
  最初はユニットが閉じられていく順番の逆順でUnionFindして〜みたいなことを考えていたけれど, どう考えてもダメっぽそうなので方針転換. 結局, 脱出可能な人数を左右から順番に見ていくだけということに気づく. 脱出可能な人数dを最初は0にしておいて左から順に, 出口に当たればd = INF, 防火扉ならd = -a[i]に更新して, ループの終わりでd--すればよい. これを左からと右から行い, 大きい方が脱出可能な人数.

AtCoder

• D: 25個の整数 - AtCoder Beginner Contest 025 | AtCoder [解答]
  だいぶ前に解こうと思って, 解説見てわかんねーってなってた問題. 数字を小さい順にマスに入れていくと, どのマスに数字が入っているかの情報だけから次の数字をマスに書き入れられるかどうかが判定できる. なので状態数は2^20のbitDPをすればよい. 普通に0から1 << 25までfor文で状態を見ていくって方針でトライしたのだけれどうまくいかなかったのでdfsしてみた. 結構判定自体も煩雑でややこしいので, そこでミスったんだろうか.

7/8 DBの合格証書が届いた

DBスペシャリストの合格証書が届いた. これで, 基本/応用/DB全部取得したので実質星野源と言っても過言ではない(？).

ところで, 応用を受けた時は合格証書の受け取りに失敗してIPAまで自分で取りに行ったことがある.  簡易書留で送られてくるのだけれど, 忙しくて受け取れないでいたら差出人のところに戻って行ってしまった. メールで取りにきてね〜と言われて, 受け取りに. 受付に入ったらいきなり例のパスワードのアレのポスターがでかでかと貼ってあって笑いを堪えるのに必死だった. 個人的には「ひどい, パスワードが使い回しだったなんて......」が好きです.

www.ipa.go.jp

そういえば, 秋の情報処理技術者試験の申し込みが開始したみたいっすね. ネスペ, チャレンジしようかどうしようか.

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次元版は用意してなかったので作った.

  github.com

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

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

7/4 ソフトウェア制作...

AOJ-ICPC(A〜Cぐらいの問題を巡回することにした.)

• Kakezan | Aizu Online Judge [解答]

• 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する時に置換先の文字が他に含まれていたらカットしないといけない.

ソフトウェア制作やらないといけないんだけど, 気分が乗らない......