問題 https://www.ioi-jp.org/camp/2008/2008-sp-tasks/2008-sp_tr-day3_22.pdf 検討 ２次元イモスみたいな方法でやるのかなと思いましたがうまくありません。100万＊100万と非常に広い範囲ですが，個々の折り紙は高々20*20、またその枚数も5000枚以下なので…

問題 C - Synthetic Kadomatsu 考察 解説ACです。 DFSを使う方法，bit全探索（4進数探索）を使う方法の２つがあり，今回はDFSで解きました。 探索はアルゴリズムの基本だなと改めて感じさせる問題です。組み合わせを全探索するときの組み合わせ配列の渡し方…

はじめに ライブラリについて勉強する中でときどきtemplateという記述に出会います。 これがどんな機能をもっていてどんなときに使うのかを学びました。 テンプレート関数 テンプレート関数は，引数の型名が変わってもいちいち型名を変更せずにそのままつか…

はじめに 冷えに不思議の冷えなし 振り返り A問題 B問題 C問題 D問題 はじめに ９月２６日に突如開催されたACL Beginner Contestで冷えて茶に落ちました。 先週、色変して緑になったばかりで７日天下でした。 またがんばって緑にあがればよいだけなのでめげ…

問題 E - おせんべい 考察 JOI難易度６に入りました。さすがに難しいなと思いましたが問題文中の ヒントで Rの上限 10は Cの上限 10000に比べて小さいことに注意せよ． とあるのでRについてbit全探索する解法に気づきます。Rの反転する行はbit 1のときであり…

FOR 文 コード例 ABC127B - Algae While 文 文字列操作 － 文字列中の文字の変換 コード例 ABC126A - Changing a Character リスト コード例 The Zen of Python FOR 文 PythonのFOR文はリストの要素に対し繰り返し処理を行うのでC++のFOR文とはだいぶ雰囲気…

問題 考察 WAしたコード ＡＣ 問題 A - 勇者ビ太郎 (Bitaro the Brave) 考察 条件を充たすものをいちいち数えると計算量オーバーしそうなので、あらかじめ累積和的に数を数えておくことにしました。制約の iがk より小さい と jがlより小さい があるので難し…

Pythonはじめました 出入力 文字列の入力 整数の入力 整数をスペース区切りで入力 配列の入力 数字を整数型で出力 文字列を出力 IF 文 文字列操作 配列の最大値 今日のまとめ Pythonはじめました これまでは、ほとんどC++以外の言語をさわってませんでしたが…

０ 自己紹介 １ 競技プログラミングをはじめたきっかけ ２ 初めてのコンテスト ３ 灰コーダーになるまで ４ 茶コーダーになるまで ５ 緑コーダーになるまで ６ これからのこと このたびめでたく緑化することができましたので茶色に落ちないうちに色変記事を…

問題 考察 提出コード TLE 修正コード 問題 atcoder.jp 考察 M日間の移動で各鉄道を何回利用するかをカウントし、ICカードを購入した場合としない場合で各鉄道の料金が安くなる方を選択します。 提出コード #include <bits/stdc++.h> using namespace std; int M[100100]; i</bits/stdc++.h>…

atcoder.jpいろいろ工夫してもどうにもTLEがとれないのですが、現在の到達点として記録しておきます。mapをうまく使えば高速化できそうな気がします。また今度トライします。 TLEしたコード #include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; v</bits/stdc++.h>…

問題 atcoder.jp 考察 一見してDPです。ちょっと前までは怖気づいてしまって手が出ない類の問題でしたが，EDPCの前半をこなした私は昨日までの私とは違います。とにかく書いてみることにしました。まずはDPテーブルをどう組むか。m日目にnにいるときの疲労度…

EDPC K問題（stone）のけんちょんさんの解説で見慣れない演算がでてきました。K - Stones ゲームを解く！Educational DP Contest K, L 問題の解説 - Qiita if (i - a[j] >= 0) dp[i] |= !dp[i - a[j]]; この縦棒に＝をくっつけた演算子（|=）はビット論理和…

成績 － Highest更新するも反省の多い回 最近の精進 A問題 B問題 C問題 D問題 提出コード E問題 WAしたコード 復習 ACしたコード F問題 atcoder.jp 成績 － Highest更新するも反省の多い回 2020年9月13日21:00-22:40に開催されたABC178に参戦しました。 結果…

ABC026-D 高橋君ボール１号 考察 ACしたコード ABC026-D 高橋君ボール１号 atcoder.jp 考察 いかにも二分探索の問題です。解が複数あるケースもあるということで単純増加でないようですが，二分探索で解けそうです。double型を使い、円周率は少数点以下１４…

巡回セールスマン問題（TSP Travelling Salesperson Problem) DPによる解法 コード例 入力例1 出力例1 入力例2 出力例2 検討メモ 巡回セールスマン問題（TSP Travelling Salesperson Problem) 蟻本P173から巡回セールスマン問題の検討です。 巡回セールスマ…

配列の初期化とmemset 配列の初期化について蟻本P174にmemsetという関数がでてきました。 手元のC++の入門書には載っていない関数でした。これまで配列の初期化をするときにはforループを回して初期化値を挿入していましたが、この関数を使うと簡単にできそ…

トポロジカルソート A.B.Khanのアルゴリズム 典型問題 コード トポロジカルソート 有向非巡回グラフ（DAG）において各ノードを順序付けしてどのノードもその出力辺の先のノードより前にくるようにならべること。 A.B.Khanのアルゴリズム 1962年にA.B.Khanが…

LCS -最長共通部分列問題 ja.wikipedia.org２つの文字列の最長共通部分列を出力する問題です。 計算機科学における古典問題として知られているとのことです。 個数の算出 dp[sのi文字目まで調べたとき][tのj文字目まで調べたとき]=個数 と置いて，dpを回して…

EDPC E-Knapsack 問題 E - Knapsack 2N個の品物があります。 品物には 1,2,…,Nと番号が振られています。 各 i (1≤i≤N) について、品物 iの重さは wiで、価値は viです。太郎君は、N個の品物のうちいくつかを選び、ナップサックに入れて持ち帰ることにしまし…

再帰でDFSを書く練習。 再帰があまり怖くなくなった。簡単なDFSが自力で書けるようになったけどまだ時間がかかる。 いつでもすらすらスムーズに書けるようになりたい。 #include <bits/stdc++.h> using namespace std; static const int INF = 1000000; int H, W; char C[51</bits/stdc++.h>…

問題 https://img.atcoder.jp/other/joi2013ho/joi2013ho1.pdf長さNの電飾の各位置の電球は点いているか点いていないかいずれかである。 任意の範囲で電飾の点灯状態を反転させた場合の交互点灯列の最長を求める。 N 考察 反転範囲を全探索して、などという…