0x19f (Shinya Kato) の日報

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

7/24 AGC018とか

AtCoder Grand Contest 018

安定の1完(). A問題が難しくて普通にお葬式になるところだった. Bは言われれば貪欲だなぁ〜って感じ.

 

ABC/ARC D問題埋め

  • D: No Need - AtCoder Regular Contest 070 | AtCoder [解答]
    部分点解法は, ある1枚のカードを抜いて部分和を列挙する. 和がK未満の部分集合に抜いたカードを入れて和がK以上になれば, そのカードは不要ではない. 抜くカードの選び方がN, 部分和の列挙がO(NK)なので, 全体で計算量はO(N^2 * K).
    満点解法は, しばらく考えたのだけれどわからなくて解説を見てしまった. 実はカードを書かれている数字の昇順でソートすると, カードiが不要ならカード(i - 1)も不要となる. なので, 必要なカードと不要なカードの境界を二分探索する. もちろん, 二分探索の判定部分では部分和のDPをする. 全体としての計算量はO(logN * NK)になる.

7/23 OS自作をしていたらWindowsが起動しなくなっていた

ここ最近結構時間を費やしてOS自作入門を読んでHaribote OSを写経したりしていたのだけれど, せっかくだから実機でも動かしてみたいなと思ってUSBにディスクイメージを書き込んで起動させようとしたら, Windowsが起動しなくなっていたことに気づいた.

 

代わりになぜかHaribote OSが起動する()

 

ほとんどはMac上でエミュレータを使って挙動を試していたのだけれど, その環境を構築する前に一瞬だけVAIOで2, 3日分ぐらい試していたので, その時に間違ってHDDにイメージを書き込んだのかなぁと. だとしたらmake installみたいなので書き込まれたんですかねぇ. 自分の性格的に特に意味もなくコマンド実行してたりする可能性は全然あるんだよなぁ. まぁ, その辺中身が何をしているのかあんまり理解してないのでアレですが.

 

運のいいことに, このVAIO自体にはほとんど大切なデータとか入れてなくて, Windowsも10への無償アップグレードをし損ねたWindows 7で, ほとんど壊れても問題ないマシンとして扱っていたのでそこまで痛手ではないのだけれど...

 

さらにいろいろ試していたら, デュアルブートさせていたUbuntuの方は起動できたのだけれど, なぜかキーボードから特定の文字だけが入力できない. そのためパスワードが入力できなくてログインできない.

 

それにしても, ブート関連の場所ってほんのちょっと書き換えただけでもOS起動しなくなるものなんですねぇ......

7/22 ソフトウェア工学と言語処理系の期末おわり

ソフトウェア工学は微妙, 言語処理系はぼちぼち(?).

ソフトウェア工学は正直ただの暗記ゲーで内容的にもそんなに面白いものではないので退屈だった.

言語処理系はちゃんと勉強してみると面白かったのだけれど, もう少しちゃんとしたレジュメ配って欲しいっす.

あと, 試験問題はバリエーションがなくてめちゃくちゃ退屈.

 

ABC/ARC D問題埋め

  • D: Alice&Brown - AtCoder Regular Contest 072 | AtCoder [解答]
    MiniMaxで全探索するプログラムを書いて0 <= X, Y <= 20ぐらいの答えを全部試してみたら, |X - Y| <= 1の時はBrownが, それ以外の時はAliceが勝ったのでそこから答えを推測.
    たまには試してみるのも大事ですね.

  • D: 井井井 / ### - AtCoder Regular Contest 071 | AtCoder [解答]
    あるi, jについてx = X[i], x = X[i+1], y = Y[j], y = Y[j + 1]で囲まれる長方形が何回足されることになるかを考える.
    これはこの長方形を含むような長方形がいくつあるかと同じなので, (i + 1) * (N - i - 1) * (j + 1) * (M - j - 1)と等しくなる.
    よって, 求める値は\sum_{i = 0}^{N - 1} \sum_{j = 0}^{M - 1} (i + 1) * (N - i - 1) * (j + 1) * (M - j - 1) * (X[i + 1] - X[i]) * (Y[i + 1] - Y[i]).
    この式をよく見るてiとjをそれぞれ総和と関係ないところから外すと, (\sum_{i = 0}^{N - 1} (i + 1) * (N - i - 1) * (X[i + 1] - X[i])) * (\sum_{j = 0}^{M - 1}  (j + 1) * (M - j - 1) * (Y[i + 1] - Y[i]))となる.
    あとは, X/Y方向の総和をそれぞれ求めて最後に掛け合わせれば, O(N + M)で求められる.

  • D: Maximum Average Sets - AtCoder Beginner Contest 057 | AtCoder [解答]
    平均の方は価値の降順にソートして, 先頭からA個の平均を求める.
    組み合わせの数は, 基本的にはコンビネーションを求めて足し上げるだけ.
    ソート列のA番目の値がN個の中にいくつ含まれるか(=d)と先頭からA個までの中にいくつ含まれるか(=c)を数える.
    平均を求めるときに, 2種類以上の価値のものを使っていれば答えはcombination(d, c).
    そうでない場合は, 全て同じ値を使う組み合わせをA個からB個まで足しあげれば良い.

