Bit全探索のおはなし

はじめに

この記事はKogakuin Univ Advent Calendar 2019 - Adventarの18日目の記事です。

adventar.org

お久しぶりです。今までの記事を全てみてくださった方には今年三回目のご挨拶となりますね。

突然ですが、朗報があります。なんと!アドベントカレンダーが全枠埋まりました!!!!!!!

ありがとうございます。特に複数記事を書かせた書いてくれた方々、卒業しても書いてくださった方々には感謝してもしきれません。

というわけでお待たせしました。bit全探索のおはなしに入ろうと思います。

Bitとは

とりあえず基礎から入っていきましょう。完全に理解している方はスルーしてください。

ビットとは、情報量の最小単位で、二つの選択肢から一つを特定する情報の量。語源は “binary digit” (二進法の数字)と言われ、コンピュータなどでは0と1のいずれかを取る二進数の一桁として表される。

出典:ビットとは - IT用語辞典 e-Words

わかりやすいですね。とりあえず、情報を「0」と「1」の2つの状態で表すんだな〜と覚えていただければOKです。

二進数とは

次は二進数についてです。

2進数とは、数を書き表す方法(記数法)の一つで、基数を2(二)とした表記法のこと。通常、アラビア数字の「0」と「1」の二つの数字を用いてすべての数を表現する。2進数の値の連なりとして表現されたデータ形式を「バイナリ」(binary)という。

出典:2進数(二進数)とは - IT用語辞典 e-Words

二進数は、数を「0」と「1」のみで表現するやつと覚えていただければOKです。

では、少し練習してみましょう!

問題1:10進数表記で「10」を二進数表記にすると A:1010
問題2:10進数表記で「64」を二進数表記にすると A:1000000
問題3:10進数表記で「1023」を二進数表記にすると A:1111111111

分からなかった方はネットワークの勉強をはじめから - 2進数と10進数の変換方法を見るといいと思います。

Bit全探索の考え方

お待たせしました。本題に入ります。

まず、Bit全探索の考え方について 簡単に言うと「ON/OFF」「True/False」「Yes/No」などの2つの事象で全てを表すことができるものの全ての組み合わせを列挙する際に強力な武器となる考え方です。

この考え方は、bitの「0」をとある事象に対する「False」、「1」を「True」として、全ての「True」と「False」の組み合わせを試していくものとなります(ただの概念だから、逆にしても実装はできるよ)。 時間計算量は少なくともO(2n)はかかるため、nが小さいときのみ有効な手法となります。

分かりにくいので例を出します。

4人の大人または子供を一列に並べる。このとき、子供を「0」大人を「1」とすると重複しない全ての並べ方は、 「0000」「0001」〜「1110」「1111」までの16種類の「0」と「1」のみの列で表現することができます。

f:id:yudegaki:20200216234431p:plain
大人 子供 子供 大人で並べた場合のBit列と10進数表記

この画像の10進数表記に疑問を持った方もいらっしゃるでしょう。 ここで先程例に挙げた並べ方のBit列を十進数にしてみると、0〜15の連続した16種の数字であることが分かります。

で?どうやって実装すればいいの?

実装では「連続した数字で全ての組み合わせを表現できる」が大事な考え方となってきます。

実装例を見てみよう!

以下のコードは「000」~「111」までを表示するプログラムとなっています。 先程説明したように「000」~「111」までのBit列は10進数として考えることができます。そのため、0から7まで1づつ増やし、その都度数字を10進数から2進数に変換することで比較的簡単に実装することができます。

このコードの初見殺しの部分を補足します。

まずは「1LL << i」。 1LLはlong long型の1という意味です。

「<<」はシフト演算です。以下の画像を見れば分かると思います。 編集の都合上で何進数かを示す(2)や(10)を省略していますので、エスパーで感じ取ってください。

f:id:yudegaki:20200217122851p:plain
シフト演算の説明

次に「bit & (1LL << i)」 「&」はAND演算。論理回路で学んだ方も多いと思います。 知らない方はhttp://www.cs.shinshu-u.ac.jp/Lecture/LogicCirc/chap7/chap7.htmlへGO!

