A問題の傾向と対策

はじめに

先日、茶色diffの傾向と、緑になるための対策 - dokinの競技プログラミングという記事を投稿しました。
この記事では、茶色diffが解けるようになるためには何が必要かを考察しましたが、そもそも灰色diffが解けるようになる段階でどういう能力が必要かわかっていないと正確な議論ができないと思ったので、以降何回かに分けて灰色diffの考察していきたいと思います。
まずは、ABCのA問題について、分類・考察していきます。

A問題の分類

対象はABC126～ABC178(現在の6問形式で開催されるABC)、2019年12月以降のABC級コンテストです。問題の解き方のネタバレが載っているので、閲覧注意でお願いします。

整数型とif文

A - Iroha and Haiku (ABC Edition)
A - AtCoDeer and Paint Cans:場合分けによる数え上げ
A - ABC/ARC
A - One Card Poker:複雑な条件の判定
A - ι⊥l
A - Between Two Integers:論理演算子(&&)の利用
A - Rotation:複雑な条件の判定
A - ABD
A - Happy Birthday!:状態の考察、判定
A - Rated for Me:複数ケースの場合分け
A - 753:論理演算子(||)の利用
A - Christmas Eve Eve Eve:複数ケースの場合分け
A - Rounding
A - Round One:場合分け
A - AC or WA
A - Poor
A - Sheep and Wolves
A - Five Variables:操作のシミュレーション
A - Air Conditioner
A - Not
A - November 30

整数型の計算(加減乗、割る2)

A - Children and Candies (ABC Edit):等差数列の和
A - Tak and Hotels (ABC Edit):場合分け
A - Trapezoids:図形問題
A - Fighting over Candies:判定
A - Addition and Subtraction Easy:場合分け
A - Two Rectangles:図形問題、最大値の計算
A - Restricted:判定
A - RGB Cards:整数問題、判定
A - Expired?:3つ以上の判定
A - ringring:最小値の計算
A - K-City:マス目の問題
A - Meal Delivery:絶対値、最小値の計算
A - Sandglass2:場合分け
A - Bichrome Cells:マス目の問題
A - One out of Three:場合分け
A - Rating Goal
A - Parking:最小値の計算
A - Libra:3つ以上の判定
A - New Year
A - Two Coins:判定
A - Traveling Budget:最小値＋和
A - Cats and Dogs:判定
A - Day of Takahashi:考察による場合分け
A - Colorful Transceivers:複雑な条件の判定
A - Add Sub Mul:最大値の計算
A - Multiple of 2 and N:整数問題(偶奇で場合分け)
A - Task Scheduling Problem:絶対値
A - Garden:図形問題
A - Train
A - Pair:整数問題(偶奇で場合分け)
A - ABC333:整数問題(偶数、奇数)
A - Maximize the Formula:最大値の計算
A - Programming Education:文字列も使用
A - Discount Fare
A - Right Triangle:図形問題
A - White Cells:マス目問題
A - Five Antennas:判定
A - Buttons:操作のシミュレーション、最大値の計算
A - Airplane:最小値の計算
A - T or T:最小値の計算
A - Dodecagon:図形問題
A - Transfer:場合分け、操作のシミュレーション
A - +-x:最大値の計算
A - Password:場合の数の数え上げ(積の法則)
A - Curtain:場合分け
A - 9x9
A - Circle:図形問題
A - Blackjack:判定
A - 500 Yen Coins:判定
A - Beginner
A - Multiplication 1
A - Calc
A - Don't be late:判定
A - box

整数型の計算(割り算,余りなども利用)

A - Restaurant
A - Remaining Time:あまり
A - Sharing Cookies:余り(倍数)に注目した判定
A - Round Up the Mean:切り上げ
A - Product:偶奇判定
A - Buying Sweets
A - Infinite Coins:余りに注目した判定
A - Grouping 2
A - AtCoder Crackers:余りに注目した場合分け
A - B +/- A:整数問題
A - Favorite Sound:場合分け
A - Biscuit Generator
A - Ferris Wheel
A - Apple Pie:操作のシミュレーション
A - Harmony:場合分け
A - Serval vs Monster:切り上げ
A - Duplex Printing:切り上げ
A - The Number of Even Pairs:N個から2個を選ぶ
A - We Love Golf
A - ∴ (Therefore):10で割ったあまり
A - Takoyaki:切り上げ
A - Payment:切り上げ
A - Kyu in AtCoder:if文を用いても解ける
A - Number of Multiples:数え上げ

小数型の計算

A - Entrance Examination:整数同士の割り算
A - Odds of Oddness:確率
A - Circle Pond:図形問題

