7/16 期末の勉強をせねば
そろそろ期末試験の勉強をしないとまずいのだけれど, もちろん全く手をつけていない. とりあえず, 今週の教場試験ってOSA, ソフ工, 言語処理系だけって認識であってますかね.
yukicoder contest 169
-
No.542 １円玉と５円玉 - 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
- 魔法を使う回数を決めると相手が倒せるかどうかをO(N)で判定できる. 回数が増えるとあるところから以降は常に倒せるのは直感的にもそうなのでにぶたんと判断. ただ, 実装でミスった. にぶたんの初期値を大きく取りすぎたらlong longからあふれてた.