7/19 Haribote OSにファイルシステムを作る

OSの授業の自由課題で『OS自作入門』のHaribote OSに簡単なファイルシステムを作ることにした. (なお, 書籍自体は23日目までしか終えてない.) ファイルシステムと言っても, ディスクI/Oのやり方がわからないのでメモリ上にディレクトリツリーがあるだけだけれど. inodeみたいな構造体を用意して, コマンドでツリー構造を変えられるようにした. いまのところ, cd/pwd/mkdir/rmdir/mv/rmぐらいは作って問題なく動いてそうな感じ. 久しぶりに線形リストを扱ったので末尾挿入や要素削除で手間取った. 他にも文字列を'/'でsplitとかは地味に面倒だった. あとは簡単なテキストファイルを作れるコマンドぐらいあるといいかなぁ. 思いの外早くできてしまったのでディスクI/Oもやってみたいのだけれど, あと1週間ちょいではなんとかならなさそう.

 

ABC038

  • D: プレゼント - AtCoder Beginner Contest 038 | AtCoder [解答]
    サークル活動で「今週のABC!」的なことをしようってこれが出題されていたので解いた. 解くのは3回目ぐらい. pair(h, w)の昇順にソート, 高さ順に全要素を見ていきながら, [1, w[i]]の最大値をBITを使ってlog(N)で更新/計算する. 高さが変わるタイミングまではBITの更新をしないのがポイント. BIT使うのも久々だったのでいい練習になった.

 

期末テスト7個って少なくないですか?(今まで13個とかがデフォルトだったので)

7/17 School Daysを1話からちゃんと見た

ニコ動でSchool Daysが無料配信になっていたので見ていた. 実は最終回しか見たことなくて, 1話からちゃんと見るのは初めてだったりする. 1話見るごとに「誠死ね」という思いがどんどん募っていく作品だった. もう少し誠に葛藤とか苦悩とかがあればそんなに胸糞悪くなく見れると思うんだけどなー. 正直コメントなしで見るのは割とつらいかも. でも, 総じて面白かったです. 昔の名作をどんどん見てアニメ力上げていきたい.

アニメ「School Days」期間限定無料配信|ニコニコインフォ

 

Educational Codeforces Round 25

結局ABCDを解いておしまい. Bは後から落とされた.

  • Problem - A - Codeforces [解答]

    0でsplitして, 1の数を数え上げて各桁の数にすればOK.
  • Problem - B - Codeforces
    10 * 10の中の連続する5マスを全部チェックして, 'X'が4つと'.'が1つある箇所があればYES, そうでなければNO. と思ったのだがハックされた. 何がいけなかったんでしょうねぇ.

  • Problem - C - Codeforces [解答]
    Aiを昇順にソートしてgreedy. それまでに解いた最も難易度の高い問題の難易度をkとする. 最初はk = Mとしておく. Aiを一つづつ見ながら, k * 2 >= Aiなら解ける, そうでなければ, 現状で解ける最大の難易度(k * 2)の問題を他のオンラインジャッジで解いてkを上げていく.

  • Problem - D - Codeforces [解答]
    よくわからなかったので二分探索してsuitabilityの最大値を計算, そこから'?'を置換した. 問題のタグにgreedyって付いてたし, もしかしてもっと簡単にできるのかも.

  • Problem - E - Codeforces [解答]
    1時間ぐらい考えていたけれど, 結局ACできなかった. どうやら辺を逆向きにすると解けるみたいなのだけど, なぜだかはよく理解できてない.

 