文字型

A - UOIAUAI:判定
A - HonestOrDishonest:判定
A - HEX:判定、文字コード
A - Double Helix
A - Next Alphabet:文字コード
A - αlphabet:文字コード(isupperを用いてもよい)
A - Keyboard

文字列型

A - AtCoder *** Contest
A - Haiku:文字列の置き換え
A - Three-letter acronym:文字コード
A - Shiritori:文字列の性質の判定
A - ABCxxx
A - Palindromic Number:整数を文字列として受け取るテクニック。整数でも解ける。
A - September 9:整数を文字列として受け取るテクニック。整数でも解ける。
A - Good Integer:整数を文字列として受け取るテクニック
A - Placing Marbles:数え上げ
A - Already 2018:文字列の書き換え
A - Diagonal String
A - abc of ABC:文字列の性質の判定
A - Something on It:前から順に処理
A - Eating Symbols Easy:操作のシミュレーション、前から順に処理
A - AtCoder Beginner Contest 999:整数を文字列をして読み込むテクニック
https://atcoder.jp/contests/abc119/tasks/abc119_a:文字列の性質の判定(場合分け)
A - Changing a Character:文字列の書き換え
A - Security:整数を文字列として読み込むテクニック
A - Fifty-Fifty:文字列の性質の判定
A - Red or Not
A - Tenki:数え上げ
A - Weather Prediction:場合分け
A - Can't Wait for Holiday:場合分け
A - Strings
A - Remaining Balls:操作のシミュレーション
A - Station and Bus:場合分け
A - Coffee:文字列の性質の判定
A - Lucky 7:整数を文字列として読み込むテクニック
A - A?C:場合分け
A - Registration:文字列の性質の判定
A - Rainy Season:場合分け
A - Plural Form
A - Keyboard:場合分け

その他

A - Grouping:配列
A - ABC Swap:操作のシミュレーション
A - Kth Term:配列

考察

C++とPythonでは大きく言語仕様がことなるので、勉強方法も当然変わってくると思います。
わたしはPythonをやったことがないので確かなことが言えませんが、向き不向きは人それぞれだと思います。
どちらかを勉強してみて、自分に合わないなーと感じればもう一方を勉強してみるとよいと思います(投げやり)。
もちろん、JavaやUnlambdaなど別の言語を用いるのもよいと思います。

A問題では、入力の個数が決まっており、for文や配列などの複雑な処理を用いる必要がありません。(配列を使う問題もなくはないですが、例外です。)
そのため、

  • 基本テンプレートと標準入出力
  • 型(int型、double型、char型、string型)の性質
  • 四則演算と余り
  • if文

に関して基本的な扱いを理解していることが最も重要です。
C++で勉強する場合、AGP4bの一章を前から順番に解いていけば、必要な知識をほぼすべて補えます。

さらに、

  • 独特の問題形式に対する慣れ
  • バグが出たときに、どこが間違えているかを見つけ修正する能力
  • どうやって実装するか忘れたときに、インターネットの海から正しい情報を調べる能力

も訓練で鍛える必要があります。

同じA問題でも、難易度や出題形式にバリエーションがあります。
問題文に書かれている通りに素直に実装すればよい問題は簡単です。しかし、
シミュレーションが必要な問題、場合分けが必要な問題などは、頭を使って考える必要があります。
また、文字コードや整数を文字列として受け取るテクニックなど、コードを書く上で覚えておいた方がよい小技もいくつかあります。

レッドコーダーへの道も一歩から、焦らず一問ずつ解いていきましょう。

茶色diffの傾向と、緑になるための対策

はじめに

先日、ツイッターで次のようなツイートをみました。

そこで、今回はABCで緑になるためには何をすればよいのかを、分析したいと思います。

茶色difficultyの問題の分類

対象はABC126～ABC177(現在の6問形式で開催されるABC)です。問題の解き方のネタバレが載っているので、閲覧注意でお願いします。

数え上げ
整数
貪欲
全探索
シミュレーション
確率、期待値
幾何
グラフ
その他

考察

ちゃんと検証していないのでよくわかりませんが、茶diffの問題を8～9割程度安定して正解できれば、緑に到達できると思います。
(difficultyは制限時間内に正解した人全体から算出されるので、時間に余裕を持って正解すれば、体感よりパフォーマンスは高くなります。)

数え上げ

数え上げの問題は数多く出題されていますが、DPを用いた問題は一問しか出題されていません。
それ以前に、「場合分け」「どこを固定してどこを探索するか」「高速化は可能か」などの基礎的な分析力を叩き込む必要があるのかもしれません。

整数

