2019-03-19

300点のエッセンス

ブログのネタがなさすぎてサボっておりました（おい）。

最近競プロが楽しくてたまらないです。AtCoder のレートももうすぐ1,200となるため、一つの目標である水色レートは到達できそうです。

さて、ここ数ヶ月間は300点問題を埋めるのに時間を費やしてきました。もちろん、上を目指すならもっと配点の高い問題をやるべきなのですが、上の難易度の問題をやる前に基礎が抜け落ちていないかチェックしたいという気持ちが大きかったのでこのような練習をしています。

まだ全ては解いていないのですが、もし緑色レートあたりを目指している人に何か役立つ情報が提供できないかなとふと思ってこの記事を書きました。AtCoder 300点の問題でこれはとてもいい練習になるなと思うものをいくつかピックアップしておきました。多すぎてもアレなので、めちゃくちゃ絞っています。また、最近のコンテストの問題はあまり選ばないようにしてあります（始めたばかりの人はもう見てしまった人も多いかと思うので…）。

若干のネタバレを含む（解法の方針的な内容）のでネタバレしたくないよ〜！っていう人は後半のネタバレ注意以降の部分は読まないようにお気をつけてください！

問題集

配点はすべて300点です。ネタバレ等はこの問題集より後にまとめてあります。

C - 4/N (Tenka1 Programmer Contest 2017)
C - One-stroke Path (ABC054)
C - Digits in Multiplication (ABC057)
C - Dubious Document 2 (ABC076)
A - Getting Difference (AGC018)
C - 高橋君とカード / Tak and Cards (ARC060)
C - 白昼夢 / Daydream (ARC065)
C - Factors of Factorial (ARC067)
C - Snuke Festival (ARC084)

ネタバレの前に

この9問に含まれる要素を本番でもきちんと書けるならおそらくABCなら300点の打率（コンテスト中のAC率）は7割超えると思います。あとは writer さんや問題の内容にできるだけ偏りがないこと、300点に限らずさらに上の問題でも使えることなどいろいろ気を使ったつもりです。

主観がかなり入っているし、筆者もそこまで競プロでめっちゃ強い人！ベテラン！という訳ではありません（冒頭でも述べた通りレートにして水色手前ぐらいです）ので、「こっちの問題の方が5億倍ええやろ！」みたいな感想もあるかと思いますが、大目にみてください。お願いします。

以下ネタバレを含みます！！！！

ネタバレしてもいいよ〜！という人は進んでください。全問一気に出ます。

Σ(っºΔºc)...

ネタバレと選んだ理由的なこと

1. 4/N

200点でももちろん全探索は出てくるのですが、この問題はきちんと3500の3乗から3500の2乗に落とせば間に合うな、と時間計算量の感覚をきちんとつかめているか、全探索を考えられるかの練習にはとてもいいと思います。うっかり 0 で割らないように気をつけてほしいというのもお気持ちとして少しあります。

2. C - One-stroke Path

next_permutation 使ってO(N!)で解いてもいいし、深さ優先探索で解くのもいいし、グラフの簡単な練習にもなるのでおすすめです。いろいろな方法で解いてみましょう。

3. C - Digits in Multiplication

約数列挙がO(sqrt(N))でできるというのは300点〜400点あたりで結構出てくる印象があります。おそらく約数列挙の中ではかなりシンプルな方の問題です。

4. C - Dubious Document 2

文字列操作、辞書順最小みたいな問題は忘れた頃に出てくる感じですね…。数問は解いておいた方がいいと思います。

5. A - Getting Difference

300点で頻出なのがGCDなんですが、コンテストでちゃんとGCDと気づく鋭い勘は鍛えておいた方がいいと思います。この記事を書いた時期に近いコンテストだと、C - Monsters Battle Royale とかですかね。

Getting Differenceは入力例に対して出力がPOSSIBLEかIMPOSSIBLEのいずれかなので、入力例、出力例からメタ読みはほぼ不可能で、ちゃんと考察しないとGCDが導けません。

6. C - 高橋君とカード / Tak and Cards

部分点解法はもう大丈夫だと思うんですが、満点解法のDPはやってないとおそらく思いつかないはずです。DPは慣れないうちは本当に難しく感じるし、バグも埋め込みやすいのですが、DPの問題だけを寄せ集めたコンテスト（Educational DP Contest - AtCoderとか）もあるくらいですから感覚を養っておくと必ず役に立ちます！300点どころか400点以上も解けるようになる可能性がグーンと上がります！