さて、この演算何をやっていると思いますか?

f:id:yudegaki:20200217125632p:plain
bit演算の説明

ここから、bitに代入された数を2進数として見たときの下からi番目(0スタート)のBitが立っている、つまり1であるかどうかを知ることができると分かります。 また、C言語(C++)のif文では、条件式の値が0だと「False」0以外だと「True」になることを利用し、「if( bit & (1LL << i) )」が真のときにはBitが立っており、偽のときにはBitが立っていないと判断することができます。

演習

いい演習問題がAtCoderにあったため紹介します。

atcoder.jp

私の実装例

この問題が解けた方は atcoder.jp

私の実装例
を解いてみてください。

さいごに

閲覧いただきありがとうございました。 大遅刻してしまって本当に申し訳ございません。

Bit全探索の考え方はプログラミングで役に立ちます。 ぜひこの記事を見てくださったプログラマーの方は覚えて帰ってください!

ではまた次回どこかでお会いしましょう。 ありがとうございました!

競プロのすゝめ

目次

はじめに

この記事はKogakuin Univ Advent Calendar 2019 - Adventar8日目です。

adventar.org

記事を丁寧丁寧丁寧に作成していたところ、時が過ぎていました。

気を取り直して記事を書いていきます。今回は競プロのすゝめということで、僕のTwitterを見てる方ならお気づきの方も多いと思います。

そうです、競プロはいいぞという記事となります。

 

競プロとは...

安心&安全のWikipediaで見てみましょう

競技プログラミング(英語: Competitive programming、略称: 競プロ)とは、プログラミングコンテストで行われる競技の一種である。

競技プログラミングでは、参加者全員に同一の課題が出題され、より早く与えられた要求を満足するプログラムを正確に記述することを競う。

出典:競技プログラミング - Wikipedia

 

情報学部の1年生には、新入生のつどいの際に紹介させていただいたので、覚えてる人もいるかな...?

簡単に言うと、プログラミングの授業の課題の発展版です。

2年次に受講できる「離散数学」や「アルゴリズムとデータ構造」を履修した人なら面白いと感じるかもしれません。感じるよね???

競プロができるサイト

ここではリンクを貼るだけに留めておきます。

初心者の方にはAtCoderとAIZU ONLINE JUDGE(通称:AOJ)がおすすめかな。

atcoder.jp

judge.u-aizu.ac.jp

codeforces.com

www.topcoder.com

面白い問題

先程紹介したAtCoder社が開催するコンテストでは、時々(文章が)面白い問題が出題されます。面白いからといって舐めてかかると顔面に右ストレートを喰らいますが...

実際に問題文を見ていきましょう

Mulitple GIft

高橋君*1は、日頃の感謝を込めて、お母さんに数列をプレゼントすることにしました。 お母さんにプレゼントする数列 
は、以下の条件を満たす必要があります。

  • A は X 以上 Y 以下の整数からなる
  • すべての 1i|A|1 に対し、Ai+1 は Ai の倍数であり、かつ Ai+1 は Ai より真に大きい

高橋君がお母さんにプレゼントできる数列の長さの最大値を求めてください。

出典:C - Multiple Gift

 日頃の感謝を込めて母親に数列をプレゼントするなんて... 普通の家庭ならサイコ扱いされてもおかしくないですよね(笑) お金はかからないので最後の手段としてはアリかもしれない????

Card Eater

すぬけくん*2はカードゲームで遊ぶことにしました。N 枚からなるカードの山があり、上から i 枚目のカードには整数 Ai が書かれています。

すぬけくんはこのカードの山に対し 0 回以上、以下の操作を行い、残ったカードに書かれた値が互いに異なるようにしたいです。最大で何枚のカードを残すことが可能か求めなさい。なお、N は奇数であり、少なくとも 1 枚のカードを残すことが可能であることが保証されます。

