あるごリズム備忘録

学んだことの記録と日記

競プロの記録 (2016_09_09)

今日は5問しか解けなった。しかもすべてyukicoderの星1問題。本当に意志が弱い。原因は寝坊と、ネットサーフィン。
ただ、ノルマの5問は何とかキープで出来たことだけはよかった。

1問目:yukicoder?No.051
No.51 やる気の問題 - yukicoder

入力値自体は、10^5以下(intでいける)だったが、処理途中の計算で、かけることにより10^10を超える値になる場合があったが、それを見落としていた。

2問目:yukicoder?No.056
No.56 消費税 - yukicoder

Dに(100+P)/100をかけるだけ。

3問目:yukicoder?No.057
No.57 ミリオンダイス - yukicoder

期待値の線形性を理解する。
出た目の合計値をN個分足しているだけなので、1つ1つのサイコロについての目の期待値(今回は3.5)をN回足せばよいだけ。
ちょっと数学的に書くと、E[X+Y] = E[X]+E[Y]。
しかし、解けなかった。必死に全パターン計算しようとしていた。
こういう問題を解くための解決策としては、期待値の線形性をいつも頭の片隅に置いておくことがあるが、例が誘導してくれてる場合もあるので気づけるようにしたい。
再解答リストへ追加。


4問目:yukicoder?No.063
No.63 ポッキーゲーム - yukicoder
最初食べた量を出す対象者を勘違いしていた。問題はちゃんと読もう。
普通にシミュレーションしたが、intの割り算の性質を利用して、(L-1)÷(2×K)×Kでよかった。
これならちょうど割り切れるものは1でなく0になってくれる。
何度も言うが、こういうテクニックがすぐに出て売るようでないと、簡単な問題の瞬殺は難しい。

5問目:yukicoder?No.064
No.64 XORフィボナッチ数列 - yukicoder

bitXORの演算子が'^'らしい。覚えた。
はじめ、実際に第N項まで計算していたが10^18だから間に合うはずがない。
排他的論理和結合法則、同じ数のbitXORは0であること、0とのbitXORはその数自身であることを使うと、F0,F1,F2,F0,F1,F2,・・・を繰り返すのでMOD3を使えば解ける。
再解答リストへ追加。

明日からはブログの更新が日を跨がないようにしたい。
A予選まであと15日。