人生人生♪
●はじめに
人生の事とか本気で考えたくないけど
このままじゃ何も成し遂げず死ぬだけなので
泣く泣く考えてブログに書く
文章化した方が達成度が把握できて良い為
●資格
・簿記2級(11月)
取らないと職場で屠られてしまう
・簿記論・財務諸表論(来年以降)
これを取ると資格勉強の泥沼らしいが要取得と言われている
・TOEIC950点・TOEFL
今TOEIC855点だけど何にも話せなくて泣いているので
・台湾語の資格
一回も勉強した事ないけど将来台湾に一度は住みたい為
・応用情報
コロナが終わったらこれは受けられそう
・統計検定
先輩が統計のプロなので勉強したいと思った
●プログラミング
・競プロ
やったからには強くなりたい
だけど絶対に誰とも比較したくない(鬱病になるので）
・サイトデザイン
デザインとプログラミングが好きなのに何でやらない！？
●そのほか趣味
・イラストコンテスト
絵描くの好きなのにいつまでも燻っていたくない
・将棋
頭良くなりたい
・数学・化学・物理
勉強全然した事ないので逆に感動する
●密かな夢
・頭が悪すぎるので院ではない学部の方の大学(理系)に入りたい
入りたいならまた職場復帰できるくらい市場価値を高める必要があるし
もちろん入れるくらい勉強する必要がある
●実現のためにやった事・やる事
・GitHubをまともにやりたくてアカウント再生
・pixiv新しいアカウント作った
・登竜門でめぼしいの応募する
・残り容量常に5GBのPCを買い換えて6月に新しいのが来る
・簿記の勉強をしている
・モニターを買った（嬉しいね♪）
●最後に
・流されてばかりで勤勉とは言い難い自分だが周りの人には圧倒的感謝
無限にお金が欲しい
Pythonでbit全探索
●はじめに
以下の問題は複数の解き方が考えられると推測されますが、
今回はbit全探索の学習として紹介します。
より良い解法・考え方等ありましたら
知る事が出来ると嬉しい為、コメント頂ければ幸いです！
●更新の目安
(0)リンクで飛べるようにする・目次を作る
(1)この実装をしてみる
僕はbit全探索のときいつもこれ使ってます。
— グリ (@grigri_grin) 2020年5月24日
import itertools
n = 4#長さを指定
for i in itertools.product([0, 1], repeat=n):
print(i)
(2)All GreenとKadomatsuを解く
●bit全探索で解く事が可能な問題
(1)ABC045 C.たくさんの数式
(2)ABC079 C.Train Ticket
(3)ABC104 C.All Green
(4)ABC119 C.Synthetic Kadomatsu ※途中です！
(5)ABC128 C.Switches
(6)ABC147 C.HonestOrUnkind2
(7)ABC167 C.Skill Up
●ABC045 C.たくさんの数式
【問題概要】
文字列Sが与えられる。Sの文字と文字の間に"+"を入れることを考える。
全く"+"を入れない場合も考える。この時考え得る全ての数式から得られる
値の合計を出力。
【制約】
(1)1<=|S|<=10
(2)Sに含まれる文字は1~9までの数字
【考え方】
(1)ありうる全ての値の合計を求めたいのでans=0とする
(2)初期の数式として文字列Sの先頭の桁を設定する。
ここに以降の桁の数字をくっつける、または"+"を挿入して
最終的にその出来上がった数式をansに加算すると考える。
(3)全ての"+"の入れ方の組み合わせを考える。
この時の入れ方としてある桁が1であれば後ろに"+"を挿入
という方法を考える。
これはbit表記により実現できる。また与えられた文字列Sに対し先頭から
"+"を挿入するか否か見ていくことを考える為、最下位bitから見る事とする。
この時この組み合わせをqとする。
(4)このqに対してその桁が1であるならば"+"を挿入
そうでないならば以降の桁のうち先頭のものをくっつける
(5)(4)により出来た数式をansに加算して出力
【コード】
●ABC079 C.Train Ticket
【問題概要】
整数A,B,C,Dが与えられる。 A□B□C□D=7が成り立つように
□の中に"+","-"を入れた式を作り、その式を出力。
【制約】
(1)0<=A,B,C,D<=9
(2)与えられた入力に対して必ず答えは存在する
【考え方】
(1)□の数は3→"+","-"の入れ方は2**3=8通り
(2)考え得る"+","-"の入れ方をABC045Cの方法を真似て実装する。
ABC045Cと異なるのは必ず"+"または"-"を入れるという点
ある桁が1である場合は"+"を挿入、
ある桁が0である場合は"-"を挿入と考える
(3)出来た数式の答えが7となるならばその数式=7を出力。
【コード】
●ABC104 C.All Green
【問題概要】
1<=i<=D(i=1,2,3,...,D)のiに対して,100*i点の問題がpi個存在する事が
わかっている。各問題を解く事で100*iの点を得られるが、それとは別に
100*i点の問題の全て、すなわちpi個を解くことにより各コンプリートボーナスci点
を得ることができる。
この時点数の合計Gを達成するために必要な問題数の最小値を出力。
【制約】
(1)入力は全て整数
(2)1<=D<=10
(3)1<=pi<=100
(4)100<=ci<=10**6
(5)ci,Gは共に100の倍数である
(6)合計Gを達成する事は必ず可能である
【考え方】
(1)①pi問全て解く問題、
②一問も解かない問題、
③0より多くpi問より少なく解く問題
の三種類に分けると考える。
③に関しては①を除いた中で最も点数が高い物を選ぶ事とする
(2)(1)をbit全探索で実装するために桁が1になっている場合①、桁が0なら②とすると考える。この時問題があるのは③だが、これはリスト・bit表記を逆向きにし、bit表記で一番最初に0が出てきたら覚えておくことで実現できる。
(3)(2)に従い素直に実装を行う。①ならばボーナススコアも加算する。この時の一時的な合計＜Gであり且つ③の範囲内で加算すればGを達成できるかどうかを確認する。もしそれができるのならば既存の解いた問題数cntと比較し、最小の解いた問題数であるならば更新する。
【コード】
●ABC119 C.Synthetic Kadomatsu
【問題概要】
N本の竹を持っており、各竹の長さはli (i=1,2,...,N)である。
この竹のうち何本かを選び、長さA,B,Cの3本の竹を作ることを考える。
竹に対しては以下3点の操作ができる。
(1)1MPを消費して1本選んだ竹に対してその長さを1プラスする
(2)1MPを消費して長さ2以上の選んだ竹の長さを1マイナスする
(3)10MPを消費して2本の竹を接続して1本の竹とする
この作成した1本の竹の長さは2本の竹の長さの合計と等しい
目的を達成するために必要なMPの最小値を出力。
【制約】
(1)入力は全て整数
(2)3<=N<=8
(3)1<=C<B<A<=1000
(4)1<=li<=1000
【考え方】
(1)
(2)
【コード】
●ABC128 C.Switches
【問題概要】
N個のスイッチとM個の電球がある。
スイッチはonとoffの二種類の状態を持つ。
電球i(i=1,2,...M)はki個のスイッチに
繋がっており、どのスイッチに繋がっているかはsij で与えられる。
この電球は、
(繋がっているスイッチのうちonになっている個数)%2=pi
である時点灯する。
全ての電球が点灯するようなスイッチのon/offの状態の組み合わせの個数を出力。
【制約】
(1)入力は全て整数
(2)1<=N,M<=10
(3)1<=ki<=N
(4)1<=sij<=N
(5)piは必ず0か1
【考え方】
(1)全ての電球が点灯するような組み合わせの個数を求めたいのでans=0とする
(2)全てのスイッチのon/offの組み合わせを考える
(3)全ての電球の点灯し具合を示すリストをlitとしておく
(4)電球のインデックスとその電球に接続するスイッチを見ていく
そのスイッチがonになっているならcntに加算
(5)cnt%2==p[電球のインデックス]ならばその電球は点灯
(6)全部点灯するならばansに加算して最終的なansを出力
【コード】
●ABC147 C.HonestOrUnkind2
【問題概要】
N人の人間がいて、彼らは"Honest"か"Unkind"に分類される。
Honestな人間は必ず正しい証言をする。
Unkindな人間は正しい証言も間違った証言もする。
人iはAi個の証言を行う。各証言は xij yij の形で与えられる。
これは"人xijはyij" という意味である。
(yij=1の時Honest、yij=0の時Unkind)
N人の中に最大で何人Honestな人間が存在するか出力。
【制約】
(1)1<=N<=15
(2)0<=Ai<=N-1
(3)1<=xij<=N
(4)自分についての証言はしない
(5)同じ人に対しての証言は各人1度のみ行う
【考え方】
(1)Honestな人間の最大値を求めたいのでans=0とする
(2)全ての組み合わせを考える。
この時矛盾するかしないかをflagという変数、
(今回はflag=1と初めに設定しておく)
Honestとなった人間のリストをhonest、
Unkindとなった人間のリストをunkindとしておく
(3)Honestな人間の証言が矛盾するケース1,ケース2を考える
ケース1:Honestな人間がある人物をHonestと答えたがその人物が
Unkindに分類されていた
ケース2:Honestな人間がある人物をUnkindと答えたがその人物が
Honestに分類されていた
ケース1,ケース2になった時はflag=0にする
(4)flag=1のままであるならば現在のhonestの人数をansと比較し
大きい方をansとして出力する
【コード】
●ABC167 C.Skill Up
【問題概要】
N個の参考書が売られており、各参考書の値段はCi円(i= 1,2,...,N )である。
各参考書を読むことにより、
M個ある能力がそれぞれAij上昇することが分かっている。
全ての能力をX以上にしたい時、それが達成不可能である場合は-1を、
達成可能である場合は達成が可能となる最小金額を出力。
【制約】
(1)入力は全て整数
(2)1<=N,M<=12
(3)1<=X<=10**5
(4)1<=Ci<=10**5
(5)0<=Aij<=10**5
【考え方】
(1)最小金額を求めたいので、minで更新できるようにans=float("inf")とする
(2)全ての組み合わせを試してみる
(3)その組み合わせを選択した場合の価格をpriceという変数,
その組み合わせを選択した場合の得られる能力のリストをabilとしておく
(4)購入したらpriceに加算、abilに得られる能力を加算
(5)実際に選択してみてそのabilの最小値>=Xとなったら目標が達成したという事
この時はans=min(ans,price)して更新
(6)ans=float("inf")のままだったら目標は達成できなかったという事
【コード】
zip演算
優先順位低(未来・過去)
●遠い未来に買いたい本
Cでポインタの基本を抑える
簡単
基本が身につく
・Effective C++ 第3版 (ADDISON-WESLEY PROFESSIONAL COMPUTI)
・新訂版MORE EFFECTIVE C++ (ADDISONーWESLEY PROFESSIONAL CO)
Effective C++ は非常に評価が高い
ここまでやれば大体OK
・Effective Modern C++ ―C++11/14プログラムを進化させる42項目
最新の基本を学ぶ
・C++ テンプレート完全ガイド (Programmer’s SELECTION)
テンプレートは難しいのでマスターしたいならやる
解説が多い
●興味がある物
・PS (ホスファチジルセリン)
・キャロライナヘレラ212
・艶漢とおそ松のコラボティー
・Blender Bottle, HALEO, PROMIXX
●作った
・ダルゴナコーヒー
●やってみたい言語
・Lisp
●初見
・Fleshgod Apocalypse
ブックマークの管理
まだ使っていないが便利そう
スニペットが作れる
・My Algorithm : kopricky アルゴリズムライブラリ
・GRAPH × GRAPH：競技プログラミングにおけるグラフ可視化サイト
グラフを可視化してくれる。すごい
【概要】
今後使いたい物をメモした。今後もメモするかもしれない。