操作:カードの山から任意の 3 枚のカードを抜き出す。抜き出したカードのうち書かれた値が最大であるようなカード 1 枚と最小であるようなカード 1 枚の合計 2 枚を選んで食べる。その後残った 1 枚をカードの山に戻す。

出典:D - Card Eater

 一見まともな問題のように思えますが、操作をみるt、、、

口からトランプを出す人*3ならたくさん見てきましたが、カードを食べる人は見たことがないですね。逆再生であることを祈るばかりです。

ドキドキデート大作戦高橋君

高橋君の通っている学校で大掃除が行われることになりました.学校には N 個の教室があり,各教室は 1 から N まで順番に番号付けられており,左から右に並んでいます.

高橋君の学校には高橋君を含め M 人の生徒がおり,掃除すべき連続した教室の区間(掃除区間と呼ぶ)は M 個既に決まっています.しかし,それらの掃除区間を誰が担当するかは決まっていません. 異なる生徒には異なる掃除区間が割り当てられ,割り当てられた生徒はそれに含まれる全ての教室を掃除しなければなりません.1 つの教室が複数の掃除区間に含まれることがあります.

高橋君は大掃除の日に女の子とのデートの約束をしていることに気づきました.デートをサボってしまうと何が起こるか分からないので大掃除をサボることに決めました. 前述の通りいくつかの教室については複数の掃除区間に含まれていることがあるので,高橋君の担当分をサボっても全ての教室を誰かが掃除してくれさえすれば,サボったことがバレないことに気づきました. 掃除されていない教室があった場合には,サボったことがバレます.

あなたの仕事は高橋君のために,サボってもバレない掃除区間を全て教えてあげることです.

なお,この学校の生徒は高橋君を除きみんな真面目なので,高橋君以外がサボることは無いと仮定してください.

出典: B - ドキドキデート大作戦高橋君

デートのために大掃除をサボるとは漢の鑑ですね(泣)

AtCoderでは、このように模範となる人の行動が問題として出題されることがあります。問題を解くだけで、人としてもプログラマとしても成長できるとはお得ですね(?)

器物破損!高橋君

良く見てみるとカードの有効期限が切れていたので、高橋君は諦めて魚屋に直接うなぎを買いに行くことにしました。
 彼の住む街は長方形の形をしており、格子状の区画に区切られています。区画は道または塀のどちらかであり、高橋君は道を東西南北に移動できますが斜めには移動できません。また、塀の区画は通ることができません。高橋君の家から魚屋までの道のりは非常に複雑なため、単純に歩くだけでは辿り着くことは困難です。
 しかし、高橋君は腕力には自信があるので道に上下左右で面している塀を 2 回までなら壊して道にすることができます。

 高橋君が魚屋に辿り着くことができるかどうか答えてください。
出典:

C - 器物損壊!高橋君

腕力に自身があると、塀を壊して進むっていう発想が出てくるんですね...

僕もリングフィットアドベンチャー*4 上腕二頭筋を鍛えて、講義に遅刻しそうな時に壁を壊していけるようになりたいです

 

他にも面白い問題はたくさんあります!興味があったらこのサイトに飛んでみると幸せになれるかも?(上記の問題はこのサイトの一部を選んで紹介させていただきました)

ugis.hatenadiary.jp

競プロ入門

さて、先程の問題をみて「解けねぇよ...」と思った方もいらっしゃるでしょう(私もそうでした)

何事もそうですが、触れたことのない分野の内容は実際の難易度よりはるかに高く感じてしまうものです。 ん?楽に解けてしまった???*5

 では本題の競プロ入門についてお話していきます。

先程色々なサイトを紹介しましたが、結論から言うとAtCoderで問題を解いてみるのがおすすめです。

主な理由としましては

  • コンテスト後の公式解説がしっかりしている(YouTubeでの解説放送&PDF)
  • 多数の言語に対応している(言語アップデートがもう少しで来るはずなので更に増える)
  • 解法(考察)をブログ等でアウトプットする人が多い
  • コンテスト数が多い
  • UI面(直感的に操作できる)

