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してみた. 結構判定自体も煩雑でややこしいので, そこでミスったんだろうか.