この問題は最近の300点に比べたら少し難しめかもしれません…がビギナーコンテストの参加者のレベルがインフレしているのでこれくらいの問題が普通に出てもおかしくない状況です。

7. C - 白昼夢 / Daydream

Codeforces とかだと(と)が正しい入れ子になっているか解析してください、みたいな問題は出るのですが AtCoder だとなかなか見ないですね…。最近数列系の問題がやたら多いのでそろそろ出てきてもおかしくない気がします。

もちろん文字列の左側からパースしても解けるのですが、解説を見て「後ろから見るとよい」「ある文字列が他の文字列のprefixになっているかどうか」あたりの知見を得るだけで、文字列問題で打つ手が増えて嬉しい気持ちになると思います。

8. C - Factors of Factorial

素因数分解と正の約数の個数と階乗の性質がセットになっていて、さらに mod (10⁹ + 7) を正しく処理する練習もできて嬉しい問題だと思います。

9. C - Snuke Festival

数列をソートして大きい順に取るとかみたいな問題は200点問題でもやるのでそれは選ぶ必要ないなと思いました。この問題は、ソートして二分探索して数え上げするという基本要素が組み合わされただけですが、めちゃくちゃ良問だと思います。

2019-02-27

タイピング練習の Tips

雑記

コンピュータを使っている以上、タイピングのスピードや正確さはずっと付きまとう問題です。タイピングに苦手意識がある人、もっと速く、正確に打てるようになりたい、と思う人はできるだけ早いうちに克服した方が絶対にいいと思います。

ここで、ぼくが今までタイピングしてきてここだけはきちんとおさえた方がいいなと思うコツを書いておきます。

一応書いておきますが、ローマ字入力が前提です。最後の方に英語タイピングについても少し補足しておきます。かな入力に関しては一切取り扱いません。

読んでほしい人

人差し指打法とか自己流でとりあえずキーボードを打っている人
パソコンをよく使うのに、キーボードの入力が手書きのスピードと大きく変わらない人、もしくは手書きより遅い人
タイピングのスピード自体は実用上ではあまり困っていないが、もう少し練習したい、速度と正確さをあげたい人

筆者のタイピング力

ミスらず打てるなら平均 7.0 key/s、高火力出すなら 8.0 key/s 〜といった感じでしょうか。普通の日本語の文章なら、5分くらいで 1,800 〜2,000 文字くらいはほぼミスなく打てるんじゃないでしょうか。

寿司打高級コース普通で 18000円くらい、一発勝負で最高 11980円（全2）
e-typing 腕試しレベルチェック Max 598

このスピード保ってノーミスは本当に辛い… pic.twitter.com/iFA1AFQCnt
— 白狐🦅 (@Arthur_Lugh) 2019年2月26日

動画で速さを確認するならこのツイートですかね。この動画のゲームのモードだと、1文字でも打ち間違えると終わりなので気持ち少し遅めになっています。

英文のタイピングについても同様くらいのスピードで打っています。

(っ_¯꒳¯_c)ｴｯﾍﾝ

速く正確にタイピングが何が嬉しいのか

基本的に嬉しいことしかありません。

文書作成やブログ書く時とか、大学でレポートを書く時とか、ちょっとしたツイートする時とか、そんな時基本的に速くて困ることはまずないでしょう。タイピングが遅い人より、速い人の方がこういう文章作成時の誤字率は少ないと思います（これは個人的な感想なので要検証ですが）。

パソコンとかが普及した現在では、手書きで綺麗な文字が書けることよりもパソコンでタイピングが速く正確に打てることの方が重要なのではないでしょうか。

タイピングのコツ

それでは本題。3点に絞っておきました。

1. ホームポジション

ご存知の方はこの部分は飛ばして構いません。

happylilac.net

このサイトの図で指の正しい使い方は一発です。

左手をA（小指）、S（薬指）、D（中指）、F（人差し指）、スペースキー（親指）、右手をスペースキー（親指）、J（人差し指）、K（中指）、L（薬指）、セミコロン ;（小指）に置きます。これをホームポジションと一般に言います。