ABC061

  • D: Score Attack - AtCoder Beginner Contest 061 | AtCoder [解答]
    辺のコストの符号を逆にすると, 頂点1から頂点Nまでの最短距離問題になる. 負の辺を含む最短経路問題なのでベルマンフォード法を使えば良さそう. 問題の設定では頂点1から頂点Nまでの中に負の閉路があるかを検出する必要がある. グラフ全体で負の閉路を検出するには, ベルマンフォード法の更新が頂点数以上起きたかどうかを見れば良い. しかし, 今回は1からNへの経路中以外に負の閉路があっても答えはinfにならない. というわけで, 1からNへの経路中だけに負の閉路があるかを判定する. これは更新をN - 1回行った結果とN回行った結果が一致するかを見れば良い.

7/16 期末の勉強をせねば

そろそろ期末試験の勉強をしないとまずいのだけれど, もちろん全く手をつけていない. とりあえず, 今週の教場試験ってOSA, ソフ工, 言語処理系だけって認識であってますかね.

 

yukicoder contest 169

  • No.542 1円玉と5円玉 - yukicoder [解答]
    制約的に全部の枚数の組み合わせを2重ループで列挙しても問題ない.

  • No.543 命題 - yukicoder [解答]
    逆と裏は待遇の関係にある. 入力されたT/Fを左右入れ替えて出力すればOK.

  • No.544 Delete 7 - yukicoder [解答]
    7を持つ桁があればそれを6に置き換えて行った数をAにする. BはN - Aで求められる.

  • No.545 ママの大事な二人の子供 - yukicoder [解答]
    半分全列挙. 実は半分全列挙の問題を自力でちゃんと答えまで出したのは初めてかも. 入力を2つのグループに分けて, それぞれの組み合わせを全列挙する. そのあと, グループ1の方を1個ずつ見ながら, グループ2の方を2分探索する. N = 1の時がコーナーケースになるので気をつける.

  • No.546 オンリー・ワン - yukicoder [解答]
    包除原理を使う. 包除も苦手. N個の中からk個の組み合わせを列挙してk個の数の最小公倍数を求め, 範囲の中から割り切れる数を求める. 1 * (k=1の総和) - 2 * (k=2の総和) + 3 * (k=3の総和) - ...が求める答え.

 

ARC078

昨日のARCは結局CD解いて2完で終了. Eはなんとなく法則性がつかめてきたところで時間切れになったので, 結局よく理解してない.

  • C: Splitting Pile - AtCoder Regular Contest 078 | AtCoder [解答]
    N - 1個の区切り方を全部試せばOK. Aiの総和と左側の和をループ回しながら足していけば, O(N)で求められる.

  • D: Fennec VS. Snuke - AtCoder Regular Contest 078 | AtCoder [解答]
    2頂点間を結ぶパスは1つしかないという木の性質を利用する. パスは一つしかないので, 途中を塞ぐと相手はそこから先のマスは塗れなくなる. 結局, 最初の白黒のマスから相手のマスに向かって最短で陣地を広げていくのが最善. なので, 自分と相手で交互に幅優先探索して白黒を塗っていけばOK. 最終的に塗れたマスの数が(先手) > (後手)なら先手の勝ち, そうでなければ後手の勝ち. ちなみに, 数が同じ時は全てのマスを塗りつくした状態で先手に手番が回ってくるので先手が負ける.

 

ARC075

  • D: Widespread - AtCoder Regular Contest 075 | AtCoder [解答]

    魔法を使う回数を決めると相手が倒せるかどうかをO(N)で判定できる. 回数が増えるとあるところから以降は常に倒せるのは直感的にもそうなのでにぶたんと判断. ただ, 実装でミスった. にぶたんの初期値を大きく取りすぎたらlong longからあふれてた.

7/14 ICPC2017国内予選で惨敗した

結論だけ、書く

失敗した失敗した失敗した失敗した失敗した失敗した失敗した

失敗した失敗した失敗した失敗した失敗した失敗した失敗した

失敗した失敗した失敗した失敗した失敗した失敗した失敗した

失敗した失敗した失敗した失敗した失敗した失敗した失敗した

失敗した失敗した失敗した

 

 

はい, 3完しかできませんでした. まじかー. お前の人生失敗してばっかだな. D問題, 3人もいてどうして分けるって発想が全く出てこなかったんだ...

Dに気を取られてて全然そのあとも問題読めてなかったけれど, Gとかワンチャン解けたのでは. 迷路の一番外側を通るようにして1週したときに, 同じマスを踏まずに回れるかみれば良さそう. Eは生成規則に従って16文字以下の論理式を列挙して, abcdの全組み合わせに対して出力が同じになる論理式を探すんですかね?. Fは考えてみたけれどわからない. Hは点の組み合わせと重ねる順番を全部試すとか?

 

なお, 3完したチームの中で最上位というなんとも言えない感じ.