などなど、他のコンテストでは(あまり)無い特徴が多く、初学者にはおすすめのポイントがたくさんあります。

特にUI面は本当に重要だと思います。コンテストまで辿り着けなければ元も子もないですからね。あれ?そういえば、ついこの間UIが変わる前まで、、、だったところがあったような無かったような

 

おすすめの問題

競プロを始めるにしても、何からやったらいいか迷いますよね。

そこで僕もよくお世話になっているけんちょんさんの記事を紹介します。

qiita.com

初学者に対する(もちろん上級者向けも)記事を丁寧に書いてくださっていて本当に尊敬してます。すごいですよね。

ちなみにこの記事が好評なことから、ここで選出されている問題がそのままコンテストになっています。

atcoder.jp

 これらの問題が解けるレベルになれば 、コンテストに参加してみてもいいんじゃないかなと思います。(解かずにいきなりコンテスト参加も悪いとは言いませんが、オススメはしません)

 

さいごに

いかがでしたか?少しでも競プロに興味を持っていただけたならば幸いです。

これを機に参加してださる方は、はじめの頃はレートなんて気にせず、週1のちょこっとした趣味として気軽に参加してみるのがいいと思います。#月刊競プロは役に立たない 等の意見をお持ちの方もいらっしゃると思いますが、年々参加者が増加してますし(今年の増加率はやばかったな、、、)やっておいて損するものでは無いと思います。

 

また、分からない問題や、聞きたいこと等ございましたら、私とか

twitter.com

メンバーに聞いていただければ(できる範囲で)お答えできると思うので、遠慮せずバシバシ聞いてください。(そのままKogCoderに入って♡)

 

次回の記事は、面白い問題から1問選んで解説するものになると思います。また丁寧に書いて時空を歪めてしまうかも

 

それでは、某学院大学に競プロ勢が増えることを願ってこの記事を終わりとさせていただきます。

最後までご覧いただきまして、ありがとうございました。

*1:AtCoder社の社長である高橋直大氏の名字から取ったと予想されている

*2:AtCoderの社員さんのTwitter垢名から取った可能性が微レ存???

*3:マジシャン

*4:Nintendo Switch用のソフトで、プレイするとガッキーになれることから全国各地で飛ぶように売れ、転売ヤー達がこぞって求めるようになった伝説のゲームである。ちなみに発売から約2ヶ月たった今(執筆当時)も入荷未定で予約待ちすら難しい状況である。

*5:KogCoder (@kogcoder) | Twitterに入りませんか?いつでもお待ちしております。

5年目

はじめに

この記事はKogakuin Univ Advent Calendar 2019 - Adventar1日目です。

adventar.org

はじめまして、yudegakiと申します。

今年はなぜかAdvent Calendarが錬成されなかったので、いい伝統は引き継ぐべく(許可はもらってませんが)急遽作成することにしました。(現在11/30 21:45... やべぇよ)

また、Advent Calendarで記事を書いてくださる方を募集しています。どんな記事でも大丈夫ですので、登録して頂けると幸いです。

今回はCORSの回避手法についての記事を書いていこうと思います。

CORS(Cross-Origin Resource Sharing)とは

 ブラウザがオリジン(HTMLをGETしてきたサーバ)以外のサーバーからデータを取得する、クロスドメイン(Cross-Domain)問題を制限するブラウザの制約のことです。この問題を回避する手法としてJSONP(JavaScriptでHTMLにscriptタグを追加する手法)とサーバー側からのレスポンスヘッダにAccess-Control-Allow-Originを追加する手法があります。

WEBプログラミングの授業で、「JSONPはやめたほうが...(意訳)」と言われたので今回は後者の手法について話を進めて行きます。

目標

localhostに建てた鯖から、外部鯖を通してAPIから200のレスポンスを受け取る。

手法

HerokuにFlaskを使って鯖を建て、鯖からAPIにリクエストを送り、レスポンスに'Access-Control-Allow-Origin'を追加したデータをlocalhostの鯖に返す。

