0x19f (Shinya Kato) の日報

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

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完したチームの中で最上位というなんとも言えない感じ.

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 [解答]
    考察も結構しんどかったけれど, そこからの実装がそれ以上にしんどかった問題.  チームメイトがまだ解いてなさそうなので解説はなしで.