競プロの記録 (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だった気持ちが良かった。競プロの楽しさを思い出させてくれる。
定着させるために、再解答リストに追加。
Ａ予選まであと１０日。
競プロの記録 (2016_09_13)
今日は新規に１０問、再解答２問を消化した。
＜星１＞
#18169 No.138 化石のバージョン - yukicoder
１文字ずつ比較していったが、１文字ずつ何十倍かして足し合わせたものを比較する方法もある。
No.146 試験監督（1） - yukicoder
MODの取り方をどこまでやるかが難しい。
また、10^9+7は次のコードで書けるらしい。
long long MOD = 1e9 + 7;
No.163 cAPSlOCK - yukicoder
変換した後charでキャストするのを忘れがちになる。
小文字と大文字の変換には('a' - 'A')を使っていたが、
次のような関数もあるらしい。
意味は名前の通りである。
islower(c), isupper(c), toupper(c), toupper(c)
Ａ予選までに次のアルゴリズムを使えることを目安としたい。
（かなり今更だが、yukicoderを参考にして決めた。）
[参考: http://yukicoder.me/wiki/guide]
今週中に１アルゴリズムに関して、最低２問ずつは解きたい。
Ａ予選まであと１１日。
競プロの記録 (2016_09_12)
今日は星１が４個と、星２を一問だけ解いた。
＜星１＞
３項の最大値と最小値の判定は、min(a,min(b,c))、max(a,min(b,c))でできる。
２項目が中央値でない判定は次のように行えばよい。
min(a,min(b,c)) + max(a,min(b,c)) != a + c
順方向にシュミレーションすると計算量が多くなる。
最終的に一番上になるカードの位置を、後の手順の方からシミュレーションする。(i : N-1 -> 0)
最後に一番上になるカードの位置を、posとする。（当然、最後は一番上になるから初期値は1）
A[i]を後ろから見ていって、posが１ならpos=A[i]とし、pos
競プロの記録 (2016_09_11)
今日は新規４問を解き、ABC045へ参加した。
計算上の直径を超えるまで半径を１ずつ増やすとかしていたけど、
計算上の半径の２倍に１足してintでキャストするだけでよかった。
２問目
No.99 ジャンピング駒 - yukicoder
偶数座標にコマ１つと、奇数座標にあるコマ１つのセットで、この２つのコマが消える。したがって、その二つを数え上げて、差を出してやればよい。
文字列を頭から見ていって、毎回２倍し、右ならそこに１加算する。
入力文字列の中の、i(奇数)文字の部分文字列は回文となっている。
サイズiの文字列はL-i+1個含まれいる。
iを大きくしながらカウントする。
５問目
No.112 ややこしい鶴亀算 - yukicoder
与えられる入力X[i]のパターンは２種類。
X[i]のうち、大きいほうの数が鶴の数、小さいほうの数が亀の数になる。
setで数を記録したりとかしていたけど、もっと簡単な方法があるのだろうか。
結果は、２完で１６６位、レートは３４９。
悔しい。さすがに３完はしたかった。
次回の目標はレート3完で650以上。
Ａ問題
A: 台形 / Trapezoids - AtCoder Beginner Contest 045 | AtCoder
やるだけ。
Ｂ問題
B: 3人でカードゲームイージー / Card Game for Three (ABC Edit) - AtCoder Beginner Contest 045 | AtCoder
シミュレーションする。
ルールの読み間違えで手間取った。
終了条件は「０枚自分の番を迎える。」なのに、「０枚になった瞬間」かと思っていた。
Ｃ問題
B: 3人でカードゲームイージー / Card Game for Three (ABC Edit) - AtCoder Beginner Contest 045 | AtCoder
bitと使って全探索するだけ。
何ビット目かす変数jと、今見ている位置を同期させればシンプルでうまくいく。
しかし、ビットの進む方向と、文字列を見ていく方向が逆（数字の増え方は同じ）だったため、ここで詰まってしまった。
図を書くときに、位置の「数字」もしっかり書き込むことで改善できそう。
本番中は解けなかった。
制約が|S|<=10の時点で、bit探索を思いつくべきだった。
やはり「まずは全探索を考える」ことが大切だ。
この習慣は持っておきたい。
（補足）
stringからintへの変換に、stoi()は使えないらしい。
普通にS[i]-'0'で数値に直すのが無難。
久しぶりにABCにリアルタイムで出場した。
強くなりたいなら、やはりコンテストに出続ける必要があると感じた。
コンテスト中の必死さやアイディアが出ないもどかしさ、
コンテスト後の悔しさや練習不足への後悔など、
モチベーションを大きく刺激してくれる。
まずは今回のＣのような問題を確実に解き切れるようにしなければならない。
そのためには、yukicoderの星１問題だけではこの手のアイディアの蓄積ができないし、
そもそもAtCoderの問題とyukicoderの問題では簡単な問題の傾向がかなり違うように感じられる。
CODEFESTIVALの予選だと、それほど求められない要素も多いような気がする。
そこで、今後１週間の１日当たりのプランは次のように定める。
1.yukicoder(星１):３問 (15×3分程度)
※勢いをつける。
2.yukicoder(星１):４問 (50×4分程度)
※定番アルゴリズムを身につける（思い出す）。
3.再解答(60分程度)
※必要なことだが解き直しはモチベーション的につらいため時間で区切る。
これを最低ノルマとする。空いた時間は、yukicoder(星１)を解き続け、AC癖をつけた。
また今後は、記事に書くのは基本的に星２以上の問題に限り、
星１問題は、よほどきになった点以外は記事にしないか、新しく知った小ワザ等のみをまとめて書く。
Ａ予選まであと１３日。
競プロの記録 (2016_09_10)
今日は新規７問、再解答３問を解いた。
1問目：yukicodere_No.069
No.69 文字を自由に並び替え - yukicoder
要素にstringを持つ配列はsortできるけど、string自体をsortすることはできない。（たぶん）
今回は26持ち分のカウントを作って、それが一致しているかを見た。
2問目：yukicodere_No.070
No.70 睡眠の重要性！ - yukicoder
分単位に直して、起きた時刻から、寝た時刻を引けばよい。
差が負になったら２４時間を足す。
時計の図的にイメージすれば、この２４時間を足す処理は自明だが、
これもまた場合分けでやってしまった。
こういう風なアイディアはどうすれば思いつくようになるのだろうか。
yukicoderの星１のような問題を解き続けて慣れることが、それにつながる気がする。
補足。
VisualStudioだとscanf()が使えず、scanf_s()にする必要があるが、提出の時はscanf()に直す必要があるようだ。
3問目：yukicodere_No.079
No.79 過小評価ダメ・ゼッタイ - yukicoder
投票数を配列に保存して、後ろの方から票数の大きいものを探していけばよい。
4問目：yukicodere_No.082
No.82 市松模様 - yukicoder
市松模様は前後左右が異なる色になっている。
これは左上のマスからのマンハッタン距離の偶奇で塗る色を決定できる。
5問目：yukicodere_No.083
No.83 最大マッチング - yukicoder
できるだけ「1」(2本分)を使って数値の桁を増やしたほうが良い。
最大桁の数字に関しては、Nが奇数の時は「７」、偶数の時は「１」にする。
他の数字に関しては考える必要がない。
自分にしてはよく思いついたなと思う。
今回のように「この難易度で、こんなに場合分けやパターンを考えるハズがない。」と、
感じたときは、たいていこのようなひっかけがある。
6目：yukicodere_No.088
No.88 次はどっちだ - yukicoder
コマの数の偶奇だけで決まる問題。実は局面は無意味。
先手の名前によって出力を変えなくてはいけない。
はじめ、入力があった時点で先手後手の名前を登録していたがそんなものは必要ない。次のように書ける。
if ((S == "oda") == (cnt % 2 == 0)) cout << "oda "<< endl; else cout << "yukiko" << endl;
7問目：yukicodere_No.089
No.89 どんどんドーナツどーんといこう！ - yukicoder
断面積に断面の重心動く距離をかけてものが体積になる。
これは感覚的に計算してしまったけど、ちゃんとパップス・ギュルダンの定理というもので証明されているらしい。
（補足）
C++（VisualStudioだけ？）でM_PIを使うときは、次のようなマクロと、インクルードが必要らしい。
>|cpp
#define _USE_MATH_DEFINES
#include
|
