こんにちは。一時に寝たのに起きたら十二時になっていて自分の体のポンコツさを実感しています。とーです。
解くに至った問題（10問）
CADDi 2018 for Beginners:B
全国統一プログラミング王決定戦 エキシビション:B
CODE FESTIVAL 2017 qual A:B
CODE FESTIVAL 2017 qual C:B
AGC:017A
ABC:021B/026C/104C/107B/119C
CODE FESTIVAL 2017 qual A B
N行M列のオセロみたいに、石が全部白を表にしておいてあり、白黒を反転させることができる 黒の数を与えられた数と等しくできますか？という問題
行をひっくり返すことをk回、列をひっくり返すことをl回やったとすると、黒が表を向いている石の数は
k*(M-l)+l*(N-k)
となる
なぜなら、k*(M-l)はk回分の行のひっくり返しをしたうえで（この時ひっくり返した行はすべて黒）、l回のひっくり返しをしていない列を選ぶ（ひっくり返した列を選ぶとまた白に戻ってしまう）場合の数と等しいからである（l*(N-k)も同じ）
んで、これが与えられた数と等しくなるかを全探索すればよい（N,K<=1000なので間に合う）
ABC107B
Grid Compression
列や行を圧縮できるところまで圧縮しましょうねという問題
愚直に列や行を取り除いて圧縮するアルゴリズムを考えていたけど、ちょっとそれは厳しいかなーと思い答えを見たところ、
「'#'が含まれる行、列をマークしておき、その行と列が交差する部分に存在する要素のみが残る」
とのこと
実際それはそうという感じで、マークがつかない→列or行がすべて'.'で構成されているため当然取り除かれるし、交差しているところは行で取り除く作業にも列で取り除く作業にも引っかからないから取り除かれない
考え方はこれでよいので、あとは実装を頑張る
行と列の数だけFalseで埋めたリストを持っておく
row = [False]*H
col = [False]*W
リストL[i][j]が'#'であれば、row[i] = True, col[j] = Trueとしてあげれば、その部分は交差しているのでOK（つまり、i行目とj列目は取り除かれない）
それが終わったら、今度はTrueになっている各行に対し、その行の中で列リストがTrueに代わっている成分だけをprintするようにしてあげればよい
列の改行はいらないが、行ごとの改行はいるので、そこに注意しながら出力する
（改行がいらないときはprint(なんちゃら,end = '' )とすればよいし、改行がいるときはprint()と下に添えればよい）
True/Falseで管理する便利さをまた一つ実感した
ABC021B
最短経路か否かを判定する問題
重みの無い経路における最短経路は閉路（同じところを二度以上通ること）がない（だから、現れる頂点はユニーク）ということに注意すればよい
ABC026C
木構造のようになった上司、部下の関係から、トップの人の給料を求めようという趣旨の問題
あれ？UF使えそう？とか思ったけど、木構造かつその構造が下にどんどん広がっていってよいということから、UFとはちょい違う実装をしなければいけない
やってみたがちょっと厳しそうだったので断念 解説ACをしました
肝心なところは、「自分の社員番号よりも社員番号の小さい人しか上司になれない」ということ
だから、番号を逆順に辿っていくことで、最終的にトップの人が求まればよい
考え方は以下の通り
まず、i番目に社員番号i+1番の人の給料、直属の部下を入れるリストPay_Subを作る
例えば（トップ含め）7人であれば、
Pay_Sub == [[1,],[1,],[1,],[1,],[1,],[1,],[1,]]
みたいな感じ
そして、部下の情報を入れていく
入力が
1
1
2
2
3
3
みたいな感じであれば、
Pay_Sub == 1,[1,2,[1,[3,4]],[1,[5,6]],[1,],[1,],[1,],[1,[]]]
のように入る
そして、リストの中を逆順に見ていき、
len(Pay_Sub[i][1]) != 0のとき（つまり部下がいる場合）、
新たに作ったリストに部下の給料を入れていき、そのmax,minを調べてPay_Sub[i][0]（社員番号i+1番の人の給料）を更新、というのを、iがN-1から0までやればよい
そして、最終的にPay_Sub[0][0]が答えとなる
ABC119C
本番中にACできなかった問題
竹がN本あれば、一本の竹につき、Aに使う、Bに使う、Cに使う、使わないの4パターンがあり、それを全探索すればよい N<=8なので多くても65536通りになり間に合う
また、竹をつなげてから伸ばしたり縮めたりすることと、一本一本の竹を伸ばしたり縮めたりしてからそれらの竹をつなげる作業は等価なので、今回は簡単な「全部繋げてから差分を伸ばす、縮める」でやるのがよさそう
竹をどこに使うかの全探索のやり方が分からず（解説には再帰を使ってやる手法が書いてあったけどこれが思いつくほど精進を積んでない）、0から4**Nを4進法で表し、それぞれの桁を竹一本一本に割り当て、（無から有を生やすことは出来ないので、最低一つの竹をA,B,Cに使うことに注意）0だったら使わない、1だったら竹Aに使う......みたいな感じでやり、このやり方でも一応ACできたが、4進法に直すところで明らかに時間を食っており、改善が必要
誰か教えてください
一応10進法をn進法に変換する簡単なやり方があったのでそれを載せておく
①10進法をn進法に直し、文字列として出力
X = int(input())
def Base_10_to_n(X, n):
if (int(X/n)):
return Base_10_to_n(int(X/n), n)+str(X%n)
return str(X%n)
②10進法をn進法に直し、左から規定の桁まで0埋めしたのを出力
X = int(input())
def Base_10_to_n(X, n):
if (int(X/n)):
return Base_10_to_n(int(X/n), n)+str(X%n)
return str(X%n)
print(Base_10_to_n(X, n).zfill(P)) #P桁埋める zfillは文字列のみ有効
参考にさせていただいたのはこちらのページです。ありがとうございます。
Python Tips：Python でゼロパディングしたい - Life with Python
ABC104C
これも実質的に全探索の問題 工夫が必要で、問題を①全部解く②ちょっと解く③一問も解かない、の三つに分類して、そのうえで「ちょっと解く」は0か1種類でよい（二種類以上を解くのであれば、点の高い方を解いた方が得だから）ということを念頭に置いて解く 全探索は上で紹介した二進法表記でイケるらしい（想定解がそれだから全探索するときN進法に置き換えるのはあながち間違いではないか......？）