コード

gistdf7c844229c70add6df137f86f0e2c08

はい、このままで動きます。

テスト

ではテストをしていきます。

今回はSimpleAPI vol.2 - 最寄り駅Webサービス & 最寄り駅モバイル地図APIを使っていきます。

まずはlocal鯖から直接GETしてみます。

 

f:id:yudegaki:20191130235407p:plain

直接GETしてみた例

あらら、、、怒られてしまいましたね。

では、先程作成したサーバーを踏み台にしてアクセスしてみましょう!

f:id:yudegaki:20191201003756p:plain

サーバーを踏み台にしたときの結果

正常にレスポンスが帰ってきました!

これを使ったサービス例

https://yudegaki.github.io/Optical-character-recognition/

これはGASを使って実装した、画像を送るとOCRした結果を返すというAPIを利用して実装しました。(この場合には、踏み台サーバーは今回省略したPOSTの処理を行っており、POSTで踏み台サーバーにbase64形式の画像を送り、踏み台サーバーが代わりにPOSTを行い、レスポンスに先述のヘッダを付けて返すという処理を行っています。)

GASで建てたサーバーはCORSに引っかかってしまうため、この回避が必要となります。

あとこのサイト、デザインがひどいので改善策を募集しています。バシバシDM OR リプください。

 

おわりに

アドベントカレンダーが始まって5年目だそうで...

今年は色々あり急なスタートとなってしまったため、枠がたくさん空いてます...

どなたか記事を書いてくださると助かります!  助けてください...(泣)

 

明日はKogCoderの期待の星metarinくんの記事です!

PCの前で全裸待機しましょう!!

 

またすぐにお会いすることになりそうですが、温かい目で見てもらえると幸いです。

AtCoder Beginner Contest 124(ABC124)全完

A - Buttons

問題文

2 個のボタンがあり、大きさはそれぞれ A,B です。

大きさ X のボタンを押すと、X 枚のコインを獲得し、そのボタンの大きさが 1 小さくなります。

あなたは、いずれかのボタンを押すことを 2 回行います。 同じボタンを 2 回押しても構いません。

最大で何枚のコインを獲得できるでしょうか。

制約

  • 入力は全て整数である。

考察

この問題は「Aを二回押す」「Bを二回押す」「AとBを一回ずつ押す」の3種類しか数字が出てこないので、この中の最大値を出力してあげれは良さそうです。

実装例

atcoder.jp

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const long long INF=1e18,MOD=1e9+7;
int main(){
	int a,b,c;
	cin>>a>>b;
	c=max(a+a-1,a+b);
	c=max(c,b+b-1);
	cout<<c<<endl;

}

B - Great Ocean View

 問題文

東西に N 個の山が連なっており、西の果てには広大な海が広がっています。

各山頂には旅館があり、あなたは海を眺められる旅館を選ぶことにしました。

西から i 番目の山の高さは Hi です。

西から 1 番目の山頂にある旅館からは必ず海を眺めることができます。

西から i (i=2,3,...,N) 番目の山頂にある旅館については、H1HiH2Hi..., かつ Hi1Hi のとき、その旅館から海を眺めることができます。

これら N 個の旅館のうち、海を眺められる旅館はいくつあるでしょうか。

制約

  • 入力は全て整数である。
  • 1N20

考察

自身の数字がそれ以前の数字全て以上であれば、「合計++;」してあげればよさそう。

二重ループでクルクルさせてあげましょう。

実装例

atcoder.jp

C - Coloring Colorfully

問題文

左右一列に N 枚のタイルが並んでおり、各タイルの初めの色は長さ N の文字列 S で表されます。

左から i 番目のタイルは、S の i 番目の文字が 0 のとき黒色で、1 のとき白色で塗られています。

あなたは、いくつかのタイルを黒色または白色に塗り替えることで、どの隣り合う 2 枚のタイルも異なる色で塗られているようにしたいです。

最小で何枚のタイルを塗り替えることで条件を満たすようにできるでしょうか。

