【C++】tupleの使い方（随時更新）
はじめに
競プロでtupleを使用するたびにググっているので、自分用にまとめておきます。 ここに書いているもの以外を使用した場合は随時追記します。
tupleの使い方まとめ
定義
std::tuple<int, float, string> t;
tupleに入っている値を取り出す
最初に知ったときは「？？」となった取り出し方。
今尚、原理は分かりません。
int i = std::get<0>(t);
tupleの値を変更する
1要素
std::get<0>(t) = 1;
丸ごと
std::tuple<int, float, string> t = std::tuple<int, float, string>(10, 5.5, "hoge");
tuple型を作成する
std::make_tuple();で引数をもとにtuple型を生成して返してくれます。autoと共に使用することで、楽にtupleを生成できます。
auto t = std::make_tuple(10, 5.5, "hoge");
おわり
【C++】空白の区切り文字をscanfで扱う
概要
競プロでC++のcinは大量の入力だと遅いらしい。
そこでscanfを使用しようと思ったが、以下のような入力を配列に入れたい場合にどうすればよいか戸惑ったのでメモ。
▼空白で分割ってどうするの...？
10000000 // 入力される個数 2 5 3 9 5 2 4 7 ...
▼これなら処理できるのに...
10000000 // 入力される個数 2 5 3 9 5 2 4 7 ... ...
こうする
空白は改行と同じ扱いを受けるので、改行の場合と同じようにscanfを使えば良いようだ。
// 使用例
int main()
{
int n;
vector<int> v;
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
int input;
scanf("%d", &input);
v.push_back(input);
}
// 以下略
}
おわり
【AtCoder】ABC108を解いたのでメモ【Python3】
結果と最終提出コード
解答中の心境
【A】
最初わからなくて焦った。紙に例を書くとすんなり解決。
【B】
解説と同じ規則性を5分程度で発見。
【C】
最初は愚直に全探索を行うもTLE。
その後、色々な方法を模索して〈ある要素がxである場合にもう一つの要素yの取りうる値を配列にメモする方法〉をとりました。
...しかし、全探索よりも圧倒的に早くなりましたがTLEは変わらず。
この時点で残り10分程度だったので断念。
【D】
Cに時間がかかりそうだった時にちらっと覗くも『有向グラフ』の文字が。お初にお目にかかったので既読スルー。
解説やコメント
【A】
解説は「足し合わせれば」と書いていますが「掛け合わせれば」ですね。笑（コードはちゃんと掛けてますし）
自分の解法と同じ解法でした。
【B】
これも解説と同じ解法でした。
【C】
余剰で一般化出来たようです。
「各要素をKで割った余剰を使えるのでは？」と考えたにも関わらず見つけ出せなかったのが悔やまれる。
【D】
述べることすらありません。笑
得たもの
- 有向グラフとの出会い
まとめ
コンテストに初参加したが、C問題を瞬殺している猛者がいる。問題に沢山触れているから、解き方がなんとなく浮かんできてスグに解けるのだろうか？それとも、発想の天才なのか...？
過去問を解いている限り、昔の方がCやD問題が簡単な印象を受ける。
【AtCoder】ABC006を解いたのでメモ【Python3】
結果と最終提出コード
解答中の心境
【A】
これは肩慣らし。
【B】
素直に下のコードを走らせた結果...TLEとWA。
（自分で10^6を実行すると数十秒かかるレベルの速度だった...。）
# N の値によってぐるぐる回す a_3 = a_0 + a_1 + a_2 a_0 = a_1 a_1 = a_2 a_2 = a_3
速度の改善がわかないが、WAについては桁が大きくなりすぎてオーバフローしたと思い、
a_3 = (a_0 + a_1 + a_2) % 10007
に変更。すると、WAだけでなくLTEも解消！
「計算の桁を減らすコトはこれほどの速度向上になるのか！」とびっくり。（10^6の場合だと10倍近く速くなった）
【C】
"老人2人=大人1人+子供1人"に気づいたので、足の本数が奇数が偶数かで老人の人数を固定。残りはつるかめ算を使って解いた。
【D】
「ただの挿入ソートか？」と思ったが、
"10, 1, 2, 3, .., 9"
のような場合には対応できないので却下。
結局、やり方が思いつかずに断念。
解説やコメント
【A】
なし
【B】
「参考になる書き方ないかなー」と他の方々の回答を漁っていると...しのみーさんの代入方法が今後役立つと感じたのでリンクとともに紹介を
# こんな感じで一つずつ入れるのではなく... a_3 = (a_0 + a_1 + a_2) % 10007 a_0 = a_1 a_1 = a_2 a_2 = a_3 # 一気に処理してしまう！ a_0, a_1, a_2 = a_1, a_2, (a_0 + a_1 + a_2) % 10007
内部でどう処理されているか分かりませんが、人間が一時的な変数を用意することなく処理が可能でとてもスマートです！！
【C】
- つるかめ算
- 老人の数の固定
を使う方法が紹介されていた。
自分の解答は2つを組み合わせているのでこれは自画自賛OK。
【D】
下の図のように、
- 位置を変更するカードを一斉に引き抜く
- 残ったカードがソートされていれば後は差し込むだけ
- つまり、残ったカードの枚数が多い引き抜きかたを探す
というのが思いつかず、スタートに立てていなかった。
さらに、このままでは速度面に不安が残るので
- 動的計画法
- データの持ち方
に着目することで速度の向上を行えば満点解法になる。
得たもの
- 複数の変数に1行で代入してしまう発想
まとめ
【AtCoder】ABC107を解いたのでメモ【Python3】
結果と最終提出コード
解答中の心境
【A】
これは肩慣らし。
【B】
え？行はif board[i] ==["."]*len(board[i])みたいに綺麗なコードで検索できるけど、列はどうするんだろ...ゴリ押すコードはプライド的に書きたくない...！あぁ...時間が...（結局、プライドなんてものは捨ててゴリ押した。笑）
【C】
計算量削減する方法全く分からない...。最も左のキャンドルと最も右のキャンドルの座標で場合分けして一通り探索する方法でもいけるんじゃね？...お。いけたいけた。
【D】
中央値を地道に求めていく方法なら書ける！でも計算量やばすぎ！中央値を1つずつ地道に求める問題なわけない.......故に、ギブアップなのじゃ！
解説やコメント
【A】
なし
【B】
《白のみの行や列を削除》ではなく、《黒がある行や列を出力》で良かった。これなら記録済みの行や列番号をスキップできるので高速化も可能になりそうだ。
問題文の『削除』につられてしまったので反省したいところ。
【C】
ゴリ押したと思った全探索が答えだった。
正直、この方法以外思いつかなかったのでホッとした。
【D】
全く何も出来なかったので、反省すべきところもない。笑
ごちゃごちゃ言い訳せずに解答だけ貼っておきます...笑
https://img.atcoder.jp/arc101/editorial.pdf
得た知識
- 問題に無意識で思考が誘導されないように注意せねば
- 《二分探索》という探索方法（《二分探索木》は知っていた）
- 数学のように問題を読み替えていく必要性がある
まとめ
- 今回のD問題をこんなに読み替えれるようになれる気がしない。笑
- 武器《二分探索》を手に入れた！
【AtCoder】ABC106を解いたのでメモ【Python3】
結果と最終提出コード
解答中の心境
【A】
- 高校時代に綺麗な公式習った気がするな〜（忘れたけど
【B】
- 105まで問題文に書いているから使わせてもらうぜ！
- 1回目の提出は奇数のみっていう条件忘れてました。ハイ。
【C】
- 「5000兆とかw 1以外の数字出力すれば良いんでしょ」って何も考えずに提出して、1が出てくる例外があるのを忘れてた。2回もWAくらった...笑
【D】
- 1つずつ確かめていく処理自体はシンプルで書きやすかった。
- しかし、提出したコードには
TLEの文字が。良く見ると条件式の値がでかい。しかし、工夫方法が分からずギブアップ。
解説やコメント
【A】
- 公式はこれだ！
(a − 1)(b − 1)
【B】
- 条件分岐で答えを直接出力する方法は頭によぎった。使ったら負けな気がして使わなかった...けど解説に書かれてた。笑
【C】
- なし
【D】
- まず、こういう2次元座標に直す発想がなかった
- さらに、累積和という方法も知らなかった paiza.hatenablog.com
- さらにさらに、二次元累積和もある（今回は未使用でも可）
得た知識
- 《累積和》というすげー方法が！（私が知らなかっただけ...？）
- 動的に累積和っぽいことをする《しゃくとり法》もある
まとめ
- D問題がサクッとできたときは基本計算回数が爆発して殺される。笑
- 武器《累積和》を手に入れた！
【AtCoder】ABC005を解いたのでメモ【Python3】
結果と最終提出コード
解答中の心境
【A】
- たこ焼きうまそう！
【B】
- 上手くやれば1行になりそう...（
.sort()で泣く泣く行を分けた）
【C】
【D】
- あー絶対ゴリ押し無理や...演算数がえぐいやん...でもゴリ押してみよう
- 店員は最後にまとめて評価すればOKでしょ
- ネスト深すぎて草生える（4段ネストになってる）
- TLE以外にWA出てる...速度は置いといて、正解が出る自信あったのに...
解説やコメント
【A】
- なし
【B】
- なし
【C】
- 模範解答通りの答えだった！
- 二部グラフの最大マッチングという方法もある
【D】
- 店員の部分に関しては満点レベルの思考だった
任意の長方形の中の合計値を高速に求める方法（下画像）が全く思いつかなかった...
numpy.arrayのライブラリごりごり使っちゃった。笑
高速化にはアルゴリズム以外に計算するパーツの事前計算が必要！
得た知識
- pythonは
if hoge <= huga <= piyo:みたいな条件式が記述できる！ - pythonのスライス便利。特にnumpyの方は超便利。
- 繰り返しになるが、高速化にはアルゴリズム以外に計算するパーツの事前計算が必要！
まとめ
- ゴリ押しはオーダーを計算してからにしよう！
- D問題はやっぱり難しい！1回書いたら制限時間ギリギリに...修正時間がないのがきつい。
- 間違ったテストケースを見て復習したいので、次回からは最新のコンテストから順にやっていこうと思う。