エラストテネスの篩が近年頻出ですが、茶diffではもう少しシンプルな問題が出題されています。

  • 範囲を絞って全探索する
  • 素因数分解した形を考える
  • modによる場合わけを考える

といった考え方は数学にも共通しています。
数え上げ、整数どちらにしても、プログラミング独特の考え方というより、高校数学の「場合の数」「整数」の考え方が使えることが多いです。
プログラミングの問題は数が限られているので、数学の参考書で勉強してみるのもそれなりに有効だと思います。

全探索

bit全探索の問題はたいてい緑diffでしたが、最近は茶色diffのことが多いです。
bit全探索の問題は、制約がN<=20など小さいのでそこから見抜きましょう。
dfs全探索などは今のところ必要なさそうです。

シミュレーション

意外と多かったのが、シミュレーション問題です。
「操作を何回かするので、操作後の状態を答えてください。」というタイプの問題です。
サンプルをもとに「操作によって状態がどのように変化していくか」をじっくり洞察する必要があります。

グラフ

グラフの問題は2問しか出題されていません。
グラフ上のアルゴリズムや探索については知らなくても緑にはなれると思います。
ただし、灰diffでグラフの問題は出題されているので、基礎的な概念(隣接リストを用いた管理など)や問題をグラフに落とし込む方法については知っておいた方がよいです。

まとめ
  • 「やりたい作業を自由に実装できる」ことは茶色では前提。
  • ○○法のようなアルゴリズムは緑になるには知らなくてもよい。
  • 考察パターンは典型といえども多岐にわたる。

AtCoder社員のりんごさんがCodeForcesのブログで、競技プログラミング(とくにAtCoder)でのスキルは

  • observation(問題に対する洞察力)
  • strategy(コンテスト時の戦略)
  • typical pattern(典型パターンの習得)
  • implement(実装)

に大別されるという趣旨のことをおっしゃっていました。

典型パターンにたどり着くための洞察は、軽視されがちですが、茶色でも多様な解き方が求められる以上必要不可欠です。
「洞察力」はじっくり問題を考えること、「典型パターン」はたくさんの問題を解くことで習得できます。
簡単な問題が解けないとき解説ACするのは知らなかった技術を習得できるので意味がありますが、難しい問題をむやみに解説ACするのはじっくり考える機会を失ってしまうかもしれません。
一つ一つの問題を無駄にせず、どういう洞察ができるか、どのような典型パターンでほかの問題とつながっているかを意識することが大事だと思います。


以上です。また加筆したいと思います。



CODE FESTIVAL 2016 qual C E 順列辞書

問題

atcoder.jp

考察

まずは、部分問題を考えます。
p_1\ldots p_nの中に0が含まれない場合の答えを計算してみます。
これは、 \sum_{i=1}^N (N-i)! \times |\{j|j > i,p_j < p_i\}|であることが確認できます。

そこで、一般の場合は、
各x,yに対し、
C_{x,y}: |\{j|j > x,p_j < p_x \}|=yとなる順列の数
とおき、 \sum_{x,y}^N (N-i)!*y*C_{x,y}を計算すればよいです。

これだとO(N^2)ですが、さらにC_{x,y}*yに注目して、
D_x:j > x,p_j < p_xなるjの数を全ての順列について足しあげたもの
とおいて、 \sum_{x,y} (N-i)!*y * D_xを計算すればよいです。

これで勝ったも同然で、p_x,p_jが0か0でないかで4通りに場合分けし、それぞれきちきち計算すればD_xは高速に計算できるので、答えが求まります。
実装は場合分けが多いのでやや大変でした・・・

感想

ひと月ほどまえ考えた際には歯が立たなかったのですが、いま考えたらすんなりいったのでよかったです。
まずは、0が含まれない場合を計算して、それらの和を別方向からみて足し上げるのが鍵でした。

提出コード

atcoder.jp

ARC067F YakinikuRestaurants

はじめに

解いて印象に残った問題の概略はツイッターに書き込んでいたのですが、それだとネタバレになってよくないので、ブログに書くことにしました。(あくまでも自分の理解のために書いているだけなのでそこまで真剣には書いていません。ご了承くださいm(__)m)
「YakinikuRestaurants」は初めて問題を見てから二か月以上、時々考えていたのですがやっと解くことができました。
解説と全然違う解き方だったので、記事にすることにしました。

問題

atcoder.jp

1<=i <=j<=Mに対し、
happy(i,j):入った焼き肉店のうち左端が店i,右端が店jであるときの幸福度の最大値
とおきます。
min{happy(i,j):1<=i<=j<=N}を求めればよいです。
各happy(i,j)の計算は安直な方法だとO(M)とかO(MlogN)かかるので、TLEしてしまいます。なんらかの工夫が必要です。

