競プロの記録 (2016_09_08)

今日は9問解いた。

1問目：ABC017_C

C: ハイスコア - AtCoder Beginner Contest 017 | AtCoder

はじめDPかと思ったが、DP用の２次元配列を作ると、10^5*10^5の規模になって間に合わない。
解説を見ると、すべての洞窟を得点の合計から、各宝石を覆っている洞窟の得点合計を引いて、その差が一番大きくなるものを選べばよいらしい。
確かにこれなら２つの極端なケースについても次のようになる。
１：すべての洞窟を探索しても宝石を集めきることがないとき。
⇒少なくとも一つの宝石については覆っている洞窟の得点が0になるため、すべての得点合計がそのまま答えになる。
２：どう選んでもすべての宝石が集まってしまう。
⇒どの宝石を選択しても、それぞれの合計得点は、すべての合計得点と等しいので答えは０になる。
実装方法としては、宝石の数分の要素数(+α)の配列を作り、imos法で計算。

2問目：yukicoder_No.024
No.24 数当てゲーム - yukicoder

０から９に関する配列を作って、入力のＹＥＳ，ＮＯによって配列の値を増減させ、元も大きな値をもつ要素が答え、というようにした。
これはＡＣしたけど嘘解法のような気がする。
解説のように、表を作って×をつけていったほうが確実でわかりやすい。

3問目：yukicoder_No.026
No.26 シャッフルゲーム - yukicoder

シュミレーションするだけ。

4問目：yukicoder_No.029
No.29 パワーアップ - yukicoder

同じ物２個のルールを優先的に使い、残りで４つ揃えるシミュレーション。
２個ルールを優先したほうが得点が最大化するというのは感覚的にはその通りだけど、証明はどうするんだろう。それともこれは自明なことなのだろうか。
また、２個ルール適用後のアイテムの個数をわざわざ計算していたが、MOD2であることは明らか。
このようなことにすぐ気づけるためにも、まず紙に書いてみるのはやはり大切。

5問目：yukicoder_No.032
No.32 貯金箱の憂鬱 - yukicoder

金額の小さい硬貨から、順に両替していった。
入力順を逆に勘違いしていてハマった。
問題文はしっかり読もう。

6問目：yukicoder_No.035
No.35 タイパー高橋 - yukicoder

合計入力数には、時間内に入力可能な文字数と与えられた文字数の小さいほうを加算してく。
逃した数には、０と与えられた文字数から時間内に入力可能な文字数を引いた値のうち、小さいほうを加算していく。
あとstringのsize()メソッドの返り値の型はsize_tという型であることを初めて知った。
このせいで、min()やmax()を使うとき少し苦労した。

7問目：yukicoder_No.046
No.46 はじめのn歩 - yukicoder

b%aが0かどうかで場合分け。0出ないなら商に1を足す。
と、思っていたが定番のテクニックとして、分数の分子に(b-1)をたしておくというのがあるらしい。
従って今回の場合、(a+(b-1))/bを出力するだけでよかった。

8問目：yukicoder_No.047
No.47 ポケットを叩くとビスケットが２倍 - yukicoder

軽く実験してみた結果、Ｋ回たたくとき、2^K以下の任意の枚数を作れそうだったので、2をK乗して、N以上になるKを答えとした。
確かに実験すればわかるんだけど、こういうのをすぐに証明できるようになりたい。

9問目：yukicoder_No.048
No.48 ロボットの操縦 - yukicoder

回転の回数は最初にカウントしておく必要がある。
今回のように、実験してみて愚直に場合分けするしかないときもあることを頭に入れておく。

Ａ予選まであと１６日。