競プロの記録 (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
|
競プロの記録 (2016_09_09)
今日は５問しか解けなった。しかもすべてyukicoderの星１問題。本当に意志が弱い。原因は寝坊と、ネットサーフィン。
ただ、ノルマの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
期待値の線形性を理解する。
出た目の合計値をＮ個分足しているだけなので、１つ１つのサイコロについての目の期待値（今回は3.5）をＮ回足せばよいだけ。
ちょっと数学的に書くと、E[X+Y] = E[X]+E[Y]。
しかし、解けなかった。必死に全パターン計算しようとしていた。
こういう問題を解くための解決策としては、期待値の線形性をいつも頭の片隅に置いておくことがあるが、例が誘導してくれてる場合もあるので気づけるようにしたい。
再解答リストへ追加。
4問目：yukicoder?No.063
No.63 ポッキーゲーム - yukicoder
最初食べた量を出す対象者を勘違いしていた。問題はちゃんと読もう。
普通にシミュレーションしたが、intの割り算の性質を利用して、(L-1)÷(2×K)×Kでよかった。
これならちょうど割り切れるものは１でなく０になってくれる。
何度も言うが、こういうテクニックがすぐに出て売るようでないと、簡単な問題の瞬殺は難しい。
5問目：yukicoder?No.064
No.64 XORフィボナッチ数列 - yukicoder
bitXORの演算子が'^'らしい。覚えた。
はじめ、実際に第N項まで計算していたが10^18だから間に合うはずがない。
排他的論理和の結合法則、同じ数のbitXORは0であること、0とのbitXORはその数自身であることを使うと、F0,F1,F2,F0,F1,F2,・・・を繰り返すのでMOD3を使えば解ける。
再解答リストへ追加。
明日からはブログの更新が日を跨がないようにしたい。
Ａ予選まであと15日。
競プロの記録 (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
回転の回数は最初にカウントしておく必要がある。
今回のように、実験してみて愚直に場合分けするしかないときもあることを頭に入れておく。
Ａ予選まであと１６日。
競プロの記録 (2016_09_07)
1問目:yukicoder_No.005
配列Ｗを昇順ソートして、小さいほうから埋めていくだけ。
配列の要素を指定する変数と、現在の箱の個数を記憶しておく変数に同じものを使っていたため詰まった。
一つの変数に複数の意味を持たせるのはバグの元。
2問目:yukicoder_No.018
負の値の剰余をとってもうまくいくようにする方法があるらしい。
割る数の巨大な倍数をあらかじめ足しておくという方法。
今回の場合は次のようなコードになる。
再解答リストに追加。
tmp = (26000 + (s[i] - 'A') - (i + 1)) % 26 + 'A';
まだこの方法には慣れていないので、数をこなして自然に使えるようにしたい。
3問目:yukicoder_No.021
グループが３個以上のため、平均が最小、最大の集合は、それぞれ要素数１になる。
従って、今回は最大値と最小値の差をとるだけでよい。
問題文と例の文章に騙されて余計なことをやっていた。
また、この問題では結局必要なかったが、整数型を四捨五入する方法を作った。
割る数と割られる数をそれぞれ１０倍したうえで計算する。それに５を加算して、１０で割る。
そのほかにも、先にdouble型で計算しておいて、0.5を足してintでキャストする方法もある。
4問目:yukicoder_No.022
文字列を先頭から見ていく。
左括弧に出会ったときは、第一引数にその位置、第二引数にその左括弧に対応する右括弧の位置（とりあえず-1にしておく）を持つpairを、
stackにpushする。
右括弧に出会ったときは、topの第二引数にそこの位置を入れて、topをsetにinsertした後、popする。
文字列を終わりまで探索すると、括弧の対応位置を要素に持つsetができる。
Kに対応するsetの要素にアクセスすれば答えが出せる。
5問目:ABC043_C
C: いっしょ / Be Together - AtCoder Beginner Contest 043 | AtCoder
変換先の数字をすべて試すだけ。
6問目:ABC039_C
C: ピアニスト高橋君 - AtCoder Beginner Contest 039 | AtCoder
あらかじめ、ドから順に並んだW,Bの文字列を連結させたものを長めに作っておく。
入力文字列を頭の方から順に、substrで２０文字分抜き出し、事前に作った文字列とどこで一致するか調べる。
音の名称を入れた配列に、発見位置のMOD12でアクセスすれば答えになる。
文字数の比的に、入力文字列に必ずしもドから始まる標準文字列が入っているわけではないことに注意。
基礎的な問題（yukicoderの☆１とか）で時間を想像以上に使う。明日からは簡単な問題を多めにして、基礎体力とスピード感をつける。
Ａ予選まであと１７日。