そこで、次の2つの方針を考えました。
1．happy(i,j)を高速に計算する。
2．F(i)=min{happy(i,j):i<=j<=M}を高速に計算する。(O(M)とかO(N)ならOK。O(NM)はアウト)

1は厳しそうだったので、2を中心に考察します。
F(i)=f(i,j)となるようなjをG(i)とおきます(i<=G(i)<=N)。G(i)としては複数の値が考えられますが、一番小さいものでもとっておけばよいです。
このG(i)の値に注目しながら、頭の中でぐだぐだと考えていると、Gがiに関して単調増加であることに気づきました。
(証明はちゃんと書くと大変だけど、正しいはず。)
単調増加といえば尺取り法なので、G(1)からG(N)の値を尺取り法の要領で計算すればよさそうです。

でも、実はうまくいきません。尺取り法でG(i)の値を計算するためには、happy(i,j)(max(i,G(i-1))<=j<=N)の値をすべてみないといけないからです。
ここで困り果ててしまったのですが、どきんさんは日ごろの行いが良いので、天啓が降ってきました。

G(i)の値を計算する順番を工夫することで、計算量を大幅に削減できるのです。
たとえば、G(1)をはじめ計算するのではなくG(N/2)を計算してみましょう。
するとこれ以降の計算では、
・G(i)(i < N/2)については、happy(i,j)(i<=j<=G(N/2))
・G(i)(i>N/2)については、happy(i,j)(max(i,G(N/2))<=j<=N)
をみれば十分なので、G(N/2)の値によらず、探索空間が一気に半分になります。
以下同様に、中間を縫うように計算していけば、happy(i,j)の計算回数は高々O(NlogN)回にできます。

各happy(i,j)はセグ木を使えばO(MlogN)で計算できるので、全体の計算量はO(NM(logN)^2)となり、まにあいます。

実装

セグ木をM本用意しないと解けないのですが、やり方がわからず困り果てていました。
ABC157Eにセグ木を26本使って解く方法があることを思い出し、他の方の提出を見ると、Segment_Tree < vector< int>> としてあって、「あーたしかにー」ってかんじでした。。

重い実装でしたが、想定よりも少ないバグで解くことができました(setと書くべきところをsetとしていたくらい)。
でもコンテスト中に解くのはきびしそうです。がんばりたいです。
公式解説では、happy(i,j)を高速に求める方針を用いていました。しっかり図を描いて検証すれば、公式解説の方針に用意気づけたのではないかと思うと残念です。
私と同じ解法の方は見つけられなかったのですが、ここで用いたテクニック(?)に名前がついているのを知っている方がいれば、教えていただけるとうれしいです。

追記:上記のhappyのようにmin{happy(i,j):i<=j<=M}なるjが単調増加であるような関数のことをmonotone minimaとよび、上のように最小値を求める方法は一般的なテクのようです。教えていただいた方、ありがとうございました。

ABC172感想速報

ABC172の感想です。コンテスト終了と同時に公開する準備の良さです。すばらしいですね()

atcoder.jp

A

文法を知っていればきっと解けます。

B

S[i]とT[i]の異なるものをカウントします

C

Cのわりに難しくないですか？典型っちゃ典型なので、diffはそんなに高くならないとは思いますが。。。累積と二分探索でときました。


D

エラストテネスがはやりすぎています。AtCoder Erasutotenesu Contestですね。


E

N=MのときBの配置が攪乱順列になるので、その漸化式を拡張できないか考えましたが、筋が悪かったです。Ai=Biになっているiの個数に注目して包除原理を使えば一発でした。


F

Nimの必勝法は前提知識です。「(a-x)^(b+x)=cなる最小のxを求めよ。」という問題に帰着できます。xor sumと似たような設定です。(a-x)+(b+x)の和が一定なことに注目すると、各kに対し((a-x)>>k)+((b+x)>>k)の値を決定できます。
あとは、aを超えないように貪欲にa-xの各bitを決定していけばよいです。(桁dpが必要かと思いましたがいらなかったようです。)

 

72位でした。Eで時間を使ったのとFで避けられるペナを出したのが反省点です。あとでちゃんとしたものをあげるかもしれません。。。

ABC171解説

ABC171の解説と感想を書きます。使用言語はC++です。

A αlphabet

atcoder.jp

概要

  • 条件分岐(if文、else文)を用いる
  • char型の文字は大小比較ができる

実装