制約

  • 1|S|105
  • Si は 0 または 1 である。

考察

結局最終型は、「0101010101.....」か、「10101010101....」のどちらかになるのは自明なので、上の2つの文字列を予め入力された文字列Sと同じ長さで生成してあげる。

その後2つの文字列をそれぞれ、Sと何個違う箇所があるかをカウントしてあげてその違いの最小値を出力してあげればよさそう。

実装例

atcoder.jp

D - Handstand

問題文

N 人の人が左右一列に並んでいます。

01 からなる長さ N の文字列 S と正整数 K が与えられます。

左から i 番目の人は、S の i 文字目が 0 のとき直立し、1 のとき逆立ちしています。

あなたは K 回まで以下の指示を行います。一度も行わなくても構いません。

指示1lrN を満たす整数 l,r を選ぶ。左から l,l+1,...,r 番目の人の状態を反転する。すなわち、i=l,l+1,...,r について、左から i 番目の人は直立していれば逆立ちし、逆立ちしていれば直立する。

K 回までの指示で、逆立ちした人を連続で最大何人並ばせることができるか求めてください。

制約

  • N は 1N105 を満たす整数である。
  • K は 1K105 を満たす整数である。
  • 文字列 S の長さは N である。
  • 文字列 S の各文字は 0 または 1 である。

考察

最初区間が出てきたので「累積和か??」と思ったけど、実装できるイメージが湧かなかったのでスルー。手元で実験していくと、先頭の番号によって以下のように場合分けできることが分かった。

HOGE1

下の画像は先頭が[0]のときの実験。(*上の画像とは0,1の上下が逆転しています)

HOGE2

 

ここから、([0]の塊の個数-k+1)回ループさせて、各回の値の最大値を出力させてあげれば良さそう!!!!!!と分かる。

N<=100000なのでこの実装ならTLEにならなそう。

実装

  1. 入力
  2. 0,1の連続した個数を保管する配列を用意。
  3. がんばって上の画像の配列みたくなるように実装する。(while文で回してあげればできそう)
  4. 先頭の文字によって場合分け(これをすることで、5(次のセクション)の「先頭||最後)の[0]の塊を含む処理」の実装を楽にすることができます)
  5. (先頭||最後)の[0]の塊を含む処理のときには、前後どちらかの[1]の塊を含まないので、それを踏まえて各回の連続する[1]の個数を求める部分を実装
  6. 出力

 

大まかに言うと、このような流れになります。(わかりづらくてすみません... )

コードを見るとなんとなーーく伝わるかなと思います。(0,1の個数を数える配列を長めに宣言しておいてから全要素を0で初期化すると、先述の5のめんどくさい場合分けの部分を少し楽にできます。等訳わからんことたくさんやってるけど)

 

実装例

atcoder.jp

感想

ABCに出始めて約1年(プログラミングを始めたのも同時期)。ようやく全完することができました!(なお、遅解きで水色パフォだった模様)

目標の水色まであと146?かな。この調子で水色になれたらいいなーと思います。

 

しかし2019年になってからAtCoderのコンテスト参加者数、レベルが加速度的に増加しているので、爆死したときが怖いですね。(今回もDが1000人以上に通されてるし)

マジで取り返しがつかなくなる前に水色になれるように頑張ります。

 

というか、自分の考え方の説明って難しいですね... この記事を見て「は?」ってなった方々ほんとにすみません。

こっちも精進していけたらなーと思います。

 

ご意見や間違い、意味不明なところ(たくさんあるけど)等ございましたら、コメントやリプにお願いします。

記事を見てくださりありがとうございました。

 

   

 

 
 
 
 
 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const long long INF=1e18,MOD=1e9+7;
int main(){
	int a,b,c;
	cin>>a>>b;
	c=max(a+a-1,a+b);
	c=max(c,b+b-1);
	cout<<c<<endl;

}

AtCoder Beginner Contest 120(ABC120)3完

自分の考察まとめとして、コンテスト中に解けた問題までブログを書くことにしました!氷河期以外はなるべく続けて行こうと思います!

