競プロの記録 (2016_09_25)
今日は星１を１５問解いた。
「星１」
問題文には、「自分以外のすべての人に」と書かれていることは確認していたけど、
テスケースがそうなっていないように見間違えた。
テスト入力が行列形式の時は、間違いやすいのでしっかり確認したい。
No.256 桁の数字を入れ替え (2) - yukicoder
やることは簡単。各数字が何回出てきたかカウントしておくだけ。
ただ、 N<10^100000 の制約を見て、10^100000回計算が必要だと反射的に思ってしまった。
でも冷静に考えれば10^100000は1000000「文字（桁）」しかない。
普通にやれば全く問題がなかった。
このような勘違いをなくさないと、Ｂ予選での早解きは難しい。
問題自体はやるだけだが、３つの数のうち最小値を選ぶ際に、先日覚えた min(A,min(B,C)) がすぐに思いついて使えた点は良かった。
Ｂ予選まであと１５日。
A予選の感想
C: 次のアルファベット / Next Letter - CODE FESTIVAL 2016 qual A | AtCoder
文字列を先頭から見ていって、できる限り'a'にするだけ。
あまりの操作数は最後の文字で調整する。
解法は割とすぐに気が付いたが、「もとから'a'」の時は例外とすることに気が付かなかった。
これで１時間半以上使ってしまい、結局解けなかった。
このような「境界」を常に考える力がまだ弱い。癖がついてない。
先ほどＡ予選に参加してきた。
結果は２完、８１２位。ひどい結果だ。
他人が着々と力をつけている間に、自分が何もせず、相対的に差が付いていることを思い知らされた。
自分がＢ３になったこともあり、上位に年下が多くなった。
自分が確実に年齢を重ねてしまっていいることを改めて意識させられ、それがまた悔しい。
ただ、ここで落ち込んでいると同じことの繰り返しになる。
また一年後に同じ場所にとどまっていることになる。
現実から目をそらしてはいけないが、自分の位置を冷静に確認した上で前を向いて、次の作戦を立てることが重要だ。
そして何よりも、行動すること、手を動かすことが必要だ。
口ではなく、手を動かす。
Ｂ予選までの計画。
というよりも、来年本選へ出場するための準備か？
いずれにしても次回の目標と、それまでにやるべきことは次のようにしたい。
（Ｂ予選での目標）
・３完（４５分以内）
・順位５５０位以内
・レート：９００以上
（やること）
・yukicoder（星１）を埋める。
・yukicoder（星２）を１５問解く。
・ABCには必ず参加する。
この他に、もちろん再解答リストも消化する。
Ｂ予選では、今回のＣ問題くらいまでの難易度の問題を素早く、
また条件を抜かすことなく解けるようにするのがよさそうなので、
星１の問題をサクッと解けるようにすることに力を入れたい。
同時に、星２の問題で、少し考察する癖も消えないようにしておきたい。
Ｂ予選直前、そして来年に「これだけはやった」といえるようにしたい。
口だけの人間はもう嫌だ。
競プロの記録 (2016_09_24)
今日は星１を６問と、星２を１問解いた。
そのほか中途半端な星２が１問。
「yukicoder: 星２」
愚直にやると10^(2+8)で間に合わない。
指数が小さいほうから計算していき、その都度一つ前のものを利用していけば、毎回丸々指数の分だけ計算する必要は無くなる。
これにより、10^2+10^8で間に合う。
自分はこのやり方で通したが、「繰り返し二乗法」と呼ばれるやり方があるらしい。
これでN乗の計算が、O(N)からO(logN)になる。
どうしても、ＭＯＤをとるのを忘れがちになるのを注意したい。
これは解けなかった。試合数は高々１５試合しかないので試す数は2^15 = O(10^4)となり、全探索することができる。
実装が長く、複雑になりそうなので、Ａ予選を控える今日はやらない。方針は立っているので、後日実装しようと思う。
Ａ予選まであと５分。
競プロの記録 (2016_09_23)
「yukicoder:星１」
N-1を言えれば勝ちである。
自分のターンと相手のターンで１セットとすると、１セットでK+1ずつ進めることができ、これが相手にとって最善であり、
(N-1)が(K+1)で割り切ることができれば相手の勝ちである。
それ以外なら自分の勝ちになる。
理解できる考え方だが、証明はどうやるんだろうか？
ちなみに、自分で実装した時は全探索でDPを用いた。
この辺のコードが比較的短い時間で、考えられるようになったのは成長だと思うが、この問題では計算時間的にACにならない。
今日は久しぶりに、短い時間（２時間程度）ながらも、「競プロのための時間」をとることができた。
これまでも、物理的に時間が取れなかったわけでなく、ただの精神的な甘えだったのだけれど。
昨日、ブログを書く際に、タイトル部分でまとめて書く日付の多さを見て、改めてサボっていた期間の長さを思い知った。
このように、自分の頑張りや生活態度を、小刻みに確認できるのが、ブログをこまめに書くことの利点だと思う。
内容としては、yukicoderの星１を３問と、星２を１問解いた。
Ａ予選まであと１日。ついに明日。
競プロの記録 (2016_09_17,18,19,20,21,22)
この６日間で解いた問題は、yukicoder星１の３問のみ。
体調不良や、友人とのゲーム作成があったとはいえ、これはさすがにひどい。
一日の間、どのように時間を使っているかの記録を久しぶりにやったほうがいいかもしれない。
生活リズム自体が崩れている。
Ａ予選まであと２日。
競プロの記録 (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++; }
この二日間は体調不良でほとんど何もできていない。
季節の変わり目だということを考慮して、もっと体調に気を付けるべきだった。
身体がまともじゃないと何もできないと改めて感じる。
Ａ予選まであと8日。
競プロの記録 (2016_09_14)
＜星１＞
今回の結界のばあい、４辺をそれぞれ直線と考えると、傾きを表す係数は、－１か１になる。
この時、直線上の任意の点はすべて、原点からのマンハッタン距離は等しくなる。
直線と円の接点の座標に関して、マンハッタンン距離をっ求めるだけの問題だった。
（補足）
四捨五入するのでなく、切り上げる場合は、double型の計算値に１を加算する。さらにここから1-e9を引いてからintでキャストする。この減算は、計算値がぴったりだった場合に、＋１されることなく正しい値にするためのものである。
瞬殺問題のハズだったが、終止コドンが途中に含まれた場合を除く処理を（必要ないのに）書こうとしていた。
例を見れば、それを除く必要が無いのはわかったはずだった。
難易度から考えて、実装が割に合わないときは、余計なケースを考えていないか、例もしっかり見て参考にするべき。
＜星２＞
エラトステネスの篩であらかじめ素数のリストを用意しておく。
（初めて使った。ライブラリにしておきたい感覚がなんとなくわかった。）
遷移先に、一つでも自分が勝てる道がある（dp[n - prim]の中に0がある）なら、勝ちである(dp[n]=1)。
dp[0]=dp[1]=1としておくのがポイント。
０と１は負け条件なのにdpが１というのが、感覚的に理解しずらかったが、こうしないとうまくいかない。（要検討）
遷移先のdpが0とは、相手が負けることなので、つまり自分の勝ちを表す。
時間はかかった(90分くらい)が、一発ACだった気持ちが良かった。競プロの楽しさを思い出させてくれる。
定着させるために、再解答リストに追加。
Ａ予選まであと１０日。