通常、競技プログラミングの問題を解く際は、「入力を受け取る→処理をする→出力する」の3ステップに分けて、それぞれのステップについて慎重にコードを書いていくのが確実だと思います。ただし、今回の問題の場合は、処理をしながら出力する方が楽なので、「入力を受け取る→処理をしながら出力する」の2ステップで説明します。

入力を受け取る

 入力と制約を確認すると、「入力は、αで与えられる。αは英大文字または英小文字。」と書いてあります。
英大文字や英小文字などの文字は、char型の変数を用いることで、受け取りができます。
*1

下のソースコードでは、char型の変数cを宣言し、入力を受け取っています。

	char c;
	cin >> c;
処理をする

cに入っている文字が大文字ならば答えとして"A"を出力し、小文字ならば"a"を出力するコードを書きたいです。
これは、if文を使って次のように書くことができます。
*2

	if (cが大文字) { cout << "A" << endl; }
	if (cが小文字) { cout << "a" << endl; }

ところで、「alphaが小文字」は、別の言い方をすると、
「cが大文字ではない」になります。
そこで、else文を使うことで、次のようにコードを書き換えることができます。

	if (cが大文字) { cout << "A" << endl; }
	else { cout << "a" << endl; }

さて、「cが大文字」はどのような条件式で書くことができるでしょうか？
一番思いつきやすいのは、すべての場合を書き下す方法だと思います。

	if (c == 'A') { cout << "A" << endl; }
	else if (c == 'B') { cout << "A" << endl; }
	else if (c == 'C') { cout << "A"<< endl; }
	・・・
	else if (c == 'Z') { cout << "A" << endl; }
	else { cout << 'a' << endl; }

この方法でも正解できますが、コードが長くなってしまうので、解くのに時間がかかります。
また、不正解だった時、間違っている箇所を見つけるのが難しくなってしまいます。
もっと良い方法はないのでしょうか？

実は、char型に代入される文字の性質を用いれば、上のコードを簡潔に書き直すことができます。
コンピューターの中では、char型に代入される文字は-128以上127以下の整数と対応しています。それを示したのが以下の表です。(負の数との対応については省略します。)*3