A - Favorite Sound

問題文

高橋くんは、自動販売機でジュースを買ったときの音が好きです。

その音は 1 回 A 円で聞くことができます。

高橋くんは B 円持っていますが、お気に入りの音を C 回聞くと満足するため、B 円で最大 C回まで聞けるだけ聞きます。

高橋くんはお気に入りの音を何回聞くことになるでしょうか。

制約

  • 入力は全て整数である。
  • 1A,B,C100

考察

この問題は、「所持金を全て使って音を聞ける回数」と「聞くと満足する音の回数」の小さい方の値が答えとなります。

所持金を全て使って音を聞ける回数は、int型同士の割り算の特徴である「切り捨て」
ex) (int)5/2==2
を使うことによって、「所持金を全て使って音を聞ける回数」は「b/a」と書くことができます。

実装例

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
ll a,b,c;
cin>>a>>b>>c;
cout<<min(c,b/a)<<endl;
}

B - K-th Common Divisor

問題文

正整数 A,B が与えられます。

A も B も割り切る正整数のうち、K 番目に大きいものを求めてください。

なお、与えられる入力では、A も B も割り切る正整数のうち K 番目に大きいものが存在することが保証されます。

制約

  • 入力は全て整数である。
  • 1A,B100
  • A も B も割り切る正整数のうち、K 番目に大きいものが存在する。
  • K1

考察

まず制約がA,B<=100なので、約数全列挙などせずに101から1まで順にAをhogeで割った余りが0&&Bを割った余りが0の時をカウントしながら全探索すればよさそう。 
ここで注意したいのが、AもBも割り切れる正整数のうちK番目に大きいものを出力しなければならないところ。これに引っかかって実装しなおした人多いのでは?(私もです)勝手に頭の中で小さい順に書き換えてしまう癖は良くないですね!ちゃんと問題文は読みましょう(自戒)

実装例

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
 ll a,b,k,cnt=0,ans;//cntの初期化(0の代入)は忘れずに!!!
 cin>>a>>b>>k;
 for(int i=101;i>0;i--){
  if(a%i==0&&b%i==0){
   cnt++;//初期化しないと++動作が不安定になります
  }
  if(cnt==k){
   ans=i;
   break;
  }
 }
 cout<<ans<<endl;
}

 

C - Unification

問題文

机の上に N 個のキューブが縦に積まれています。長さ N の文字列 S が与えられます。

下から i 番目のキューブの色は、S の i 文字目が 0 のとき赤色、1 のとき青色です。

あなたは、赤色のキューブと青色のキューブが隣り合っているような部分を選んで、それら 2個のキューブを取り除く操作を何度でも行えます。

このとき、取り除いたキューブの上にあったキューブは真下の物体の上に落下します。

最大で何個のキューブを取り除けるでしょうか。

制約

  • 1N105
  • |S|=N
  • S の各文字は 0 または 1 である。

考察

違う色が重なったときに、2個のキューブを消すらしい。

ということは、先頭から順に配列を見ていって、赤(青)が来たときに、それまでに消えていない別の色 青(赤)が1つでもあれば取り除けるキューブ+=2」と「青(赤)の残り個数のカウント-=1」を、全くない場合(0個のとき) 現在参照している色 「赤(青)の残り個数のカウント+=1」していけばよさそう

実装例

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
 string s;
 cin>>s;
 ll ans=0,cnt_0=0,cnt_1=0;
 for(int i=0;i<s.length();i++){
  if(s[i]=='0'){
   if(cnt_1==0)cnt_0++;
   else{
    cnt_1--;
    ans+=2;
   }
  }
  else{
   if(cnt_0==0)cnt_1++;
   else{
    cnt_0--;
    ans+=2;
   }
  }
 }
 cout<<ans<<endl;
}

感想

今回は3完14:07で787位でした。

目標にしていた全完はまたも叶わず、、、 いつ全完できるんだか、、、

