読者です 読者をやめる 読者になる 読者になる

あるごリズム備忘録

学んだことの記録と日記

競プロの記録 (2016_09_25)

今日は星1を15問解いた。

「星1」

No.239 にゃんぱすー - yukicoder

問題文には、「自分以外のすべての人に」と書かれていることは確認していたけど、
テスケースがそうなっていないように見間違えた。
テスト入力が行列形式の時は、間違いやすいのでしっかり確認したい。

No.256 桁の数字を入れ替え (2) - yukicoder

やることは簡単。各数字が何回出てきたかカウントしておくだけ。
ただ、 N<10^100000 の制約を見て、10^100000回計算が必要だと反射的に思ってしまった。
でも冷静に考えれば10^100000は1000000「文字(桁)」しかない。
普通にやれば全く問題がなかった。
このような勘違いをなくさないと、B予選での早解きは難しい。

No.279 木の数え上げ - yukicoder

問題自体はやるだけだが、3つの数のうち最小値を選ぶ際に、先日覚えた min(A,min(B,C)) がすぐに思いついて使えた点は良かった。


B予選まであと15日。

A予選の感想

C: 次のアルファベット / Next Letter - CODE FESTIVAL 2016 qual A | AtCoder

文字列を先頭から見ていって、できる限り'a'にするだけ。
あまりの操作数は最後の文字で調整する。
解法は割とすぐに気が付いたが、「もとから'a'」の時は例外とすることに気が付かなかった。
これで1時間半以上使ってしまい、結局解けなかった。
このような「境界」を常に考える力がまだ弱い。癖がついてない。


先ほどA予選に参加してきた。
結果は2完、812位。ひどい結果だ。
他人が着々と力をつけている間に、自分が何もせず、相対的に差が付いていることを思い知らされた。
自分がB3になったこともあり、上位に年下が多くなった。
自分が確実に年齢を重ねてしまっていいることを改めて意識させられ、それがまた悔しい。
ただ、ここで落ち込んでいると同じことの繰り返しになる。
また一年後に同じ場所にとどまっていることになる。
現実から目をそらしてはいけないが、自分の位置を冷静に確認した上で前を向いて、次の作戦を立てることが重要だ。
そして何よりも、行動すること、手を動かすことが必要だ。
口ではなく、手を動かす。

B予選までの計画。
というよりも、来年本選へ出場するための準備か?
いずれにしても次回の目標と、それまでにやるべきことは次のようにしたい。

(B予選での目標)
 ・3完(45分以内)
 ・順位550位以内
 ・レート:900以上

(やること)
 ・yukicoder(星1)を埋める。
 ・yukicoder(星2)を15問解く。
 ・ABCには必ず参加する。

この他に、もちろん再解答リストも消化する。
B予選では、今回のC問題くらいまでの難易度の問題を素早く、
また条件を抜かすことなく解けるようにするのがよさそうなので、
星1の問題をサクッと解けるようにすることに力を入れたい。
同時に、星2の問題で、少し考察する癖も消えないようにしておきたい。
B予選直前、そして来年に「これだけはやった」といえるようにしたい。
口だけの人間はもう嫌だ。

競プロの記録 (2016_09_24)

今日は星1を6問と、星2を1問解いた。
そのほか中途半端な星2が1問。

「yukicoder: 星2」

No.16 累乗の加算 - yukicoder

愚直にやると10^(2+8)で間に合わない。
指数が小さいほうから計算していき、その都度一つ前のものを利用していけば、毎回丸々指数の分だけ計算する必要は無くなる。
これにより、10^2+10^8で間に合う。
自分はこのやり方で通したが、「繰り返し二乗法」と呼ばれるやり方があるらしい。
これでN乗の計算が、O(N)からO(logN)になる。
どうしても、MODをとるのを忘れがちになるのを注意したい。

No.43 野球の試合 - yukicoder

これは解けなかった。試合数は高々15試合しかないので試す数は2^15 = O(10^4)となり、全探索することができる。
実装が長く、複雑になりそうなので、A予選を控える今日はやらない。方針は立っているので、後日実装しようと思う。

A予選まであと5分。

競プロの記録 (2016_09_23)

「yukicoder:星1」

yukicoder