整数 文字
0～31 (制御文字)
32～47 記号('*,'+'など)
48～57 数字('0'～'9')
59～64 記号('=','?'など)
65～90 英大文字('A'～'Z')
91～96 記号('^','_'など)
97～122 英小文字('a'～'z')
123～126 記号('~'など)
127 (制御文字)

*4
詳しい対応関係を知りたい方は、「ASCII」で検索してみてください。wikipedia:ASCII

このように、char型の文字は整数と対応しているので、通常の整数と同じように、足し算や引き算、大小比較をすることができます。*5
今回の場合は、大小比較をすることで、cが大文字であるかを簡単に確かめることができます。
具体的には、
「alphaが大文字→cに対応する整数(65～90)は'Z'に対応する整数(90)以下である。」
「alphaが小文字→cに対応する整数(97～122)は'Z'に対応する整数(90)より大きい。」
という関係性があるので、次のようなコードに書き直すことができます。

	if (c <= 'Z') { cout << "A" << endl; }
	else { cout << "a" << endl; }
まとめ

まとめると、以下のコードを提出することで、この問題に正解できます。

#include <bits/stdc++.h>
using namespace std;

int main() {
	char c;
	cin >> c;

	if (c <= 'Z') { cout << "A" << endl; }
	else { cout << "a" << endl; }
}

類題

A - Next Alphabet　char型の文字に対する「足し算」を使うことで、簡潔に解けます。

B Mix Juice

atcoder.jp

概要

  • 配列を用いて入力を受け取る。
  • 合計金額を最小にする→安いものから順番に買う。
  • sort関数を用いることで、安いものから順番に並べることができる。

考え方

N個の果物からK個の果物を買って、合計価格を最も安くするためには、安い果物から順番に果物を買っていけばよいです。
サンプルで見てみましょう。

入力例1
5 3
50 100 80 120 80

この場合、N=5,K=3,p[1]=50,p[2]=100,p[3]=80,p[4]=120,p[5]=80です。
50円,100円,80円,120円,80円の5個の果物があり、そのうち3個を買ったときの合計価格は、最も安くていくらになりますか？という問題です。
プログラミングの問題だと意識せず、算数の問題だと思って解くとわかりやすいかもしれません。
安い順番に果物を並べると、50円,80円,80円,100円,120円になるので、合計価格の最小は、50+80+80=210円です。

そこで、この流れに沿って、以下の順番にコードを書いていきましょう。

  1. 入力を受け取る。
  2. p[1]からp[N]を小さい(安い)順番に並べなおす。
  3. 安いものから順にK個足し合わせる。
  4. 答えを出力する。

実装

B問題の実装には、for文や配列など、A問題の実装よりも高度な知識が必要になります。

入力を受け取る。

入力は、整数N,Kと、整数列p[1],...,p[N]で与えられます。
まず、int型の変数N,Kを宣言し、受け取ります。

int N, K;
cin >> N >> K;

続いて、整数列p[1]…p[N]は配列を用いて受け取ります。
配列の添え字はp[0]から始まるので、p[1]からp[N]まですべての入力を受け取るためには、最低でもN+1個の要素を確保する必要があります。

以下のコードでは、vectorを用いて、要素数N+1個の配列変数を宣言し、for文を用いて入力を受け取っています。
*6

vector<int> p(N + 1);
for (int i = 1; i <= N; i++) {
	cin >> p[i];
}
p[1]からp[N]を小さい(安い)順番に並べなおす。

配列の順番を小さい順に並べなおすには、sort関数を使うのがすごく便利です。
*7

sort(first,last)//[first,last)の範囲を小さい順に並べる(ソートする)。

今回は、一番前の次の位置(p[1])から、一番後ろまでをソートしたいので、

sort(++p.begin(), p.end())//++を前につけると次の位置に移動する。

とします。
細かい意味はよくわからないかもしれませんが、そういうものだと思ってください。
私もよくわかっていませんが、そういうものだと思っているうちにいつのまにか使いこなせていたりします。

安いものから順にK個足し合わせる。

今、p[1]からp[N]まで安い順に並んでいるので、p[1]からp[K]までを順番に足し合わせればよいです。
まず、答えを格納する変数ansを宣言し、0に初期化します。
続いて、for文を用いて、ansにp[1]からp[K]を順番に足し合わせていきます。

int ans = 0;
for (int i = 1; i <= K; i++) {
	ans += p[i];
}
出力する。

ansを出力します。

cout << ans << endl;
まとめ

まとめると、以下のコードを提出することで、この問題に正解できます。

#include <bits/stdc++.h>
using namespace std;

int main() {
	int N, K;
	cin >> N >> K;
	vector<int> p(N + 1);
	for (int i = 1; i <= N; i++) {
		cin >> p[i];
	}

	sort(++p.begin(), p.end());

	ll ans = 0;
	for (int i = 1; i <= K; i++) {
		ans += p[i];
	}

	cout << ans << endl;
}

C One Quadrillion and One Dalmatians

概要

  • まずは文字列の長さを求めて、それから具体的な答えを求める。

考え方、実装

幅優先探索を使うとO(N)でシンプルに実装することができます。(例:D - Lunlun Number)
しかし、今の問題でその方法をするとTLEしてしまうので、Nの値から直接答えにアタックする必要があります。
今回は、考え方と実装を同時に説明していきます。

入力を受け取る。
long long N;
cin >> N;
犬の名前の長さを求める。

まず、犬の名前は短い順に並んでいるので、N番目の犬の名前の長さLが気になります。
例えばN=27のときL=2、N=123456789のときL=6です。

犬の番号 名前の長さ
1～26 1
26+1～26*26+26 2
26*26+1～26*26*26+26*26+1 3
... ...

つまり、

  1. N<=26のとき、L=1で終了
  2. Nから26を引く。
  3. N<=26*26のとき、L=2で終了
  4. Nから26*26を引く。

・・・
のような操作を行えばよいです。
前もって、26の累乗を求める再帰関数を書いておき、while文を用いて実装するのが簡単だと思います。

long long power_26(int a) {
	if (a == 0) { return 1; }
	return 26 * power_26(a - 1);
}

int L = 1;
while (N > power_26(L)) {
	N -= power_26(L);
	L++;
}
犬の名前を求める。

さて、長さLの単語のうち、辞書式でN番目の単語を求める問題を解きましょう。
ところで、「K桁の整数Mが与えられたとき、その各桁の値d[1]…d[M]を上から順に求めよ」という問題には、次のような実装を行いました。

vector<ll> ans(M);
for (int i = 0; i < K; i++){
	d[K - 1 - i] = M % 10;
	M /= 10;
}

今回の問題は、Nを10進法(0...9)の代わりに26進法('a'…'z')だと思って、同じことをやればよいです。
ただし、1番目の単語が"aa…a"(="00...00")なので、Nから1を引く処理が必要です。

N--;
vector<char> ans(L);
for (int i = 0; i < L; i++){
	ans[L - 1 - i] = N % 26 + 'a';//'a'を足すことで、0...25を'a'...'z'になおす。
	N /= 26;
}
出力する。
for (int i = 0; i < L; i++) cout << ans[i];
cout << endl;
まとめ

まとめると、以下のコードを提出することで、この問題に正解できます。
Submission #14616506 - AtCoder Beginner Contest 171

D Replacing

atcoder.jp

概要

  • クエリの問題は、データの持ち方を考える。

考え方

この問題はクエリを順番に処理していくタイプの問題です。
処理の流れは次のようになると思います。

  1. 入力(今回はN,Ai)を読み取り、データを初期設定する。
  2. クエリを読み取り、データを更新する。
  3. クエリの答えを計算して出力する。
  4. ２と３を繰り返す。

ここで、Q\leq 10^5ですから、各クエリの処理は高速に行わなければなりません。
そのためには、「簡単に更新できるデータを保持する」ことがカギになります。

たとえば、A_1\cdots A_nの各値をいちいち更新していくことを考えましょう。
このとき、一回のクエリで更新するデータは最大N個なので、時間もO(N)かかります。
全体ではO(QN)なので、間に合いません。
そこで、より効率的な形でデータを保持する必要があります。

今の問題だと、各クエリでAの要素の和を求めたいので、そのために必要なデータは何か考えます。
j番目のクエリで、要素の和は(A_i=B_jをみたすiの個数)*(C_j-B_j)だけ変化します。
そこで、

  • count_x:A_i=xであるようなxの個数(x\leqq100000)
  • S:現在のAの要素の和

をデータとして持っておけば、一回のクエリで更新するデータはcount_{B_j},count_{C_j},Sの3個なので、高速に実行できるとわかります。

実装

入力を受け取り、初期値を設定する。

入力自体はint型でおさまりますが、和を計算するとオーバーフローの危険性があるので、long long型を用います。
*8

int N;//Nの受け取り
cin >> N;
vector<long long> A(N + 1);//A[i]の受け取り
for (int i = 1; i <= N; i++)cin >> A[i];

int M = 100000;//A[i]の上限値は100000
vector<long long> count(M + 1, 0);//count[x]の初期設定
for (int i = 1; i <= N; i++)count[A[i]]++;

long long S = 0;//Sの初期設定
for (int i = 1; i <= N; i++)S += A[i];
クエリの処理

各クエリで入力b,cを受け取ったとき、更新する値はcount_b,count_c,Sです。

int Q;
cin >> Q;
for (int q = 1; q <= Q; q++) {
	long long b, c;
	cin >> b >> c;

	long long memo = count[b];//更新前のcount[b]の値を保存
	count[b] = 0;
	count[c] += memo;
	S += memo * (c - b);
	cout << S << endl;
}
まとめ

まとめると、以下のコードを提出することで、この問題に正解できます。
Submission #14629167 - AtCoder Beginner Contest 171


E Red Scarf

概要

  • xorは怖くない。
  • a xor a=0を用いて式変形していく。

考え方

排他的論理和(xor)に関する問題はAtCoderでよく出題されます。なじみのない演算なので面食らうかもしれませんが、慣れれば問題ないです。
「xor 競技プログラミング」で検索すれば、競技プログラミングで使えるxorの技がいくつかでてくるので、問題を解きながら覚えていきたいところです(私もまだまだです)。

次の性質はxorの問題を解くときにしばしば用います。(上2つは当たり前ですが、3つ目はxor独自の性質だと思います。)

今回の問題も、これらの性質を用いて解いていきます。

求めたい整数の値をx_1,x_2,\cdots,x_Nとおきましょう。
いま、各iに対し、
a_i=x_1 \ xor \ x_2 \ xor \cdots x_{i-1} \ xor \ x_{i+1} \ xor \cdots x_N
であることがわかっています。
これを簡単な形に書き直したいです。
そこですべての要素をxorして、S=x_1 \ xor \ x_2 xor \cdots xor \ x_Nとおくと、
a_i=(x_1 \ xor \ x_2 \ xor \cdots x_{i-1} \ xor \ x_i \ xor \ x_{i+1} \ xor \cdots x_N) xor \ x_i =S \ xor \ x_{i}
になります。(累積和をxorバージョンに書き換えたものだと思えばわかりやすいと思います。)

あとは、Sの値を求めれば十分です。
あまり頭を働かせず、とりあえずすべてのa_iのxorをとってみます。
a_1 xor a_2 xor \cdots xor a_N =(S xor x_1) xor \cdots xor (S xor x_N)=x_1 xor \cdots x_N =S
N個の Sがみごとに相殺して、1つだけ残りました！([tex N]が偶数であることを用いています。)

よって、以下の手順で実装を行えば、この問題を解くことができます。

  1. 入力を受け取る
  2. S =a_1 xor a_2 xor \cdots xor a_Nを計算する。
  3. 各 iに対し、 S xor a_iを計算する。

F Strivore

概要

  • みょーん

*1:M - 1.12.文字列と文字

*2:G - 1.06.if文・比較演算子・論理演算子

*3:処理系によっては、char型に対応する整数の範囲が「0以上255以下」となることもあるようです。AtCoderの環境では「-128以上127以下」として問題ありませんが、いずれにせよ負の数との対応は考えない方が安全です。

*4:文字'0'～'9'に対応している数字が0～9ではないのには注意してください。(数字の0と文字の'0'は区別して考えましょう。)

*5:オーバーフローには注意が必要です。0以上127以内の範囲におさまるように足したり引いたりしてください。

*6:配列についてはN - 1.13.配列、 for文についてはL - 1.11.for文・break・continueをご覧ください。

*7:O - 1.14.STLの関数の後半をご覧ください。

*8:私は、MLEしてしまう時以外はいつも整数型にlong longを用いています。

【AtCoder今昔物語】M-SOLUTIONS プロコンオープン B - Sumo

高橋君、すぬけ君、りんごさん・・・AtCoderに登場する様々な人物、彼らの歩んできた人生を私たちは問題文中でしか知ることができません。彼らが一体何者なのか、どういう思いで問題に挑んでいるのか、少ない手がかりを元に解き明かす、シリーズ【AtCoder今昔物語】第一回目は「M-SOLUTIONS プロコンオープン B - Sumo」です。

 

なぜ高橋君は8番以上勝たないと次の大会に出ることができないのか？

今回はその謎にせまります。

 

atcoder.jp

 

ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー

 

負け越せば即引退．．．

令和元年夏場所、ベテラン力士の高橋には土俵人生最大の試練が訪れていた。

 

東京都に生まれた高橋は子供のころから文武両道でまわりの注目の的だった。

とくに相撲の才能は他を圧倒し、慶応大学4年生の時に全国大会で優勝、学生横綱に輝いた。

そして高橋は平成14年春場所、幕下15枚目付け出しで初土俵を踏んだ。

 

鳴り物入りで入門した高橋の実力は、世間の期待を裏切らないものだった。

2場所で幕下を通過したその場所で十両優勝、初土俵から僅か4場所で新入幕を手中に収める。

鋭い立ち合いから速攻で寄り切る相撲、そして何よりも彼の奔放な発言は、たちまち高橋をお茶の間の人気者にした。

高橋が『サモアの怪人』横綱・美羽鳳鵬を破った時にインタビュールームで放った一言、「金星が俺を高めるんじゃない。俺という存在が金星の価値を高めるんだよ。」は今でも好角家の語り草になっている。

平成19年秋場所には関脇に昇進、その後も三役の常連として横綱や大関を大いに苦しめた。

 

しかし、そんな彼も押し寄せる年齢の波に抗うことはできなかった。

 度重なる怪我や筋力の低下により、平成28年には長く保った幕内の地位から十両に陥落、その後も低空飛行を続けた。

そしてついに令和元年夏場所、西十両14枚目にまで番付を落としてしまった。

十両の定員は28名、つまり今の彼の番付は十両の最下位だ。

この場所で負け越せば、幕下への陥落が決定的、幕内での実績が十分にあり妻子もいる彼にとって、それは引退を意味する。

本場所は15日間、なんとしても8勝して来場所に望みを繋げなければならない。

妻のため、子供のため、応援してくれるファンのため、高橋はこの正念場を乗り切れるか！？

 

入力例1

oxoxoxoxoxoxox

 

初日、盤石の相撲で白星をあげた高橋は、その後負けと勝ちを交互に繰り返し、14日目を終えて7勝7敗となる。

千秋楽は東幕下3枚目4勝2敗青木との入れ替え戦！

高橋はこの取組に勝って、十両残留と現役続行をものにすることができるのか！？

 

入力例2

xxxxxxxx

 

夏場所9日目。BS放送にて

NHKアナ「えーここで情報が入ってまいりました。昨日8連敗で負け越し、幕下への陥落が決定的となっていた西の十両14枚目高橋、先ほど日本相撲協会に引退届を提出したとのことです。えー元関脇の高橋が引退です。詳しい情報はまた入り次第お伝えいたします。」

荒磯親方「そうですかー。彼も怪我がありながら、稽古して必死に頑張ってきたのを見ていたんですが・・・残念ですねー。」

 

ーーーーーーーーーーーーーーーーーーーーーーーーーー

 

文章って書くの難しいですね。小説家の人はすごいです、、

 

次回があるのかどうかはわかりませんが、思いついたら何か書きたいと思います。