人差し指を置くFとJのキーに小さい突起が付いているのはキーボードを見なくてもここに人差し指を置いてあとは自然に指をおけばホームポジションになるよ！という印です。

2. ローマ字入力

https://www.e-typing.ne.jp/datas/roma/roman_matrix.pdf

ヘボン式のローマ字を覚えている人が多いと思いますが、タイピングでは訓令式の方が打ちやすいので慣れないうちは訓令式で打っておくと良いと思います。ただし、一部の文字に関しては例外的にヘボン式を用います。

URL の e-typing というサイトのローマ字表は、ぼくが普段タイピングする時のローマ字表とほぼ同じものです。

50音に関して、あいうえおは1文字、か行〜わ行まで2文字で統一されていてとても覚えやすいと思います！！

ただし、e-typing のローマ字表にもあるように、「ん」に関してはNを1文字ではなくNNと2文字重ねて打つのがタイピング界では主流な気はします（要出典）。

「ん」においてNを2個重ねる理由としては、例えば「今夜」とか打つ時に「konya」と打つとおそらく「こにゃ」と出てきてしまうと思います。日本語変換は賢いものが多いので「こにゃ」で変換しても「今夜」に変換されるものが多いですがこういう例もあるので基本的に「ん」を打つ時はNを2回重ねます。

もちろん、Nを1個にしても全く誤解のない文字列（例えば、「新春シャンションショー」はどの「ん」をNを1個で打ってもひらがなではきちんと「しんしゅんしゃんしょんしょー」と出てくる）であれば、Nを1個で打っても構わないとは思いますし、その方が速く打ち間違えも少ないですが、慣れないうちはNを2個重ねる習慣をつけておくことが望ましいです。

3. 手元を見ないで打てるようになる（タッチタイピング）

一部ではいまだに「手元を見ずに文章をキーボードで入力できること」を「ブラインドタッチ」と言ってる人もいるようですが、この用語はタイピング界では差別用語として嫌われているので、手元を見ずにタイピングすることを基本的には「タッチタイピング」という方が望ましいです。

さて、手元を見ないで日本語入力を打てるようになるコツですが、段階を踏んで練習していくといいと思います。僕の場合だと

母音あいうえおの配置（A, I, U, E, O）をしっかり覚えて手元を見なくても正確に打てるようになるまで指に馴染ませる
か行〜わ行までのひらがな1文字をしっかり覚えて1と同様に覚える
「しゃ」「ちゃ」「〜だった」のような文字列について1と同様にする
無料のタイピング練習サイトなどを使って短文を手元を見ずに打てるようになる（速度や正確さは放置する）
タイピング練習サイトなどを使って長文を手元を見ずに打てるようになる
4, 5 に慣れてきたら少しずつタイピングのスピードを上げる。ただしミスが多くなりすぎるようなスピードでは打たない

という感じでしょうか。タイピングの練習サイトについては後でいくつか挙げておきます。速く正確に打てるようになるには基礎を固めるしか方法がありません。

数字や記号についてはここまで見ないで正確にタイピングするのは結構難しいと思うので、後回しにして構わないと思います。

タイピング練習サイト

タイピングの練習にオススメのサイトを挙げておきます。5~10分あれば暇な時にいつでも練習できるサイトなので気に入ったサイトがあればブクマしておくといいと思います。

1. Easy タイピング

neutralx0.net

ホームポジションや基本的な日本語入力の確認に使ってみるといいと思います。

2. e-typing

www.e-typing.ne.jp

十数年前くらいからあるサイトです。無料で短文から長文まで様々なジャンルの文章で練習が可能なこと、練習結果がスコア化され、苦手キーやスピード、正確さなど細かく分析してくれるのが特徴です。また、ローマ字入力だけでなく、英文入力の練習もできるようになっています。

3. 寿司打

typingx0.net

ここも有名だと思います。ゲーム感覚でタイピングが上達するサイトとしてはこれ以上良いところはないと思います。

いかがでしたか？？？

基礎さえしっかりしてしまえばセンスとかそういうのもほぼ関係なく簡単に上達するのがタイピングのいいところだと思います。1日数時間とかかけて練習する必要はありませんし、毎日5分とかでいいので試してみてはどうでしょうか(っ_ ॑꒳ ॑_c)

けものみち

まったりと、きのむくままに。