N-1を言えれば勝ちである。
自分のターンと相手のターンで1セットとすると、1セットでK+1ずつ進めることができ、これが相手にとって最善であり、
(N-1)が(K+1)で割り切ることができれば相手の勝ちである。
それ以外なら自分の勝ちになる。
理解できる考え方だが、証明はどうやるんだろうか?
ちなみに、自分で実装した時は全探索でDPを用いた。
この辺のコードが比較的短い時間で、考えられるようになったのは成長だと思うが、この問題では計算時間的にACにならない。


今日は久しぶりに、短い時間(2時間程度)ながらも、「競プロのための時間」をとることができた。
これまでも、物理的に時間が取れなかったわけでなく、ただの精神的な甘えだったのだけれど。
昨日、ブログを書く際に、タイトル部分でまとめて書く日付の多さを見て、改めてサボっていた期間の長さを思い知った。
このように、自分の頑張りや生活態度を、小刻みに確認できるのが、ブログをこまめに書くことの利点だと思う。

内容としては、yukicoderの星1を3問と、星2を1問解いた。

A予選まであと1日。ついに明日。

競プロの記録 (2016_09_17,18,19,20,21,22)

この6日間で解いた問題は、yukicoder星1の3問のみ。
体調不良や、友人とのゲーム作成があったとはいえ、これはさすがにひどい。
一日の間、どのように時間を使っているかの記録を久しぶりにやったほうがいいかもしれない。
生活リズム自体が崩れている。

A予選まであと2日。

競プロの記録 (2016_09_15,16)

No.182 新規性の虜 - yukicoder
問題はやるだけだが、いくつか新しく知ったことがあった。
まず連想は配列mapについて。
今回、入力が初めての数字だったら、m[A]=0; と初期化していたが、必要ない様だ。
いきなりインクリメントしてしまってよい。
次に、autoについて。
連想配列mのすべての要素にアクセスするとき、煩雑なiteratorの宣言を書かなくてよい。
それぞれ次のように書ける。

map<int, int> m;

map<int, int>::iterator it = m.begin();
while (it != m.end()) {
	if ((*it).second == 1) cnt++;
	it++;
}

for (auto i : m) {
	if (i.second == 1) cnt++;
}

この二日間は体調不良でほとんど何もできていない。
季節の変わり目だということを考慮して、もっと体調に気を付けるべきだった。
身体がまともじゃないと何もできないと改めて感じる。


A予選まであと8日。

競プロの記録 (2016_09_14)

<星1>

No.172 UFOを捕まえろ - yukicoder

今回の結界のばあい、4辺をそれぞれ直線と考えると、傾きを表す係数は、-1か1になる。
この時、直線上の任意の点はすべて、原点からのマンハッタン距離は等しくなる。
直線と円の接点の座標に関して、マンハッタンン距離をっ求めるだけの問題だった。
(補足)
四捨五入するのでなく、切り上げる場合は、double型の計算値に1を加算する。さらにここから1-e9を引いてからintでキャストする。この減算は、計算値がぴったりだった場合に、+1されることなく正しい値にするためのものである。

No.175 simpleDNA - yukicoder

瞬殺問題のハズだったが、終止コドンが途中に含まれた場合を除く処理を(必要ないのに)書こうとしていた。
例を見れば、それを除く必要が無いのはわかったはずだった。
難易度から考えて、実装が割に合わないときは、余計なケースを考えていないか、例もしっかり見て参考にするべき。

<星2>

No.7 プライムナンバーゲーム - yukicoder

エラトステネスの篩であらかじめ素数のリストを用意しておく。
(初めて使った。ライブラリにしておきたい感覚がなんとなくわかった。)
遷移先に、一つでも自分が勝てる道がある(dp[n - prim]の中に0がある)なら、勝ちである(dp[n]=1)。
dp[0]=dp[1]=1としておくのがポイント。
0と1は負け条件なのにdpが1というのが、感覚的に理解しずらかったが、こうしないとうまくいかない。(要検討)
遷移先のdpが0とは、相手が負けることなので、つまり自分の勝ちを表す。
時間はかかった(90分くらい)が、一発ACだった気持ちが良かった。競プロの楽しさを思い出させてくれる。
定着させるために、再解答リストに追加。


A予選まであと10日。