次回のコンテストはAGCなので早解きでワンチャンレートが上がればいいなーという体で参加したいと思います。(ただ参加者のレベルが上がっているので1完じゃあ厳しいかな...)

水色に早くなりたい!!!!!!!!(あと+265)

 

記事を見てくださりありがとうございました

ご意見や間違い等ございましたら、コメントよろしくお願いします!!

 

 

||||>||#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1e18
bool comp(const pair<int,int>& a,const pair<int,int>& b){
    return a.second<b.second;
}
int main(){
    ll a,b,c;
    cin>>a>>b>>c;
    cout<<min(c,b/a)<<endl;
   

平成30年度秋期FE午後のアルゴリズム問題をC++で実装&AOJ109のSmart Calculatorで動作確認

こんにちは、ゆでがきと申します。
今回は、先日行われた基本情報技術者試験で出題された擬似言語をC++で書き換えたものを紹介していこうと思います。またそのコードが本当に正しいものなのかをAOJの問題計算機 | Aizu Online Judgeで確認していこうと思います。

そもそも問題のコードがなにをやっているか理解できなかった方

daeudaeu.com

この方が丁寧に解説していらっしゃるので、こちらを先に見ることをおすすめします。

実装したコード

 

gistea4de8b4da6d5d30fa35ebf38afdc93c

はい。そのまま実装しただけです。
ひとつ訂正しておくと、38行目のコメントにある"計算優先度の一番高い値を示す"は
"計算優先度の一番高い値の位置を示す"です。

AOJの問題で確認

さて、一番の重要事項である「本当にこのコードは正しいの?」を計算機 | Aizu Online Judgeで確認していきましょう。

この問題は最初に、数式の入力個数であるNが渡されます。その後に数式が入力されるので、その答えを出力しろ。という問題です。

ひとつ気になることといえば、数式が入力される際、末尾に'='がついていることです。ご安心ください。今回のアルゴリズムでは、数字,'+' , '-' , '×' , '÷' , '(' , ')' のみカウントして計算するものになっているのできちんと解を出力することができます。

AOJはいろいろな入力ケースを用意していて、少しでも違う動作をするような箇所があったらAC*1は出ないようになっているので、無事にACを出すことができたら、コードが正しいことの証明になります。

では提出していきましょう。

実装したコード(AOJ109用)

 

gisted7117f4af65a6547404ffd200005cce

先程のコードに、Nの入力受けとN回ループするfor文を実装しただけです。

果たして結果は…?

 

f:id:yudegaki:20181111220109p:plain

はい、ACいただきました。

まとめ

 この記事を書くきっかけになったのが、私自身がH30秋の基本情報を受験してこの問題を見たときに「このアルゴリズムAOJの例の問題に使えるんじゃないか?」と思ったことでした。実際に試してみて、うまく行ったのでこういう形で今回アウトプットしてみました。
本当に大切なアルゴリズムの解説部分ですが、他の方がわかりやすい解説を書いていたので、サボってしまいました(こら)
次回また記事を書くことがあったら挑戦してみようと思います。

クソ記事に付き合ってくださった皆様、ありがとうございました。

*1:Acceptedのこと。競技プロ界隈では”正しい”解を出せたよ、的な意味で使われている

C++のString型個人的まとめ

基本的に<string>をincludeしないと使えないよ!!!!!!!!!!!
あと"using namespace std;"もね
それじゃ、まとめていくよ

編集する文字列の名前をmojiとするよ

・文字列の抜き取り
  str=moji.substr(位置,長さ);

・文字列の反転
  <algorithm>をincludeして
  reverse( moji.begin(), moji.end() );

・文字列の連結
  moji=(str1+str2);

・文字列の削除
  ・末端の文字を消す場合
   moji.pop_back();
    ・任意の場所一箇所を消す場合
   moji.erase(moji.begin()+ここに配列番号);
  ・範囲を指定して消す場合
   moji.erase(moji.begin()+範囲の最初の番号,moji.begin()+範囲の最後の番号);

・文字列の長さ
   moji.length();

・文字列の初期化
   moji.clear();